As an experiment, I want to teach an ANN to play the game of Nim.

The normal game is between two players and played with three heaps of any number of objects. The two players alternate taking any number of objects from any single one of the heaps. The goal is to be the last to take an object.

The game is easily solvable and I already wrote a small bot that can play Nim perfectly to provide data sets for supervised learning.

Now I am struggling with the design question, how should I output the solution to a specific board state. The answer always consists of two components:

  • How many stones to take (a more or less arbitrary integer value)
  • Which heap to take the stones from (the index of the heap)

What are available design choices in this regard and is there a state-of-the-art design for this type of problem?


1 Answer 1


Nim is a simple game and it's really simple to build a bot that gives the optimal solution.

The correct move is to leave an odd number of piles of size 1

So when it comes to training an ANN to play a game, there are some this to keep in mind.

  • Fixed play area (This is taken care of as there are only 3 stacks)
  • Providing input to the model so it knows it's current state (You can use a simple array of integers [3, 4, 1] denoting the current state of the stacks)
  • Providing feedback. An important step to guide the network in the right direction (You already have an optimal bot to do this)

Now that you can easily cover all the requirements, it's pretty simple to teach the model.

  • Input - Current state of the model [3, 4, 5]
  • Output - Move that model will make [2, 0, 0]
  • Final output - Here you will have to add another layer with a custom function.

    This is the important part, to direct the model. Check if the move made is GOOD, BAD or ILLEGAL and assign a custom output to the same. For example

    • GOOD return1 if it matches one of the optimal moves.
    • BAD return 0 if it's not the optimal move and
    • ILLEGAL return -1 if the move is not allowed.

Another thing to keep in mind is that this might require a slightly larger network as it as to learn complex functions that are not linearly separable.

You don't need to train that model by playing it against itself as you already have the optimal solution. Playing against itself is required only when you are trying to achieve something that better than the current best agent.

Check this out, it's pretty interesting Neural network to play snake

  • $\begingroup$ Good answer, just note the Nim can be played with N stacks. There the winning strategy is to finish every move with a nim-sum of 0. Nim-sum is the sum in binary, neglecting all carries from one digit to another. see Wikipedia: en.wikipedia.org/wiki/Nim#Mathematical_theory $\endgroup$
    – Cohensius
    Commented Aug 19, 2021 at 5:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .