My Life With Battleship

My life With Battleship

by Curt Rostenbach

Battleship.png

High School

I learned how to program computers in high school (1970-73). We had two ASR-33 teletypes with built-in acoustic couplers. 

ASR-33
ASR-33 Teletype

These gave us access to a Digital Equipment Corporation (DEC) Program Data Processor (PDP) model 8/I running Timesharing System (TSS) version 8/I.  I had seen and played some of the games that came with the system, but it was seeing a fellow student, Dave Langraf, demonstrating a game he had written called FOXBAT that gave me the idea to write my own.  I had spent the first 12 years of my life being an only child growing up on various farms.  My closest friend my age lived three miles away.  I didn't get to play many games.  It was mostly reading, television, and my imagination.  But occasionally my folks would visit friends in town and I'd get to play games with others.  One game I liked to play was called BATTLESHIP

Seeing Dave play a game of his own design, it struck me that I could write my own to play.  Dave's program was essentially a computer mediated game where two people would play against each other.  One person would fly a bomber with the intent of evading the other player flying a fighter and attempt to drop his bombs on the target.  The fighter would attempt to destroy the bomber with air-to-air missiles. 

But my idea was to have the computer play me instead of another person.  This goal forced me to learn programming to achieve that end.  It also required analyzing the game in order to figure out how to tell the computer to play. 

The project was broken into two pieces. 

My first version, I attempted to write in FOCAL-8.  However I ran out of memory even before I had the ship placement logic written. 

So I was forced to move to BASIC-8, which had just come out with a newer version that supported CHAINing.  I had started in FOCAL-8 because it was the only programming language I knew at the time.  Moving to BASIC required learning the language as well. 

I learned that if I picked a project to do on my own, it would force me to learn whatever was necessary to do the task.  Which I thought was much better than being assigned a task.  Generally the person assigning the task also thinks they know how it should be completed.  I would use the self-learning aspect for the rest of my career in programming. 

Design decisions

As I researched the game, I came to the conclusion that I couldn't program an exact version of the game.  The problem I ran into was how to tell where the boundaries of the ships were.  The computer's ships I would know because I'd be assigning values to them.  But the player's ships, not so much.  I didn't want to force the player to tell the computer where their ships were.  This would invite accusations that the computer could cheat.  To deal with that problem, I had to introduce a new constraint into the game.  The plastic game pieces on the commercial product already limited you to horizontal or vertical placement, not diagonally.  My added rule was that ships could not be end to end or side by side.  In other words, they couldn't touch.  But you could place them diagonally from each other. 

Methodology

Placing Ships

For each of the ships, the computer would pick a random location on the board.  It would then randomly choose Horizontal or Vertical orientation.  My initial version would then randomly choose to go Positive or Negative from that location.  My later version would always go positive, since it is the initial location that is most important.  It would then do a trial run to position the ship based on its size.  If there were any violations from touching another ship, running off the edge of the board, or encountering an exclusion zone of a previously placed ship, it would go back to choosing a random board location.  If no violations occurred, the ship would then be positioned on the board.  This would continue until all the ships were positioned in legal locations. 

Battle Phase

Battle Logic: Intialization

The program would initialize itself by building an array of ships and their sizes. 

Ship name Size
Aircraft Carrier 5
Battleship 4
Destroyer 3
Submarine 3
PT Boat 2

One for the player and another for the computer. 

The computer would then create a "shooting pattern" of every other location.  Again using random numbers, it would jog to one side or the other, so that you could not anticipate which locations would be shot at. 

Battle Logic: Potshots

In the beginning, the computer would choose a random location on the board, but it would only shoot at every other location, avoiding locations that were:

Once an opponent's ship was HIT, it would shift to hunt mode. 

Battle logic: Hunt Mode

With the first HIT, the initial hit location would be noted.  This would be used to reset the location being fired upon after a MISS, or if the edge of the board would be encountered. 

Again, the program would rely on random numbers to determine whether to shoot horizontally or vertically, plus or minus.  If the next shoot was a MISS, it would reset and shoot in the opposite direction, changing axis if:

The number of resets would be tracked and if the count exceeded a certain value, as when you have shot all around the initial HIT location without scoring another HIT, a cheat situation would be declared and the game would be forfeit.

Once another HIT is obtained, the program will continue to shoot in that direction unless:

In any of those instances, it would attempt to reverse direction.  Shooting would then continue in that direction until the ship was SUNK.  Failure to sink the ship would result in a cheat determination, either by the axis would need to change after a run had been determined, or the number of HITs is larger than the existing unsunk ships. 

Battle logic: SUNK

After a ship is SUNK, it is marked as such in the list of ships, then on the board, and then an invisible exclusion zone would be marked around the ship where there were not already shots taken at those locations. 

If there are no longer any ships remaining, a win is declared, and the computer would print out a screen showing where remaining computer ships were located.  Otherwise the battle logic resumes taking potshots. 

Battle Logic: Player shots

Essentially in the trading of shots, the computer is merely doing the bookeeping, reporting HITs and MISSes, and in the case of SUNK, reducing the count of computer ships.  If the count of computer ships reaches zero, the computer announces that the player has won. 

