Friday, October 9, 2009

Move generation part 1

OK, first off I'm gonna try to make these blog entries less wordy,(yeah right) and put more technical comments into the source code. If you have any questions, add your comments to the blog, and I will do my best to answer them.

OK, last post we set the stage for having the program generate moves. In alpha5 we get started on doing just that. It's by far the most complex task to date.

We define move generation as the process of generating a list of possible moves. MoveGen does not include the actual selection of a move to be played on the board.

MoveGen serves two purposes...

1. To help the engine make a move. In this case I will have the program generate a list of all possible moves, then use a recursive algorithm such as MiniMax to choose the best move from the list.

2. To help determine whether or not a move attempted by drag and drop in the GUI is legal. In this case the program will generate a list of all possible moves for the piece being moved, then verify that the attempted move is on this list.

In my program, the MoveGen process will consist of three phases...

1. Generate a list of pieces and locations for the side to move.

2. Loop through the piece list, Generating candidate moves for each piece based solely on the properties of the pieces and the geometry of the chessboard.

3. Trimming the list to reject candidates on the basis of castling rights, enPassant eligibility, and whether or not the proposed move leaves the king in check.

We need to give some thought as to how to create arithemetic formulas that describe the way each piece moves. In this sense there are two categories of pieces...

1. Knights, pawns, & Kings - The legality of one attempted move has no bearing on the legality of any other attempted move. For these pieces, we make use of large static arrays that are stored in the Data class.

2. Bishops, Rooks, Queens - These pieces move along lines. As we search along a line for possible moves, the search along that line stops as soon as we encounter a non-empty square.

Currently I have completed phases 1 and 2 of the MoveGen process, for both purposes and for piece category 1.

MoveGen is controlled from the GUI in three ways...
1. When the user drops a piece on a square, purpose 2 is initiated via the isLegal() method of the Utils class. If the move is legal according to the work done so far, then the GameState object is updated and the board is repainted.

2. When the user clicks on the moves button, purpose 1 is carried out, and the list is displayed in the text area. No changes are made to the board or GameState object.

3. When the user clicks on the move button, purpose 1 is carried out, and then a move is chosen randomly from the list, at which point the GameState object is updated and the board is repainted.

You will notice that move lists are compiled into a static array of integers in the MoveGen class. Move lists are not passed as arguments in any way. No move objcts are created until a final move is actually selected. There are important performance benefits to this approach when it comes to to develop a recursive algorithm for selecting an optimal move for the engine to play.

Finally I have added a setup checkbox to the GUI. When the checkbox is selected, the entire MoveGen process is bypassed for moves by drag and drop, and you can move the pieces without restriction. You can see that when the box is deselected, you are unable to move category 2 of pieces at all. Category 2 will be the next step.

As always, documented source code and an applet version of the program is available on the fchess2 website.

Have a nice day.

No comments:

Post a Comment