Inside this repository are my tic-tac-toe projects This project was my introduction to artificial intelligence, through creating an algorithm that could play Noughts and Crosses (Tic-Tac-Toe). I started by using a 2D list to make the board. This worked well as it was easy to make the evaluation function which works out the state of the board, whether someone has won, or if the game is still going.
The Minimax algorithm works by searching all of the following boards until they reach a terminal state, which is a win, draw or loss. Then the two players in the game are either maximising or minimising the score. The score of a board is 10 if noughts won, and -10 if crosses won, and 0 if it is a draw. The noughts would be maximising, and on their turn they would choose the height score, and on a crosses turn they would choose the smallest score. So the recursive minimax function will search all the boards, then work its way back to the starting position, calculating the best move.
This worked well, however was slow. There were two ways I could optimise it. I could either make the code run faster, or reduce the number of positions that the computer searches. I started by reducing the number of positions searched. I used alpha-beta pruning, which will reduce the number of boards searched by seeing if the person/ai would ever chose that move as it would go to a losing position. This sped up the ai, as it had to search less boards, by eliminating certain paths.
However it still wasn't fast enough, so I tried to make my code run faster. I found that chess AI's use bitboards as a way to represent the board so their algorithms work faster. Instead of using python lists, where the evaluation function is slower, by using bitwise operations you could speed up the algorithm. You would store the board in a list of 2 elements, which were integer values. When converting the integer values into binary, you would get a layout for the flattened board. Where a 1 was, would be where a player has moved. However you would need 2 boards, one containing the positions of the noughts, one for the positions of the crosses. Then any function used in the evaluate function would need to use only bitwise operations, which were faster and this sped up the algorithm a lot.
After feeling complete with my algorithm, scanning the first turn in under 0.3 second, I tried to make 3D noughts and crosses. This was done by stacking 2 more noughts and crosses boards behind the first one, creating many more paths to win. This wasn't too hard to code, however I ran into the issue that with the MiniMax algorithm, allowing it to search all positions took too long, even with bitboards and alpha-beta pruning. This led me to limit the depth, however it never could work with a deep enough depth to be good.