Tuesday, October 20, 2009

Quiescent Search and Piece/Square Tables.

Ok, in the last phase we introduced some recursive algorithms ( negamax-alphabeta ) to facilitate some proper decision making by the engine. Now in the alpha8 phase we continue on with another recursive algorithm, and also add some positional smarts and improvements to the GUI.

Quiesecent search is a routine that is called at the end of the search tree. It is pretty much like alphaBeta search, except that it evaluates only captures, and it will continue to search until it reaches a position where there are no more captures. This makes it far less likely that the engine will lose material, without taking the time to evaluate all of the possibilities. Move ordering is essential here, as this is the only control on how deep the seaqrch might go.

Piece/square tables are an easy way to add positional smarts to the program. There is not too much to say here, they are just a series of 64 element arrays, one array for each piece, that assign values according to which square the piece occupies. This function is controlled from the evaluate() method of the Engine class.

There are also a few changes to the GUI.

1. An improved piece design. I'm now using externally loaded .png image files with transparent backgrounds. Transparency is dealt with using the alpha component.

2. A single action button, which works hand in hand with a drop-down list that determines which action gets performed. This allows me to add functionality without using more space in the GUI.

3. A checkbox that will invert the board so that black is at the bottom. This was a little tricky, it involves changing the mapping between the xy co-ordinate system that java uses for mouse-events & graphics commands, and the (row,col) co-rdinate system of the chess board (0,0) is a8, (7,7) is h1. The formulas below relate the top left corner of the square in xy co-ordinates to the row column co-ordinates, for a give square size ss...

Normal: row = y/ss; col = x/ss;
Inverted: row = 7-y/ss; col = 7-x/ss;

OK, that's about it for now. Hopefully in the next phase I will introduce some proper chess notation.

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

Have a nice day.

Friday, October 16, 2009

NegaMax with alphaBeta pruning.

In the last post, we completed the process of generating a list of all possible moves, and had the engine choose randomly from the list. Now in the alpha7 phase we add add some algorithms to enable the engine to analyse the position and calculate the best move to play. I won't attempt to explain how negamax and alpha-beta pruning works, there are plenty of websites that explain that. I will make a few general comments. My program currently has the following basic algorithms that are all design to work together.

Negamax ( which is equivalent to MiniMax ), is the standard base recursion algorithm for traversing (searching) game trees. Negamax will examine every possible variation, even obviously bad ones. It can be very slow, because we all know how the number of possible chess moves can grow exponentially.

AlphaBeta pruning is added to the picture to improve the performance of negamax, and it serves this purpose very well. It does so by eliminating from further analysis those variations that, based on best play by both sides, can't possibly change the final decision. Assuming we are searching at a fixed depth, alphaBeta will make the same move as negaMax, only it will do so faster. It follows that if we are playing under time controls, alphaBeta will search deeper than plain negaMax.

MVV/LVA (Most Valuable Victim/Least Valuable Attacker) is a method for ordering the list of possible moves at each node. The effectiveness of AlphaBeta pruning is improved if we can place those moves that are likely to be "best" at the top of the list. Naturally we can only make guesses as to which move is best, but we know that if we evaluate captures first, and furthormore we order the captures according to the MVV/LVA principle, we will significantly improve the speed of alphaBeta search.

An evaluate() function is a must. evaluate() assigns a value to those positions at the end of the search tree (leaf nodes). Negamax/alpha beta provides a means of comparison of values assigned by evaluate(). At this point, my evaluate() only calculates the material balance. This means the program has no strategy, but is very good at tactics. Strategy, in the form of a better evaluate() function, comes later once I have squeezed the most out of my algorithms.

If you wish to learn more about these topics, I can recommend the following website, which was a big help to me. It will help you to better understand my source code.

http://web.archive.org/web/20040403211728/brucemo.com/compchess/programming/index.htm

I have redesigned my GUI to help evaluate the effectiveness of the different features. There is a drop-down list which controls which algorithms will be used. It's all pretty straightforward. Output for each computer move includes the time taken and the # of leaf nodes evaluated. The Better the algorithm, the fewer leaf nodes you need to evaluate.

