Author: Tom Likens
Date: 09:54:02 11/17/02
Go up one level in this thread
On November 17, 2002 at 09:31:07, Bob Durrett wrote: > >Recently, I expressed my perception/impression that chess engines were all very >similar. But some people said that wasn't so. > >Now, I am interested in move generators. I would like to know, for my own >education, whether or not most people use the same basic ideas in producing >their own move generators. Are the move generators in common usage all very >similar? > >Are there just a few different kinds of good move generators? Or, are there as >many different kinds of good move generators as there are chess engine >programmers? > >Which, of the different kinds of move generators are best suited for use in >chess engines? Are there several different kinds of move generators which all >do well in chess engines? > >Also interested in knowing how critical the move generator is to a chess engine. > In other words, if the move generator used is inefficient or somehow not right, >would that mean that the chess engine would never be any good? > >Thanks in advance, > >Bob D. Bob, Most engines generate psuedo-legal moves (i.e. moves that may or may not place their own king in check). Some of course, like movei, generate only legal moves so both methods work. The other distinction you'll hear about are incremental move generators. They generate only a few (or one) moves each time hoping to take advantage of an alpha- beta cutoff, which could save them (hopefully) a large amount of move generation work. Here are the main methods I'm aware of (this list may not be complete, but hey the price is right). 1. Mailbox offset This is usually the first method someone thinks of when they first start trying to program a computer to play chess. It typically involves a 12x12 data array with the outer two edges filled with a "magic" boundary value. The moves for the pieces are generated by adding a piece-specific offset to the location of the piece. The edge boundary is two deep instead of only one so that knight moves off the board can be detected. There are numerous ways to optimize this, but IMHO there are better methods so they are not worth pursuing. 2. Table-driven In this method all the possible moves for every piece from every square are pre-computed when the program is initialized. To generate a move you iterate through the moves for each piece and their location, saving the moves that seem legal (i.e. don't capture your own piece etc.) It is fast, but memory intensive. Gnuchess 4 is a good example of this type of move generator. And there is a good write up of the gnu method included in its documentation. It's rumored that Ferret (the *very* good chess engine written by Bruce Moreland) uses a derivative of the gnu generator with a large number of clever enhancements and improvements. HiTech was another famous program that used a table-driven move generator (although it was different from the gnu method). 3. 0x88 This is a rather clever method of move generation that tries to optimize the inner loop of the move generator. This method uses a 16x8 array to represent the board. Only the left portion of the board is utilized. This method exploits the "magic" of twos- complement arithematic to simplify detecting the edge of the board. By ANDing the index of a piece (or any potential square it would like to move to) with 0x88 it is trivial to determine if the square is off the board. If this expression is non-zero then you've run off the board- very clean and quick. Of course, the advantages don't stop there. Another benefit of this method is that the squares have unique mathematical relationships to each other that can be exploited to perform, among other things, fast in-check evaluation. Many commercial and amateur programs use this method, it's easy to understand, easy to code, cache friendly and fast. 4. Bitboard Bitboards are the latest rage because the are used by Crafty and they are fairly elegant once you get mind wrapped around them. They were invented, to the best of my knowledge, by the Chess 4.x crew and the Kaissa programmers roughly at about the same time. They take advantage of the fact that modern computers use a word length of 32-bits which is exactly half of the 64 squares of a chess board (serendipity if I ever saw it ;) The new 64-bit machines will be even better. Data about the board can be represented by setting a bit in a bitboard (i.e. the bitboard containing the location of all the white pieces would have a bit set corresponding to each square a white piece resided on). The real advantage of this method is that it is exceedingly easy to extract information out of these bitboards using basic (i.e. *fast*) AND, OR, XOR operations. For example, to obtain all the pieces a white knight on E5 would attack we could or the pre- computed knight attack from E5 with the bitboard containing the location of all the black pieces. The resultant bitboard would*only* have bits set that corresponded to captures. The down side of bitboards is that they (some claim) are not as efficient on 32-bit machines. This may or may not be true, since a lot of clever things can be done to speed them up. ****** There are probably other methods that I've missed or forgotten. You'll more than likely find that your move generator will be based around the basic data structures you employ in your engine. Whatever method you pick, you should probably stick with it for a while since it take a decent committment to wring the most performance out of these various techniques. Another interesting item you'll note, is that as your engine matures the move generator will begin to take less and less of the overall execution time. So making it correct, rather than fast, should probably be an equal priority. Look into the "epdenum" command in crafty. It will give you counts of *all* the legal moves in a variety of positions. You can use this to verify that your move generator is correct. regards, --tom
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.