Monday, October 12, 2009

Move Generation part2. Defining Checkmate and Stalemate.

Last time we got started on having the program generate legal moves, and I wrote in detail about the different phases of legal move generation, the different purposes, and the two categories of pieces that have distinctly different methods of move generation. We expand on those concepts in the alpha6 phase.

With the alpha6 phase, we complete the process of all aspects of legal move generation, touch wood, which includes definitions of check, checkmate, and stalemate. At this point, a thorough understanding of the GameState class, and all the different ways its variables can change, is required to fully understand what is going on. Also, you should try to understand the difference between a candidate move and a legal move, I'll describe that a little more below.

The process of having the engine make a move starts with a call to the getMove method of the Engine class, passing a copy of the current GameState object which contains all the information needed for the engine to make a move. The getMove method calls the moveGen method to generate a list of candidate moves, then calls the makeMove method for each candidate move to do the final legality check. The engine then selects randomly from the list of legal moves. This random selection will of course change in the future. Note that each call to makeMove returns, for each legal move, an updated gameState object representing the game state after the move is made. Depending on the move selected, it is the updated GameState object which is used to update the central GameState in the Game class.

The makeMove method makes use of an important new boolean method called isSquareAttacked. This method is used to prevent the engine from castling through or while in check, and also prevents the engine from leaving its king in check. There is one more use for this method which sheds light on the way in which game ending conditions are detected. In the getMove method of the Engine class, if the list of legal moves has length 0, then isSquareAttacked is called on the king position. If the answer is true, then it must be checkmate, otherwise it must be stalemate. Thus checkmate is not detected until the engine tries to make a move in a checkmate position. This may change in the future.

It is worth noting that the legality check for moves from the GUI uses the same code as legal move generation from the engine. Instead of choosing randomly from a list of legal moves, we check to see that the move made in the GUI is included in the list of legal moves. Legality checking for a GUI move is initiated from the mouseReleased method. At such time as I am certain that all bugs are worked out, I'll have separate legality code for the GUI, as there are some useful reasons for completely separating the emgine and GUI code.

I'll point out that the methods of legal move generation can be repeated many thousands of times when enalyzing the consequences of a single move. Therefore as I delve into move selection algorithms such as negamax/alphabeta, I expect to change some of the moveGen code in order to improve performance.

Finally there are a few changes in the GUI. The most significant is the addition of left and right arrow buttons which allow us to move backwards and forwards through the move sequence. This makes use of an ArrayList of move objects which is stored in the Game class. We also have added a setup checkbox which bypasses move legality checking and allows us to manually set up a position to be played out.

The next installment will probably feature some improvements to the GUI and the introduction of a negamax recursive algorithm for selecting the best move.

As always, updated source code and applet are available on the fchess2 website.

Have a nice day.

1 comment:

  1. amatorish coding style, using global variables, and unmeaningful identifirs

    ReplyDelete