Making Chess AI in a day


While studying for the subject AI (just the night before the exam), I decided to make the chess program and test the MiniMax algorithm stated in the book. Although I had around 8 chapters and it was 2 a.m. already, the urge to create this program was so strong that I had to close the book and start the mighty visual studio leaving the exam on luck!

By the morning sunshine, the program looked ready and I needed to test it (which I did only after the exam, because you can't leave so much on luck). The program defeated one of my friend Marinal Alhawat mercilessly (he was the only tester :p well beside me, and I used to close it if I was losing).

And here I am sharing my experience. I have decided to start writing it again while I am drafting this post. [It can take a little longer this time, coz this time, I'll be commenting things ;) ]

Idea

The principle algorithm that we'll be using is called MiniMax algorithm. You can read about it here. Since chess is a turn based game, the algorithm can be thought to give the best move for the turn, So you pass the state of the board to this MiniMax function and it returns the best move along with 'a score' representing the advantage measure of that move.

How?
At each step we generate all possible moves, and play each move and change the state of board. Then we call the same function again with this new state of board, which we believe will return the best move by the opponent and the 'score' of the move. For each move we need to pick the move with minimum score returned. (the score returned is of the move played by opponent). Then we can return the best move along with the score (just negate the minimum score).

Get Started

Open Visual Studio and create a new WPF application. You can also use the remote repository https://github.com/AkshayVats/Chess and clone to 'Initial Commit'.

Using GitHub

This is optional guide.

Cloning a repository

1. Start Visual Studio and choose 'Open from Source Control' [File>Open]
2. From team explorer select 'Clone'
3. Enter the url [https://github.com/AkshayVats/Chess] and a local path
4. Click Clone button
5. Open the cloned solution

Reverting to a Commit

Visual Studio Git extension seems non-functional for reverting. The easiest way is to get the commit Id and use command line to revert to that commit. This is explained here (you'll need git command line)
Few shortcuts, to get commit id from within VS, select Action > View history from team explorer
Choose a commit, right click and select commit details. From details menu Select Actions>Copy Id

To open Command prompt with project directory, Select Changes sub menu from Team explorer. Choose Actions > open Command prompt

Application Flow

The idea is to keep UI away from most logic.


Making the UI

First lets create the board. We'll be using canvas as this container provides absolute positioning system (we can add a ui element and specify its top and left values to display it). I added a new class BoardUi to manage Ui related to chess board. Its current dependency is canvas only. 

In this class, we have a method to draw the board called 'DrawBoxes' which draws the board in 3 steps -
  • Add the border of main board
  • Mark labels
  • Add each box
The result looks like this -




Changes committed as 'Board Ui'

Rendering the board

Next we need a way (or data structure) to represent chess board state in memory and then we will create a method to render this Data structure on the chess board.
To represent the board, we can keep 2D array and each cell can store the piece that occupies that cell. So, essentially a piece contains information about 'what it is' i.e Is it a rook? or some other chess piece and secondly which team it belongs to i.e Is it white or black?
Here I have created a base class called 'ChessPiece' (pretty obvious) and all other chess piece classes like 'Pawn', 'Rook' etc inherit from it. Our base class is also abstract and you cannot instantiate it.

A bunch of classes derive from this base class and provide the implementation of GetIcon method which is required by Ui based classes to show the piece icon.

Another addition is the class 'TurnManager' which will hold the chess board and simulate the chess game. It is also responsible for setting up the initial chess board and calling Render method in BoardUi.

At this point we have our initial chess setup


Changes committed as 'Initial Chess Setup'



Structuring the app

At this point we need to completely structure our app.

This is the code map of our app. Its hard to explain it but the main points are -

  1. MainWindow essentially has only 2 dependencies BoardUi and TurnManager
  2. TurnManager exposes a function called SetupPlayers to provide white and black players (they can be any of human or AI players)
  3. ChessPiece interface available to all other classes (except TurnManager) hides the setter of piece position
  4. ChessPiece now have readonly Team
  5. TurnManager implements the interface ITurnManager that exposes only MovePiece and IconClicked
Also added SelecIcon(ChessPiece) method to BoardUi that will make that piece glow red to signify selection.
Changes committed as 'Structured'


Moving Pieces

First step is to know what are the valid moves for the given chess piece. For this purpose, lets add a function to the interface ChessPiece called IEnumerable<GridCell> PossibleMoves(). This should return the Cells that are valid moves for that Chess piece.
As all our chess piece classes namely Pawn, Rook, etc implement this interface. We can continue providing their definition.

To find available piece what information is needed?

  1. We need full board awareness (so we need a reference to 2D board from TurnManager)
  2. We need current position of the cell in question
See Pieces/xxx.cs file implementation where xxx= Pawn, Rook, etc

So when user clicks on a piece, we can generate the possible moves and color those boxes and when the user clicks a box afterwards, BoardUi can ask TurnManager to make the move if it is possible.
TurnManager can verify valid move by checking if the possible moves list contain the destination cell.

After all this we get this nice looking move indicator,






The user can select any of the valid boxes (green colored) and knight will be moved there!













To be continued...

Comments

  1. This comment has been removed by the author.

    ReplyDelete
  2. Every such thing comes with a #ExamNextDay Story :P Great Work ! :D

    ReplyDelete

Post a Comment

Popular Posts