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.

2 comments: