Unbeatable Noughts And Crosses using artificial intelligence
An implementation of the Noughts and Crosses game for 3x3 and 4x4 boards, using the MiniMax algorithm.
Release notes
Version v1.0.0 is available. What's new.
Introduction
The rules for this implementation are:
- The program allows the user to choose the game type (human v. computer, human v. human, or computer v. computer).
- The computer player can win or draw, but never lose.
- The user has the choice of which player goes first.
- The user can play on a 3x3 or 4x4 board.
I decided to implement a C# application with a GUI for this project.
Structure / organization
The GUI logic is separated from the GUI-agnostic code, so that the classes can be easily plugged in a console application, for example. The game can now be played in a 4x4 board as well.
There are two "conventions": player1
always stores the first player, and the first player's mark is an X.
The code is organized as follows:
GUI agnostic
- Player.cs:
It saves the name of the player, its turn, and if it's a robot or a human.
- Board.cs:
Stores the marks in a two dimensional
string
array. - GameStats.cs:
Checks for a winner and saves the winner stats, i.e., the type and index of the winner line, and the wins/draws/losses.
Game engine
- AI.cs:
A class with common methods to be shared by the derived classes. All child classes have a
CalculateCell()
method to initialize the relevant variables and anAlgorithm()
method for the recursive calculation. The latter is invoked by the former. - AIMiniMax.cs:
The simple MiniMax implementation. Too slow for boards bigger than 3x3.
- AIMiniMaxAlphaBeta.cs:
The MiniMax implementation with alpha-beta pruning. It works reasonably better than the previous for a 4x4 board up to a depth of 8 levels. It's the one actually used in the game. Other algorithms can be used, updating the proper line in the
RobotTurn()
method of the MainWindow.xaml.cs class:AIMiniMaxAlphaBeta ai = new AIMiniMaxAlphaBeta(); //AINegaMaxAlphaBeta ai = new AINegaMaxAlphaBeta(); pos = ai.CalculateCell(board, first);
To get better results in a big board, specially for the first moves, alpha-beta is not enough, since it depends on the order in which children are visited. Initial shallow searches followed by some move-ordering technique, implementing "memory" through transposition tables or any other techniques could be investigated, (but were not used here).
– See also: rough benchmark.
GUI related
- MainWindow.xaml.cs:
Connects the GUI-agnostic part of the application and the GUI-related part. It uses a
UniformGrid
and lightweightTextBlock
s for the grid. The menu uses two modal dialogs, FormNew.xaml.cs, to fetch the relevant data and start a new game, and MenuPopUps.xaml.cs, to provide extra information.To set a position in the board, two variables are needed: an
index
for the GUI grid, and a pairpos {i, j}
for the board, wherei
is the row index andj
is the column index.The human and robot logic flows are very similar. They are covered by
RobotTurn()
andHumanTurn()
, at the end of whichUpdateGameStatus()
is called. - FormNew.xaml.cs:
It allows the user to choose human or robot players and set who goes first. It also provides inputs for the human's names. In case names are not provided, defaults are used. The GUI is updated with every click on a radio button. Finally, the user can select the board size.
- MenuPopUps.xaml.cs:
The pop-up modal windows for the other items of the menu.
- Styles.xaml:
Where the styles of the application are set.
Unit Tests
There are one file per class and one or more methods per class method.
The testing was done with a mix of unit tests, the Visual Studio debugger, and good ol' paper and pencil.
To do
- Implement move-ordering? Check the Dictionary or HashMap classes out.
- Find a good code profiler.
- Implement the MVVM pattern for the views.
- Implement bindings. This is a bit tricky because the binding can only be made to one-dimensional arrays, which would need a restructuration of the
Board
class, and they should also implement theINotifyPropertyChanged
interface, which would make the application non-GUI agnostic.
Rough benchmarking
How much faster is "faster"? I performed a very rough test with the help of the Stopwatch
class, letting the computer play against itself on a 64-bit Intel Core i7 @2.40GHz and 8Gb RAM running Windows 7. These are the results for depth = 8:
Turn | NegaMax (3x3) | MiniMax (3x3) | NegaMax α-β (3x3) |
MiniMax α-β (3x3) |
NegaMax α-β (4x4) |
MiniMax α-β (4x4) |
---|---|---|---|---|---|---|
1 | 921.5219 | 914.1616 | 71.9640 | 37.2818 | 1487.5512 | 1450.5537 |
2 | 122.3636 | 131.0587 | 16.6207 | 15.3873 | 649.3235 | 648.4331 |
3 | 45.4589 | 23.9258 | 4.3286 | 4.9744 | 1883.5635 | 1899.4341 |
4 | 2.1258 | 2.8447 | 0.4310 | 0.4447 | 489.4397 | 492.3388 |
5 | 1.2838 | 1.3201 | 0.3635 | 0.1428 | 329.4927 | 324.9467 |
6 | 0.1633 | 0.3314 | 0.1398 | 0.1265 | 148.9294 | 147.3261 |
7 | 0.0949 | 0.1240 | 0.1090 | 0.0816 | 110.4120 | 72.6110 |
8 | 0.0573 | 0.0560 | 0.0209 | 0.0226 | 59.3166 | 57.3879 |
9 | 0.0303 | 0.0128 | 0.0277 | 0.0295 | 32.8582 | 21.3582 |
10 | 7.4715 | 7.4809 | ||||
11 | 0.8514 | 2.6638 | ||||
12 | 0.9908 | 0.9878 | ||||
13 | 0.3262 | 0.3275 | ||||
14 | 0.0500 | 0.0555 | ||||
15 | 0.0688 | 0.0667 | ||||
16 | 0.0320 | 0.0320 |
NegaMax and MiniMax oscillate in between similar (average) values inside a window of systematic variations. However, compared to their pruning versions, the speed-up is evident.