0
$\begingroup$

Question

How can I train a machine learning model to predict best next move using reinforcement learning for Battleship? (using reinforcement learning is the key of this question. I want it to learn the formulas for "best move from a statistical standpoint")

The best move is the one that minimized the number of turns until all ships are sunk.

I plan to use Tensorflow. From my understanding, this is how the model should look like for this problem:

# Each input neuron is a categorical variable:
# 0.00 < x <= 0.25: missed shot
# 0.25 < x <= 0.50: ship hit by shot
# 0.50 < x <= 0.75: sunk ship
# 0.75 < x <= 1.00: cell that has not been chosen/shot yet

tf.keras.models.Sequential([
    tf.keras.layers.Dense(5 * 5),  # input is a 5 x 5 board
    tf.keras.layers.Dense(4),  # hidden layer, can be any number

    # output is a 5 x 5 board,
    # each with a value 0.00 <= x <= 1.00
    # low values are bad or invalid moves,
    # and high values are good moves
    tf.keras.layers.Dense(5 * 5),
]

and in pseudocode for the whole algorithm:

# Creates a game board of size 5x5 with ships randomly placed in a valid configuration
game = setup_board(x=5, y=5)

until game.is_over():
    game.make_random_valid_move()

    # TODO: where and how should the reinforcement learning take place?

Statistically best move

From a statistical standpoint the best:

  • first move is anywhere not near edge
  • move when there is a hit, but unsunk, ship is an adjacent cell

Battleship rules (non-standard, simplified for StackExchange question)

  • Grid/board is 5 units by 5 units
  • Ships are randomly placed in horizontal or vertical orientation
    • Ships do not move across turns
  • Ships must have at least one unit of padding between ships
  • There are 1× 2-unit ship and 1× 3-unit ship

Example configurations

  • · denotes a missed shot
  • × denotes ship hit by shot
  • █ denotes sunk ship
  • denotes cell that has not been chosen/shot yet

Empty board

  • Starting board for all games
░░░░░░░░░░░░░░░░░░░░░
░   ░   ░   ░   ░   ░
░░░░░░░░░░░░░░░░░░░░░
░   ░   ░   ░   ░   ░
░░░░░░░░░░░░░░░░░░░░░
░   ░   ░   ░   ░   ░
░░░░░░░░░░░░░░░░░░░░░
░   ░   ░   ░   ░   ░
░░░░░░░░░░░░░░░░░░░░░
░   ░   ░   ░   ░   ░
░░░░░░░░░░░░░░░░░░░░░

First shot

  • Sub-optimal first move
░░░░░░░░░░░░░░░░░░░░░
░ · ░   ░   ░   ░   ░
░░░░░░░░░░░░░░░░░░░░░
░   ░   ░   ░   ░   ░
░░░░░░░░░░░░░░░░░░░░░
░   ░   ░   ░   ░   ░
░░░░░░░░░░░░░░░░░░░░░
░   ░   ░   ░   ░   ░
░░░░░░░░░░░░░░░░░░░░░
░   ░   ░   ░   ░   ░
░░░░░░░░░░░░░░░░░░░░░

Optimal shot

  • Since there are two hits, and ships cannot be adjacent, then then two shots must be hitting the same ship
    • the next shot should either be to the left or right of the existing shots
░░░░░░░░░░░░░░░░░░░░░
░   ░   ░   ░   ░   ░
░░░░░░░░░░░░░░░░░░░░░
░   ░   ░   ░   ░   ░
░░░░░░░░░░░░░░░░░░░░░
░   ░ × ░ × ░   ░   ░
░░░░░░░░░░░░░░░░░░░░░
░   ░   ░   ░   ░   ░
░░░░░░░░░░░░░░░░░░░░░
░   ░   ░   ░   ░   ░
░░░░░░░░░░░░░░░░░░░░░

Choose left

░░░░░░░░░░░░░░░░░░░░░
░   ░   ░   ░   ░   ░
░░░░░░░░░░░░░░░░░░░░░
░   ░   ░   ░   ░   ░
░░░░░░░░░░░░░░░░░░░░░
░ · ░ × ░ × ░   ░   ░
░░░░░░░░░░░░░░░░░░░░░
░   ░   ░   ░   ░   ░
░░░░░░░░░░░░░░░░░░░░░
░   ░   ░   ░   ░   ░
░░░░░░░░░░░░░░░░░░░░░

Choose right

░░░░░░░░░░░░░░░░░░░░░
░   ░   ░   ░   ░   ░
░░░░░░░░░░░░░░░░░░░░░
░ · ░ · ░ · ░ · ░ · ░
░░░░░░░░░░░░░░░░░░░░░
░ · ░ █ ░ █ ░ █ ░ · ░
░░░░░░░░░░░░░░░░░░░░░
░ · ░ · ░ · ░ · ░ · ░
░░░░░░░░░░░░░░░░░░░░░
░   ░   ░   ░   ░   ░
░░░░░░░░░░░░░░░░░░░░░
  1. the × becomes █ to denote that the ship is sunk
  2. ships cannot be adjacent, so the adjacent cells are ruled out

Game over

░░░░░░░░░░░░░░░░░░░░░
░ █ ░ █ ░ · ░   ░   ░
░░░░░░░░░░░░░░░░░░░░░
░ · ░ · ░ · ░ · ░ · ░
░░░░░░░░░░░░░░░░░░░░░
░ · ░ █ ░ █ ░ █ ░ · ░
░░░░░░░░░░░░░░░░░░░░░
░ · ░ · ░ · ░ · ░ · ░
░░░░░░░░░░░░░░░░░░░░░
░   ░   ░   ░   ░   ░
░░░░░░░░░░░░░░░░░░░░░

All ships have been sunk, so the game is over

Improve this question
$\endgroup$
2
  • $\begingroup$ Welcome to AI Stack Exchange. This could be the basis of an interesting question, but it looks like you need a full tutorial on how to understand and implement reinforcement learning. That's not really feasible, it would be too much. Plus resources for that already exist. I suggest find a tutorial that does something similar to your game, and attempt to continue your project that way. Ask a more focused question when you hit a specific block that stops you following the example or tutorial $\endgroup$
    – Neil Slater
    Commented Sep 3, 2023 at 8:54
  • $\begingroup$ As a simple suggestion, I think you can solve this problem in various ways. Probably the classic alpha-beta search would be enough to solve small grids and should be way simpler to implement and debug than RL. Also, you can try a tabular RL algo like policy iteration to avoid the burden of deep RL. Another option, would be a model-based RL approach like using monte carlo tree search (MCTS). $\endgroup$
    – Luca Anzalone
    Commented Sep 3, 2023 at 13:58

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .