NAIL122 AI for Games�MCTS Assignment��Peter Guba
Faculty of Mathematics and Physics
Charles University
The Assignment�
Implement MCTS in chess
Steps:
1. Download this project:
https://github.com/peter-guba/MCTS_chess_assignment
2. Open it in Unity and adjust the MCTSNode and MCTSSearch class so that the program performs MCTS.
3. Profit!
Short assignments
Short assignments�
You can miss 2 of the intermediary deadlines – missing more will result in failure.
If you miss a deadline, you have to deliver that part of the assignment the next time you submit something.
Short assignments�
THE SOLUTIONS TO THE SHORT ASSIGNMENTS DON’T HAVE TO BE CORRECT!!!
In fact, you have no way of checking if they are correct. You just have to think about how the given part of the algorithm should work, create an initial implementation that compiles and send it to me.
Short assignments�
You can receive a bonus exam point for completing all the assignments on time (but NOT FOR COMPLETING THEM ALL AT ONCE, as that would partially defeat the point of doing it this way – only for delivering one each week).
The Project
The Project�
I used this project as the basis: https://github.com/SebLague/Chess-AI
The original project was made by this guy: https://www.youtube.com/@SebastianLague
Here is a video explaining the project: https://www.youtube.com/watch?v=U4ogK0MIzqk
(You don’t need to watch it to do the homework, but it’s very interesting.)
The Project�
I used this project as the basis: https://github.com/SebLague/Chess-AI
The original project was made by this guy: https://www.youtube.com/@SebastianLague
Here is a video explaining the project: https://www.youtube.com/watch?v=U4ogK0MIzqk
(You don’t need to watch it to do the homework, but it’s very interesting.)
I had to jerry-rig 2 projects together, so it’s sadly not going to be the prettiest piece of software you’ve ever seen.
How to work with it�
I made the adjustments to the project in Unity 2021.2.6f1, but the original project was made in Unity 2019.4.15f1, so it should work fine in versions from 2019 onwards.
After you run it, you’ll be presented with a chess board and 6 buttons, the functions of which should be quite self-explanatory.
You can change the game and AI settings in the editor by clicking on the Game Manager object and then adjusting the values in its scripts.
AI Settings�
Besides the MCTS algorithm that you are supposed to implement, the project already has a functioning implementation of Alpha-Beta Search. Both of these algorithms have some common settings. Here are the important ones:
AI Settings�
Besides the MCTS algorithm that you are supposed to implement, the project already has a functioning implementation of Alpha-Beta Search. Both of these algorithms have some common settings. Here are the important ones:
If threading is used, then the AI algorithm will be run in a different thread than the main one meaning the project won’t freeze while waiting for the algorithm to finish.
DO NOT USE THIS UNTIL YOU THINK YOUR ALGORITHM WORKS!!! The reason is that, if an error occurs within the AI thread, you won’t be notified, the thread just won’t finish.
AI Settings�
Besides the MCTS algorithm that you are supposed to implement, the project already has a functioning implementation of Alpha-Beta Search. Both of these algorithms have some common settings. Here are the important ones:
If time limit is used, the AI will have a given number of milliseconds to make a decision. This number is entered through the “Search Time Millis” parameter.
THIS ONLY WORKS WHEN THREADING IS USED!!!
Tests�
The tests consist of 15 problems where your program has to find the correct sequence of moves to checkmate its opponent. The problems are divided into three groups of five, based on how many moves the sequence has – 1, 2 or 3, more than that turned out to be too complex. I left the problems for 4- and 5-move sequences as comments, in case some of you’d like to give them a try (you then have to provide the settings though). Otherwise, they can be ignored.
After the tests finish running, the program will tell you how many were completed successfully. There is also a log file (simply called log.txt) to which the results of the individual tests will be written – it is located at ./Chess-AI-main.
Tests�
If you want to play around with test settings, they can be found in the TestSettings class. The parameters for a single test are:
fen – an encoding of the chess board (explained in the section about the FenUtility class)
numOfMoves – the number of moves in which the algorithm is supposed to checkmate the opponent
numOfPlayouts – the number of playouts (simulations) available to the algorithm for the given test
playoutLength – the maximum length of a playout (simulation)
team – the team that goes first
Tests�
You can also make the program stop after a test fails by setting the “Stop Testing On Failure” value to true in the Game Manager settings.
API
Important classes�
MCTSSearch, MCTSNode – The classes that you’re supposed to expand.
Board – Represents the current state of the chess board.
Move – Represents a single move.
MoveGenerator – A class for generating moves.
Evaluation – A class for evaluating states.
FenUtility – Contains methods for storing and loading board configurations.
SimMove, SimPiece, SimPieceType – Classes used in simulation – lightweight equivalents of their counterparts that lack the sim- prefix.
Board�important methods & attributes
WhiteToMove – A boolean variable that indicates which player is on the move.
Clone() – Creates a clone of the board.
GetLightWeightClone() – Creates a lightweight clone of the board (a 2D array of SimPieces). This lightweight clone is used in simulations.
MakeAMove(Move move, bool inSearch) – Applies a given move to the board. The second parameter is set to false by default and isn’t something you need to worry about (it is used by AlphaBetaSearch).
MoveGenerator�important methods & attributes
GenerateMoves(Board board, bool isRoot, bool includeQuietMoves) – Generates possible moves for the given board. The second argument determines whether the node for which the moves are to be generated is the root node. The third parameter is set to true by default and you should leave it that way (it determines whether non-capturing moves are generated too).
GetSimMoves(SimPiece[,] state, bool team) – Generates moves for a state given as a 2D array of SimPieces. Used during simulations. The second parameter determines the team for which the moves are to be generated. Note that it also generates moves if the game is over, so it can’t be used to check whether the game has finished.
MoveGenerator�important methods & attributes
GenerateMoves(Board board, bool isRoot, bool includeQuietMoves) – Generates possible moves for the given board. The second argument determines whether the node for which the moves are to be generated is the root node. The third parameter is set to true by default and you should leave it that way (it determines whether non-capturing moves are generated too).
GetSimMoves(SimPiece[,] state, bool team) – Generates moves for a state given as a 2D array of SimPieces. Used during simulations. The second parameter determines the team for which the moves are to be generated. Note that it also generates moves if the game is over, so it can’t be used to check whether the game has finished.
There is a similar function called GenerateMoves_DO_NOT_USE. DO NOT USE THAT ONE!!!
MoveGenerator�important methods & attributes
GenerateMoves(Board board, bool isRoot, bool includeQuietMoves) – Generates possible moves for the given board. The second argument determines whether the node for which the moves are to be generated is the root node. The third parameter is set to true by default and you should leave it that way (it determines whether non-capturing moves are generated too).
GetSimMoves(SimPiece[,] state, bool team) – Generates moves for a state given as a 2D array of SimPieces. Used during simulations. The second parameter determines the team for which the moves are to be generated. Note that it also generates moves if the game is over, so it can’t be used to check whether the game has finished.
Pay attention to this, it was the most common mistake last year.
Evaluation�important methods & attributes
EvaluateSimBoard(SimPiece[,] board, bool team) – Evaluates how good a state given as a 2D array of SimPieces is.
FenUtility�important methods & attributes
startFen – A string that determines the configuration of the chess board when the program is turned on. This string is in the FEN notation (you don’t need to understand how it works, but, in case you want to, here is a link: https://en.wikipedia.org/wiki/Forsyth%E2%80%93Edwards_Notation
). Useful for debugging.
SimPiece�important methods & attributes
team – The team to which the piece belongs.
type – The type of the piece.
API�
This should be everything that you need to use. If you arrive at the conclusion that you need to also use some other method/property, it’s probably safest to ask, lest it produces unintended side-effects.
MCTS implementation notes
Guidelines�
For tree policy, use UCB. The c parameter should be set to 1.
In the Expansion step, pick actions starting from the last one. (This doesn’t have anything to do with MCTS in general, it’s just the way I did it and it’s important for our implementations to be as similar as possible. In this case, if two or more moves have the same score, which one is picked depends on their order and your results could be affected by this.)
When performing simulations, first clone the state in the node using the Board.GetLightWeightClone method and use the lightweight clone.
When evaluating states, use rewards 0 = loss, 1 = win, Evaluation.EvaluateSimBoard() for anything else. (Alternatively, you can use different rewards if you find it easier, but you need to adjust UCB accordingly in order to achieve the same results.)
MCTS Settings�
If set to true, the number of playouts that the algorithm can perform is limited by the following parameter.
The maximum depth of the playouts. (This is independent of the depth of the tree, so every playout should have this maximum depth, independent of how deep in the tree it starts.)
You need to take these settings into account when implementing your algorithm. Their values are passed through the settings variable.
MCTS Settings�
If set to true, the number of playouts that the algorithm can perform is limited by the following parameter.
The maximum depth of the playouts.
(The values used here are taken from one of the tests – for an actual game, something like 70 000 and 100 might be better.)
Caveats�
THE GAME ENDS WHEN ONE OF THE KINGS IS CAPTURED, NOT WHEN CHECKMATE OCCURS! (This is much easier to check and has also allows the algorithm to identify bad states more easily.)
As the lightweight clone of the current state is just a 2D array, it has no special methods, so there is no method for applying moves to it. However, as doing so just requires changing the position of one piece according to the data in a SimMove object, I thought I could leave this for you to implement where you see fit.
A simulation ends either when it exceeds maximum simulation length, or when one of the kings is captured (again, no method for checking this, for the same reason).
Caveats�
When implementing MCTS, you don’t need to fill out the bestEval variable. AlphaBetaSearch uses this variable for logging, so I left it there but you can safely ignore it if you want to.
After the search finishes, the content of the bestMove variable is passed to the GameManager, so make sure it is filled out whenever the search terminates (possibly by updating it every iteration).
The diagnostics class is present for logging purposes (to see how it’s used, look at AlphaBetaSearch). Again, it can be useful for debugging stuff but feel free to ignore it. If you are going to use it, you can alter its contents however you want.
Resources
Resources�
Resources�
https://www.dailychess.com/chess/chess-fen-viewer.php
http://www.ee.unb.ca/cgi-bin/tervo/fen.pl
https://www.sparkchess.com/mate-in/five
https://www.chesspuzzles.com/mate-in-two
Allows you to convert board positions to FEN notation.
Resources�
https://www.dailychess.com/chess/chess-fen-viewer.php
http://www.ee.unb.ca/cgi-bin/tervo/fen.pl
https://www.sparkchess.com/mate-in/five
https://www.chesspuzzles.com/mate-in-two
Allows you to convert FEN notation to board positions.
Resources�
https://www.dailychess.com/chess/chess-fen-viewer.php
http://www.ee.unb.ca/cgi-bin/tervo/fen.pl
https://www.sparkchess.com/mate-in/five
https://www.chesspuzzles.com/mate-in-two
Offers some more chess puzzles in case you need them.
Resources�
https://www.dailychess.com/chess/chess-fen-viewer.php
http://www.ee.unb.ca/cgi-bin/tervo/fen.pl
https://www.sparkchess.com/mate-in/five
https://www.chesspuzzles.com/mate-in-two
Even more puzzles.
Resources�
https://www.dailychess.com/chess/chess-fen-viewer.php
http://www.ee.unb.ca/cgi-bin/tervo/fen.pl
https://www.sparkchess.com/mate-in/five
https://www.chesspuzzles.com/mate-in-two
Chess program that can solve checkmates.
Resources�
https://www.dailychess.com/chess/chess-fen-viewer.php
http://www.ee.unb.ca/cgi-bin/tervo/fen.pl
https://www.sparkchess.com/mate-in/five
https://www.chesspuzzles.com/mate-in-two
(Can be used to check which move your algorithm should pick.)
End Notes
Some Advice�
If your algorithm either keeps stopping or throws an error somewhere outside your MCTSSearch and MCTSNode classes, you’re probably not setting the second parameter of the GenerateMoves function correctly (this was the most common mistake last year)
Focus on the one-move tests first (comment the others out).
Some people last year tried making and unmaking moves, probably because that’s how the Alpha-Beta implementation works. This is not the correct approach however. Instead, you should always clone the board and then apply a move to it. (To this end, I’ve renamed the UnmakeMove method to UnmakeMove_DO_NOT_USE.)
Don’t forget to use UnityEngine.CoreModule.Mathf for math operations instead of System.Math.
Use breakpoints, not just Debug.Log.
Passing requirements�
YOUR PROGRAM DOESN’T NEED TO PASS ALL THE TESTS TO BE OK. This is due to differences in our implementations. If your solution isn’t passing all the tests but you think it’s ok, send it to me and I’ll take a look (if it isn’t at least passing the majority though, then chances are it isn’t ok).
There are two parts to completing this assignment – understanding the algorithm and being able to debug it. The second part is going to be a huge pain for most of you, so make sure you save enough time for this. If you find you are stuck, feel free to write to me, it is within my expectations that most of you won’t be able to complete this without at least a little guidance.
End Notes�
Once you’re done, send me your solution or discord or via e-mail (guba@ksvi.mff.cuni.cz). DO NOT TRY TO SEND ME THE ENTIRE PROJECT, just the scripts that you have changed/added.
Let me know if you encounter any bugs that I should fix or if you come up with some extensions of the project that would make working on the assignment easier.