Conclusion

This version of BATTLESHIP, or as I had to name it, BATSHP, because the file system in TSS-8/I limited file names to six characters maximum, almost won a game once.

Analysis

The placement of ships by the computer could at times be very devious.  This was a result of using random numbers.  A person, subconsciously, desires symmetry and balance of some sort.  It is not difficult to put yourself in the place of your opponents and think, "Where would I place my ships?"  With the computer's random numbers, you couldn't do that. 

On the other hand, the computer had no such empathy going the other direction, so its shots were many times "uninformed." 

Winning in Battleship is essentially a matter of reducing the volume of where a ship could be.  Since the game was programmed to shoot at every other location, in order to be assured of hitting the smallest ship on the board, there was just too much space for the ships to be located, even with the exclusion zones cutting down the volume. 

Furthermore, the computer would waste shots on locations where a ship could not fit. 

In the end, I was disappointed by the success rate of the program.  But I enjoyed the "hunt", so to speak, of learning how to analyze the problem and then learning how to write a program that at least, attempted, to exhibit artificial intelligence by being able to take the place of a person. 

College

First, let me admit that I did not go to college.  I worked at one.  I was a computer operator for the University of Iowa Physics Department.  Working 3rd shift, I was responsible for the operation of two Univac 418 computers (Models I and II, pick your level of obsolescence) running data reduction programs written by experimenters to process information from satellites Pioneer 10, Pioneer 11, and Hawkeye I.  Later, another Univac 418, this time a Model III, was added to my responsiblilites. 

Since I worked 3rd shift, I was given a list of production programs to run for the night.  If I finished the list before the end of my shift, I was allowed to use the computers as my own.  So I would rewrite the programs to make them run faster. 

The experimenters loved me because I stretched their grant money, they were billed for time.  My coworkers loved me because I would perform time/motion studies and make some jobs easier to run.  The system programmers, not so much. 

But I learned how to program in FORTRAN and ART418 Assembler. 

Since most of my time was spent waiting for jobs to finish, I had time to do analysis and then write programs.  So I decided to revisit my BATSHP program, rewriting it in FORTRAN. 

A Quantum Leap Forward

Since the problem was reducing the volume of space to shoot at, I looked at the minimum number of shots required to sink each ship. 

For the Aircraft Carrier, that meant every 5th location.  Twenty shots guaranteed the Aircraft Carrier would be hit at least once. 

Aircraft Carrier grid
Aircraft Carrier grid

For the Battleship, every 4th location, 25 shots. 

Battleship grid
Battleship grid

The Destroyer and Submarine, every 3rd location,

Destroyer/Submarine grid
Destroyer/Submarine grid

and every 2nd location to hit the PT Boat

PT Boat grid
PT Boat grid

Unfortunately those patterns do not overlap well. 

All grids
Combined grids

So I decided to go for a little inefficiency and use every 4th and every 2nd location to shoot at. 

Large Small grid
Optimal grids (Battleship and PT Boat)

The plan was to shoot on the large grid (every 4th location) to target the large ships, possibly picking off the smaller ships at the same time.  After the large ships had been sunk, and if there remained smaller ships on the board, the program would shift to shooting at the smaller grid (every 2nd location).  This would fold the two grids together.  Fast forwarding a bit, I observed one game where the player had positioned his ships such that every ship was going to be hit using the large grid.  I knew immediately that there was no way he was going to win. 

Another change I adapted was when it came to picking a location to shoot at.  Before taking the shot, a routine would look to see if the smallest ship still on the board would fit at that location.  If not, it was as good as a shot and I would have the program "haze" it out, so it would never be considered again. 

The next breakthrough was the creation of the "Discrimination" function that instead of randomly shooting around the first HIT location, it would look to see which direction had the longest run of available locations.  It would then shoot in that direction, if the shot was a MISS, instead of shooting in the opposite direction as the previous version did, it would call the discriminator function again. 

Another feature of the discriminator was that it would check to see if the smallest ship still on the board would still fit.  If not, it would cry foul.  I had once seen a game where the player cheated, but the computer did not catch on until after he had won the game. 

We have a winner

This new design not only started winning, but it started racking up a 60% win ratio.  Some people would always win, others always lose, and the rest, like me, win and lose.  When I moved to the Chicago area in 1976, to be a computer programmer for the Milwaukee (Rail)Road at Union Station, I rewrote the program in IBM's FORTRAN IV to run on an IBM S/370.  When testing, it beat me four times in a row.  By the fifth game, I was getting desperate to win and thoughts of Frankenstein and his monster were swirling around in my mind.  I finally won that game and was able to declare it ready to take on the world.  I play for enjoyment, I programmed the computer to kill. 

The Apple II version

A few years later, I was working at one of the first microcomputer stores that were coming into existence, and I converted my FORTRAN version to APPLESOFT BASIC. 