As always, an updated applet and source code is available on the fchess2 website. If you have any questions, you are welcome to commment in the blog.

Have a nice day.

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.

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.

Wednesday, October 7, 2009

Introducing the concepts of game state and move.

To understand the alpha4 phase requires a strong familiarity with fen positional notation.

First a little housekeeping. I ended up re-writing my Utils class. No new functionality, but I now use HashMaps and TreeMaps for all the mappings between the various co-ordinate systems. This eliminates a whole mess of methods using switch() statements, and leaves us with two primary methods in the Utils class.

toFen( int[] ) - converts an integer based position array to the position field of a fen string. This is called by the toFen instance method of the GameState object.

toArray( String ) - converts the position field of a fen string to an integer based position array. This is called by the constructor of the GameState class in order to build its position array.

Also, the Maps are initialised on start-up via a method call from the Table constructor.

In the last installment, we added the ability to drag and drop the pieces, with no restrictions. Today we have added the following restrictions in the Table class...

1. in the mousePressed method, a boolean condition to prevent either side from moving out of turn.

2. in the mouseReleased method, code to prevent a piece from being dragged off the board. This code checks that the xy co-ordinates of the mouseReleased event fall within the bounds of the board (JPanel)

3. If conditions 1 & 2 are satisfied, then in the mouseReleased method there is a move legality test. Currently this test only prevents a piece being dropped on a square occupied by another piece of the same color.

In support of these developments, we have added four new classed.

GameState - GameState objects encapsulate all of the information needed to describe the current state of the game, including the position.

Game - a class to keep track of all game related issues, such as the current game state, a list of all the moves played( currently unused ). This class will grow significantly over time.

Move - an object to represent a move. Includes source square, destination square (both are indexes of the position array) and the type of piece moved.

MoveList - a class which extends ArrayList, each element contains a move that is played on the board. Currently this class is unused.

Also, one critical method was added to class Utils. This is boolean isLegal( GameState, Move ). This is the aforementioned legality check called from MouseReleased. The next phases of development will revolve around this method, as we attempt to define what constitutes a legal move. This is a complex task, involving the properties of the pieces, defining check, checkmate and stalemate, rights to castle and capture en passant, and other issues.

At this point it is worthwhile to trace the sequence of events when the program is loaded.

The main starting point is a call to the Table constructor from Fchess2, the main container class. Currently the following steps are performed by the constructor...

1. A call to a method which initializes all the HashMaps for the co-ordinate system mappings.
2. A call to build and display the GUI, including an empty chessboard.
3. A call to reset(), passing the starting fen. reset() performs steps 4 - 7.
4. resets various flags and variables
5. passes the fen string to the Game constructor, which in turn passes the fen to the GameState constructor.
6. assign the posn array of game.state to the position array of the board.
7. calls board.repaint() to draw the position denoted by the original fen parameter.

This reset() method is called from two other places...

1. the event handler for the reset button calls reset( startFen );
2. the event handler for the fen button calls reset() passing the fen string pasted by the user into the text field.

OK, that's it for now. As mentioned earlier, the next phase is to define what constitues a legal move. The approach will be to write a method that generates all possible legal moves for a position, then we check to see that the move being attempted by the dragging of pieces exists in the possible moves list.

As always, an updated applet and current source code is available on the fchess2 website.

Tuesday, October 6, 2009

Drag and Drop of chess pieces.

Last time, in the alpha2 phase, we added the ability to create positions on the board by interpreting a fen string pasted by the user. In the alpha3 phase we add the ability to move the pieces using drag and drop. To do this we added variables pieceMoved, xDrag, yDrag, xOffset, yOffset, and a boolean isDrag. We also added bodies to three methods of the table class, as follows.

mousePressed( MouseEvent e ) - When you press on a piece, you pick it up. The position array index is calculated from the xy co-ordinates of the mouse event, the corresponding posn array element is cleared, and the xOffset and yOffset are calculated. These offsets represent the distance of the mouse click from the top left corner of the square being clicked. more on that later. Another key variable is isDrag, which flags the paintComponent method that a piece is beng moved.

