Possible Improvement: Generate N legal boards from current state

[Meerkov]

Hi, I read your article and thought it was a nice read. Just adding this comment as another possible improvement to drive the number of turns down.

Currently, the probability of each square is calculated individually for each ship. An alternate method would be to generate N legal boards from the current gamestate, and use that to inform the probability.

This would likely eliminate the need for hacking in probability adjustments for shooting near successful hits, as well as provide better long-tail behavior, including games when the first several shots are misses. The boats will interfere with each other's positioning, allowing a more accurate probability distribution using this sampling method.

[aydinschwa]

Hi Meerkov, first off thanks for the fix on the place_ships function! Agreed that generating all legal boards from the current game state would eliminate the need for hacking probability adjustments for shooting near successful hits. I'm not clear on why it would improve performance though, my intuition is that this method would have the same performance as the one that's already implemented.

[Meerkov]

Imagine a small 1x6 board. [0,0,0,0,0,0]
And two boats (size 2 and size 3).

In the current system, the following happens:
2 ship can be at: position [0:1], [1:2], [2:3], [3:4], [4,5] : 5 possible locations.
3 ship can be at: [0:2], [1:3], [2:4], [3:5]: 4 possible locations.
This would seem to indicate there are 20 possible positions...

This results in a probability distribution that leans towards the center and away from the sides, but doesn't provide any sure hit. The first attack will be either at index 2 or 3, with a probability of 5/6 to hit.

The proposed system would place both ships:
There are only 6 valid configurations.
[2,2,0,3,3,3]
[2,2,3,3,3,0]
[0,2,2,3,3,3]
[3,3,3,0,2,2]
[0,3,3,3,2,2]
[3,3,3,2,2,0]

This indicates that actually, you have a 100% chance of a hit at the 1st and 4th index.

Edit: And because evaluating every possible legal board state may be infeasible, I suggest sampling N legal boards at random to reduce the computation time.