[Coladam] Chess openings book reader almost done.
newcoleco at yahoo.fr
Tue Jul 27 01:00:55 CEST 2010
I was working on some codes to deal with the openings book I'm planning to do for my chess program. After thinking a lot, I finaly decided to deal with a tree-like structure with the possiblity of some branches merging for optimization purpose (to avoid encoding twice same sequences of possible end-moves between variations).
The way I entend to use the openings book is to always respond with the best move possible, which is the first one listed in the data structure. so I don't need to encode all possible openings variations, but still need to encode them all in order to always give a good challenge by playing the strongest moves. If the computer starts (playing white), a random function is used to select one of the 4 best first moves, which should help to get a few variations in the gameplay, otherwise the openings book is used in sush a way that the first entry is always the best one to play. So, if the player don't play the first listed move, it's not a problem because these variations are listed too and all made in a way that whatever who plays white the strongest move is the first in each list (or node in the tree-like structure if you prefer).
The tree structure can be see as a list of potential moves that branch to sub-lists, ans so on, up to a certain point where the AI should start making decisions.
In each (sub-)list of moves in the openings book, the first entry is always the best move possible based on statistics of real games of chess played during years (see previous message about openings and database); so, my routine for the CPU is to always play the first entry of the (sub-)list and be ready for the next move. This way, the list of needed openings is reduced and can be optimized in a way to play a lot of moves within the opening part of the game.
I've used my strategy of reading data bit per bit to encode a lot of moves in the openings book whatever its final size. My first estimation is 5000 moves within 8KB (which is 2000 more than Chess Challenger CC10 for the same size).
I've coded already the openings book reader in assembly codes. It supposed to deal with the tree-like structure, but it's not tested yet.
I still need a way to encode the openings into my defined format, dealing with a list of possible openings, set them into tree-like structure and encode the resulting data into bits. Not an easy task, but I suppose I can code something in Java to help me make a first small openings book for testing purpose.
I've commented all the routines done so far for this project.
And for those waiting for a ROM file... well, I need to do at least 2 things before even considering making a first ROM file. 1 - Drawing graphics, 2 - Dealing with player entries ( joystick + validate moves ). So, it's not for tomorow.
That's all for now!
More information about the Coladam