0
$\begingroup$

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?

$\endgroup$
-1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Using the term “model” for describing the neural network and it's number of input neurons prevents, that the Nim game is analyzed by itself. This results into a misunderstanding what human players are doing in the game, what their strategy is and which features will become important. Nim doesn't have to do with “complex functions that aren't linearly separable” but with different heaps and a number of stones the player can take. $\endgroup$ – Manuel Rodriguez Jun 17 at 7:14
  • $\begingroup$ If you look into the optimal strategy to win a game of Nim, you would have come across the term Nim sum which is an XOR function. As I have mentioned in the solution, XOR is a linearly inseparable function $\endgroup$ – skillsmuggler Jun 17 at 7:27
  • $\begingroup$ "Nim doesn't have to do with “complex functions ... of stones the player can take." All algorithms and function of a computer are based on logic and a game of nim has nothing to do with a stone rather it's a mathematical equation from the perspective of the ANN. $\endgroup$ – skillsmuggler Jun 17 at 7:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.