Unbeatable Noughts And Crosses using artificial intelligence

An implementation of the Noughts and Crosses game for 3x3 and 4x4 boards, using the MiniMax algorithm.

Screenshot of a winning board Get the code

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 an Algorithm() 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 lightweight TextBlocks 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 pair pos {i, j}for the board, where i is the row index and j is the column index.

    The human and robot logic flows are very similar. They are covered by RobotTurn() and HumanTurn(), at the end of which UpdateGameStatus() is called.

  • FormNew.xaml.cs:

    Screenshot of the form that fetches the variables to start a new game.

    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 the INotifyPropertyChanged 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:

Time in milliseconds elapsed per computer turn.
Turn NegaMax (3x3) MiniMax (3x3) NegaMax
α-β (3x3)		 MiniMax
α-β (3x3)		 NegaMax
α-β (4x4)		 MiniMax
α-β (4x4)
1921.5219914.161671.964037.28181487.55121450.5537
2122.3636131.058716.620715.3873 649.3235 648.4331
3 45.4589 23.9258 4.3286 4.97441883.56351899.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.

Get the code