Author: Sune Fischer
Date: 11:02:16 11/15/02
Go up one level in this thread
On November 15, 2002 at 13:16:37, Bob Durrett wrote: >On November 15, 2002 at 12:30:12, Sune Fischer wrote: > ><snip> > >>>Let me end this with a question: >>> >>>What types of algorithms are implemented in modern chess engines, other than >>>"search algorithms"? >> >>There are three main components in a chess program, generation of moves, search >>of the game tree and evaluation of positions. >> >>Plenty of algorithms go into all phases. >> >>-S. >> >>>Bob D. > >That's useful. Thanks. > >Could you please advance to the next level? > >(1) What are the main components of the "generation of moves"? This is "implementation specific" so to speak, you need a way to describe your position, where the pieces are on the board and if castle is a legal move, information like that. Some use bitboards for this, so they have a small bundle of 64-bit variables that each hold some piece of the needed information, eg. a bitboard for the occupied white pieces and a bitboard for the black knights, etc.. Bitboards based engines can generate the legal moves by computing an attack bitboard for every piece. Then you extract the set bits on the bitboard and this is the to-square. You can do this for all the pieces and all of their respective attack boards and you have a list of the (pseudo) legal moves. There are other ways, like 0x88, where things are done by table lookups. >(2) What are the main components of the "search of the game tree"? The basic algorithm here is the alpha-beta. The idea is to assume the opponent picks the best move he can - always. Then we search for the move which is the best I can do, assuming he will do the best he can do, when he assumes I do the best I can do and so on. Really this is running backwards, from the leafs and up the tree. Alpha-beta is pretty cool because you don't need to search the second move in a position, if the first move you found was so good that you opponent has already found a better alternative down a different branch of the tree. There are lots of cute tricks to speed this up, like a transposition table, where you save results and can reuse them again should the position repeat in the tree. You must also have heard of null move, ie where you try a reduced depth search to see if the position is so good that you can afford not to make a move! If so we must be in rediculous position, very unrealistic and so it's not worth searching. Other kinds of pruning are done so to not waste a lot of time searching deeply down the stupid branches, and extensions to go deeper where you think something interesting is happening (ie finding mates!). A very important thing is the quiesce search, where you try and reach a quiet position. It is important not to do the evaluation on a position full of action, ie. the side not to move has a rook en-prise. Maybe he will lose the rook and be a rook down. It would be extremely hard to figure out this kind of dynamic, the search is better at handling this. >(3) What are the main components of the "evaluation of positions"? This is the "knowledge" part, although I would argue that the extensions and pruning techniques are also knowledge based. You know for example that double pawns are bad, so penalize it for that, reward it for high mobility of a bishop and so on. Finally you end up with a score that you send from the leaf down the search, so the search can see which positions are good for whom. >At some point, I assume this will get into differences between individual chess >engines. Yes, manny manny endless variations on these themes, so engines will be different. I believe there are different roads that lead to the same goal. -S. >Bob D.
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.