Я ☞ Tutorials ☞ Battleship player agent - 2

Previous part: Battleship player agent - 1

From opponent point of view, another board cell consists either the result of a shot or the measured probability of hitting ships:

type Mark = Shot `ML` Integer
 
pattern Shot e = This e
pattern Mist e = That e

The question is: how to calculate probabilities? We have a set of available ships, they cound be arranged on a board anywhere until they touch each other. For this we are going to use Sliding List

To check if we can fit a ship, we should reserve a window:

window ship = ship `yukl` Forth
 `ha` New `ha` State `ha` Event
 `ha` extend @List `hv` by Fore

The next step is to check if we can put a ship into the window cells. We cannot fit the ship only if there is a sunk ship or we miss the target.

If we see that we can fit a ship in a sequence of cells, we could increase probability of that cell to contain a ship.

match cell = cell
 `yokl` Run `ho` Forth
 `ha__` Miss `ho` Shot `ho` Error
   `la` Bang `ho` Shot `ho` Valid
   `la` Sunk `ho` Shot `ho` Error
   `la` (+1) `ho` Mist `ho` Valid

We change the state of all cells in the window only if there are no missed shots or sunk ships:

mount ship = Same `hu` ship `la` is `li` match ship

To be sure to check all possible locations of a ship, we need to slide the window by one cell and start the same process of matching cells until we couldn’t move the window further:

chance = enter @(State `WR` Sliding List Mark)
 `yuk___` State `ho` New `hv__` Event `hv_` mount `ho` auto `ha_'he` Scope `hv` at @(List Mark)
 `yuk___` State `ho` New `hv__` Event `ha` slide `hv` by Future
 `yok___` Retry `ha` Perhaps `ha` not

The algorithm is the following:

• Prepare a sliding window (according to a ship size)
• Calculate probabilities and slide until the end
• Rewind to the beginning, drop the sliding window

distribute fleet = fleet
 `yokl` Forth `ha` Run
 `ha__` intro @(State _)
  `ho_'yok` New `ha` window
  `ho_'yuk` New `hv` chance
  `ho_'yuk` New `hv` rewind

Let’s run it to be sure that algorithm is working at least for a sample:

main = print `ha` that `hv_` distribute fleet `he'he'hv` to known

We can see that there is more chance to hit the ship in the center of the board at the start:

2 4 5 5 5 5 5 5 4 2

And this is result we get if there is the sunk ship on the board:

1 1 # # # 2 4 5 4 2

Aha, we already can spot the problem. According to our rules, ships couldn’t touch other! Probability around known ship cells should be equal to zero.

We are going to fix it in the next part of this tutorial.

Full source code is available here.

Continue this tutorial