Programming Resta-Um using Monte Carlo Method

Question

I have little experience in Java and I’m trying to apply the Monte Carlo Method in Combinatorial Game Theory. I’m trying to demonstrate the Leftover Game Method where it needs to be solved using random steps. For the method to be effective about 10,000 simulations will have to be made, the victories and the most effective steps have to be recorded. The Monte Carlo method has already been applied in other games such as Go Computer. The problems I have had and in the structure of the project, if it is better to have everything sorted by classes, how to record the results, and how to organize the program so as to play randomly.

until now I have the basic structure of the game, and the logic behind the steps allowed.

Answer 1

Define a data structure

At a high level, you basically need to define a proper dice structure to represent the board for the Game.

In the case of Java, it can be a two-dimensional array with the width and height of the board. For example:

int[][] tabuleiro;

Define how information will be represented

Since this array cannot be deformed to suit the board, I suggest starting it with the values:

• -1 (a negative) where it is forbidden to put pieces
• 0 (zero) for absence of parts
• 1 (a) where there is a piece

Initialize with the initial state

Create a method that fills the values across the array, following the rules mentioned above, depending on the initial game board.

Implement the rules of the Game

Implement a method for moving parts:

mover(origemX, origemY, destinoX, destinoY)

The method should check whether movement is allowed or not. For example;

1. The source position must have a part, that is, the value of the array at the position (origemX, origemY) must be equal to 1.
2. The destination position must not contain a part and must be a valid position, that is, the value of the array at the position (destinoX, destinoY) must be equal to 0.
3. The difference of position between origin and destination shall be two vertical or horizontal boxes.
4. There must be a piece between the origin and the destination.

And so on. The above topics are just a simple summary to make the movement.

After verifying that movement is possible, the method must then apply the changes in the vector to perform the movement:

1. The source position of the array receives 0.
2. The destination position of the array receives 1.
3. The piece that was "skipped" from the array receives 0.

Implement the solution algorithm

Now that you have the board and the action implemented, you will also have to implement the solution.

Unfortunately, I don’t know how to solve this board using the Monte Carlo method, so I can’t give an initial direction at this point.

However, before implementing anything, you must solve the problem first. This means that you must somewhere have a specification of the algorithm that solves.

Once you have this algorithm, that is, a sequence of steps that solves the problem after a limited amount of iterations, then it will be much easier to think of a solution by putting everything you have together.

Registration of operations

Recording the steps taken by the solution algorithm is something quite simple.

At each step of the algorithm, print in the console or in a text file the "decisions" made.

In addition, in the method mover() mentioned above, print also the movement being carried out. For example:

Moving part from (origemX, origemY) to (destinoX, destinoY)

Or if it is an invalid move:

Invalid motion attempt from (origemX, origemY) to (destinoX, destinoY)

Only with this tracking can you rebuild the game step by step on a real board.