mouseDragged( MouseEvent e ) - As the piece is moved, a MouseEvent is generated, the new position of the piece is claculated, and repaint is called to paint the piece in the new position.

mouseReleased( MouseEvent e ) - The piece is dropped on a new square. The appropriate index of the position array is calculated from the xy of the MouseEvent, the array is updated, and paintComponent is called. Later on, the mouseReleased event will be a trigger for all sorts of actions to update game state variabled, and ultimetely to tell the engine that itis it's turn to move. But we're not there yet. All in due time.

We will take a close look at a few of the variables that come into play here...

isDrag - Normally, the paintComponent method of the Board class gets information from the position array to determine where to draw the pieces. But when a piece is being dragged, it is not in the position array. The boolean isDrag tells the paintComponent method that there is a piece not in the array that needs to be painted.

xOffset, yOffset. When a piece is drawn, what is actually being drawn is a square BufferedImage with a transparent background. xOffset and yOffset are constants from the original mousePressed event that started the piece move. They are used to calulate xDrag & yDrag from the xy co-ordinated of the MouseDragged event. xDrag and yDrag become the new top left corner of the BufferedImage, this is what is passed to the graphics drawImage command.

One more thing. At the moment, the entire board and position is redrawn with each incremental movement of a piece being dragged. This is easy to implement, and does not seem to cause any resurce usage problems. At a later date we will look at a more efficient repaint which redrawns only the affected areas of the board.

OK that's it for now. Currently there are no restrictions on how the pieces can be moved. That will entail co-ordinated effort in a number of areas, including internal representation of a move, of the game state, which is more than just the position of the pieces, and also move legality according to the rules of chess. The next few posts will document the effort towards that goal.

As always, the updated alpha3 source code is on the website.

http://sites.google.com/site/fchess2/

Monday, October 5, 2009

piece graphics and internal position array

version alpha2

Now we add functionality for displaying chess positions on the board. Input to the process is in the form of a fen string to be pasted into a JTextField. Then we click on the fen button, and the proper position is displayed on the board. Right now the pieces are kind of crude in appearance, but that will change soon enough.

Anyways, we have a number of new constructs...

The position array is of type int[64], one entry for each square on the board. The choice of int[] is an important one, and will be explained shortly.

A new interface, Pieces, which for now provides both identity and value, as follows:

type   white   black
---------------------
king    1       -1
queen   90     -90
rook    50     -50
bishop  30     -30
knight  29     -29
pawn    10     -10


these integers serve to identify the pieces, and also represent their value. Later, when the engine wants to calculate the material balance, it need only add up the position array. Making all the values a multiple of 10 allows for flexibility in tweking the values based on positional considerations. The Pieces interface will be implemented by any class that needs to know about the pieces. Sticklers will say i should have used an Enum here, maybe I'll switch sometime down the road.

A new class, Utils, which will contain static methods used by all parts of the program. Right now these methods contain methods which support the transformation of a fen position string into the internal position array. At the point we need the means to map back and forth between a few types of notation e.g.

the rank and file algebraic notation of the chess world top left = h8, bottom right = h1, maps to row column array notation (0,0) to (7,7) which maps to single dimension position array notation (0-63), which maps to the xy pixel co-rdinates of the upper left corner of each square on the chessboard.

A number of methods have ben added to the Board class in support of all this activity. The current piece design involves creating blank, transparent BufferedImage objects for each piece type, then associating a graphics context with the image, drawing primitives on this context, then drawing the image to the screen. You might well ask: Why not just draw the primitives directly to the drawing surface? Well the reason is that the way I have described facilitates easy switching between primitive or GeneralPath shapes, and externally created image files. In all cases it is an image we are drawing to the empty chessboard, and thus the paintComponent method is simplified.

Anyways, i have just provided a high level desription of what is going on. If you scrutinize the source code you can work out the actual details yourself.

As always, you have access to the source code and an up to date applet by following the link below.

Have a nice day.

http://sites.google.com/site/fchess2/