I also connected with a computer game company called Gamemasters.  They had an Alpha Micro timesharing computer that they sold time on to play games over modems.  As I remember, this was around 1982-83.  For them, I wrote a client/server version that ran an Alpha BASIC version of my program for the battle logic for the server and a graphical program that ran on an Apple II as a client.  I don't remember if the term Client/Server was even around at that time.  Like most of my career, I tended to be 10 years ahead of the pack.  Too early to be of any real use to me. 

Gamemasters was definitely too far ahead to succeed either.  A major problem that would not be solved until years later, would be how to handle multiple real time events over modems running at a blistering 300 baud (30 characters a second). 

The Big Putdown

Home game consoles were starting to come to market and so in 1979, I approached Milton-Bradley (the copyright holders of the game at that time, it is Hasbro now) and offered them the game.  I figured I could rewrite it again in Assembler for whatever hardware they chose. 

Instead, I was brutally told, "There is no market for single player games."  Remember me mentioning how I tended to be 10 years ahead of the curve?  This was one of those moments. 

So I figured there was no where I could go.  I certainly couldn't sell my Apple II version without their lawyers jumping all over me, so I just let it languish. 

They eventually came out with a two player electronic version that had you enter the ship positions and added sound effects.  And still later they came out with a handheld version (single player). 

Graphical interfaces

I kept picking at it over the years.  When the Macintosh came out, I started work on a MAC BASIC version. 

MAC BASIC was a bit primitive then.  You had to jump through all sorts of hoops to make the graphics work.  I ended up converting the core logic because I was finally able to abandon line numbers and go back to symbolic names for the routines, much like I was able to do with the FORTRAN version. 

However my access to a Mac was limited, this being the days of the 512K "Fat" Mac.  I did not think the Mac had really arrived until the Mac Plus came out with 1 MB of RAM. 

So I never finished the MAC BASIC version, but I did start to realize my usual control loop was not going to work in that environment. 

When Microsoft's VISUAL BASIC 1.0 came out, I got excited again and made another attempt to convert Battleship to use a graphical interface. 

This time I tried to use buttons with graphics for each of the boards.  You haven't seen slow until you see VB 1.0 try to monitor 200+ buttons. 

This was when I reached the absolute conclusion that my text based version was never going to function without a complete rewrite.  And that was when development of the graphical version stalled for many years. 

Years Pass

I never truly gave up on at least thinking of Battleship.  I contemplated going beyond static board analysis and thought of bringing statistics to the game. 

I was looking for a way to give the program a bit of empathy as to where ships could be located.  While I liked how the game could come up with confounding layouts from using random numbers, I thought it could be improved by training it where not to place its ships, to avoid the times when it made them easy targets.  Given local storage, and today's Internet communications, could it start acquiring knowledge of where people tend to place their ships and where they tend to shoot, and then use that information to avoid being hit, and where to assign priority of shots on the gameboard? 

I figured I'd go with three levels and two sets, one for seeking and the other for avoidance.  The three levels would be;

These would applied in a sliding scale.  Especially for the seeking out of ships. 

The last game list would be the shots from the last game played, but only the seeking shots, not the tracking shots.  Woe be upon the person too lazy to move their ships between games. 

The player list would be an aggregate of all the games played with that player. 

The general player list would collect all the games from all the players. 

Present Day

The Cloud Lifts

Those of you that know me, are aware of some of the health issues I have dealt with over the years.  Back in 2011, I underwent a liver transplant.  It is said transplantees notice a change fairly soon after the transplant.  I'll agree with that.  It seemed as though a cloud had lifted over my mind.  However, I had to go back into the fog by taking a fairly powerful pain medication to deal with the extreme pain in my feet.  Who would have thought getting a liver transplant would make your feet hurt? 

Luckily after a year, the pain receded and I took myself off of the drug.  And the cloud lifted once more.  A solution to the Battleship problem emerged. 

In a way, it reminded me of a mental quirk I have.  I'm not alone with this, many other people have mentioned that it happens to them as well.  It seems my subconscious does not really give up on problems.  It's not something I rely on, but sometimes after a night of sleep, I wake up and see a novel solution to a problem I have been working on. 

Getting off the drug felt like that.  A problem that had been worrying me for years, suddenly had a solution. 

So I started work on the current version of Battleship using C#.NET. 

Olde Tyme Programming

During my programming career there have been several revolutions in programming. 

Unfortunately I'm still more comfortable in Structured, than I am in Objects, but I was hoping to use Battleship as way to change my methodology.  I was only partially successful.  Certainly the project suffered from creeping featurism, but not so much in the form of program features, but in attempting to replace the "magic numbers" the original code used with enumerations. 

Certainly the structure I used to track status kept getting enlarged.  I think in the next version I will break it up into two status structures, one for the player and another for the computer.  The original code did not need structures as large as the one I ended up with.  Modern code can be much wordier and convoluted than the old text driven programs. 

But certain things were added easily.  Take the voice output for one, I added it on a whim and it was ridiculously easy.  It only became less so when I attempted to fine tune the pronounciations.  It became necessary to maintain two sets of text, one for display purposes and the other for pronounciation. 

For example, "PT Boat" had to be encoded as "Pea Tea Boat"


This page is still under construction


home

E-mail curt@rostenbach.com