The Battleship Algorithm February 4, 2010Posted by eric22222 in General, Math.
As Stephanie has posted, I managed to win the first event of the 2010 CSC Decathlon without even being present. Here is the story.
The Battleship tournament was Friday night, but I knew I had to work. I had joked with Todd about just writing down my moves in advance, knowing that wouldn’t do the trick. That morning, I was explaining how I couldn’t make a good set of rules without some sort of conditional statements. Todd said that as long as it was easy to understand, I could give it a try. So, during my two Friday classes, I wrote out my step-by-step plan, as well as some configurations for my own pieces.
Surprisingly enough, I managed to get three consecutive victories, netting me the blue ribbon.
But enough talk. Here’s the algorithm I wrote out. It could’ve been better, but it got the job done.
BATTLESHIP BATTLE PLAN:
Opening attack: E5, F6, D4, G7, G3, D8, C3, H8, H4, C7, F2, E9, I5, B6
Cleanup 1: If two hits are in the same row/column, then beginning with the upper-left hit, aim one cell in the direction of the second hit. Use chart until a sink:
All hits that were part of the sink are considered “closed.” If two open hits are in the same row/column, repeat cleanup 1.
*Clearest line: the direction from a cell that goes farthest without a moss or border in the line. In case of a tie, a coin flip can decide clearest line.
Second strike: B2, I9, B10, I1, A5, J6, E1, E10, A1, J10, J2, A9
If applicable, repeat cleanup 1.
Cleanup 2: Beginning with the cell A1, spiral clockwise inward looking for an open hit. Attempt a strike in the first cell in the clearest line. Use the above chart. If, after a sink, cleanup 1 is applicable, revert to it. Repeat until all hits are closed. By the completion of this step, the cruiser and battleship will have been destroyed.
Search & Destroy: Starting with A3 and working right/down diagonally, attack any cell in which four adjacent cells are open (note A3 itself fails the requirement). On a hit, use cleanup 2. Repeat Search & Destroy with starting cells C1, A7, and G1. Only one ship can possibly remain.
The Wild Hunt: Repeat Search & Destroy, but reduce the number of required adjacent open cells to 3. Proceed to two, then one.
When taking the lead: “That ship has a lot in common with your chance of winning. (lower voice) It’s sinking.”
1st hit after 1st sink: “I’m about to sink your boat. With math!”
1st hit after 2nd sink: “I’m about to sink this boat, too!” If opponent replies “with math again?” reply “No, with red, plastic missles!”
Opponent takes early lead: “Math beats luck in the long run.”
After sink, far behind: “Time for the greatest comeback in Battleship history!”
In lead, one boat left to fine: “Now it’s just a matter of time…”
First move it a hit: “I like where this is going.”
Starting new step: “Initiating phase <name>.”