Chess AI

Chrisir

@ asimes:

hello asimes, I was just looking at your chess engine AI 2.

Do you allow for a few questions?

What is the general program architecture, do you have a frontend for the display of the board and entering the moves and separately a backend for the AI ?

Is that the normal way of doing it? How do backend and frontend communicate? Is there a code like e2e4 etc.? Is it vital for the AI to know the entire game or would it be sufficient if the frontend would hand the entire current board to the backend?

Thank you so much!

Greetings, Chrisir ;-)

asimes

Personally I think of my program as almost only a back-end. The front-end is just visually showing the current state and handling click / drag.

For reference: http://alexsimes.com/index.php?foo=visual programming&bar=chess ai 2

I actually made AI 2 (as well as AI) before studying the Minimax Algorithm which is the algorithm it should be using. The process I made up when writing it was similar in a general sense. There are a number of functions that need to be implemented:

State Representation:
Determine how you want to think about the board. Personally I decided that an integer array of 64 elements (one for each square on the board) made sense at the time. White pieces were enumerated (Pawn -> 1, Rook -> 2, etc.) and Black pieces were stored in the same way but negative (Pawn -> -1, Rook -> -2, etc.). A 0 represented no piece on the board.

I plan on making another again (maybe in the summer when I have more time) and now know that it is possible to represent the board with a long (it has 64 bits, two ints could works as well) for each piece type. There would be a long for white pawns, another for white rooks, etc. The advantage is that you can move many pieces at once or calculate moves efficiently by using shifts and bitwise operators.

Visual Representation:
This actually is the easiest part and I found it fun to design pieces. Given any state (as described above) iterate over the board and draw the appropriate piece. It is useful to have a functions for drawing each piece as well as either color. Otherwise you could also use images, but really this is not a very expensive computation as you only have to draw the board when a piece moves generally.

Interaction:
Personally I find that entering commands is quite tedious and that a click and drag style of control is nicer, Processing has mouse functions that make this easy as well. To prevent pieces from being moved in a way that breaks the rules of chess, on mouseReleased() call a lookup given the piece that was selected and determine if the move was valid. Note that this updates the state of the board if it was valid

Move Generation:
This can be tedious to do as it has to be tested again and again because if it is wrong the whole thing will not work. The idea is that given a state iterate over every square. If a square is not 0 then a piece is there. If it is white's turn and the square is > 0 then it is a white piece and movements need to be generated. Likewise, if it is black's turn and the square is < 0 then it is a black piece and movements need to be generated.

Search:
For every movement that could happen given the current state, store a new state. You can get away with less storage by instead storing what is different between the two states but this is also more complicated, I am going to assume we are storing complete state (int array of 64 elements).

For my own program I traversed this list of states in a breadth-first search. If the initial state is called A1 (this is just a name, not a variable) and it can generate 20 new unique states, then each of of these could be called A1-B1, A1-B2, … A1-B20. For each state A1-Bi, perform the same procedure so that each A1-Bi has its own list of possible states that follow it (note, these are the other player's possible moves) producing all possible A1-Bi-Cj. This can continue for an arbitrary amount of depth but keep in mind that calculating movements and storing states are both exponential, things can very quickly get out of hand by making it go just one step further.

Each state has to be "scored" and the assumption that a player picks the "best" move should be made. Explaining this here is quite complicated, I would recommend reading about the Minimax algorithm.

Chrisir

Thank you very much!