Author: Tord Romstad
Date: 04:21:49 01/07/04
Go up one level in this thread
On January 07, 2004 at 05:47:47, Matt Thomas wrote: >I hadn't really reviewed an attack table layout. I read a few things on >bitboards on various web sites and they seemed cool so I decided to use them. >When you mention attack table it makes me think of something like an opening >book that has predefined move responses. Is that a fair assessment or is it >something different? It is something entirely different, I think. If I understand correctly, what I use is an example of what is commonly called attack tables: I have two 256-element arrays of 16-bit unsigned integers, one for each player. The arrays are indexed by the squares of the board (my board has 256 squares). Each entry in the arrays contains information about the number and types of attackers to the corresponding square of the board. The individual bits of each array entry have the following meaning: bits 1-3: The total number of attackers (X-ray attacks and normal attacks) to the given square. bit 4: 1 or 0, depending on whether the square is attacked by a pawn. bit 5: 1 or 0, depending on whether the square is attacked by a knight or bishop. bit 6: 1 or 0, depending on whether the square is attacked by a rook. bit 7: 1 or 0, depending on whether the square is attacked by a queen. bit 8: 1 or 0, depending on whether the square is attacked by a king. In these 8 lower bits, I include X-ray attacks as well as normal attacks. When an X-ray radiates through a more valuable piece, the bit for the less valuable piece is not set in the attack table. In the upper 8 bits, I have information only about the *direct* attacks to the square. Unlike in the lower 8 bits, I distinguish between bishops and knights: bit 9: 1 or 0, depending on whether the square is attacked by a pawn. bit 10: 1 or 0, depending on whether the square is attacked by a knight. bit 11: 1 or 0, depending on whether the square is attacked by a bishop. bit 12: 1 or 0, depending on whether the square is attacked by a rook. bit 13: 1 or 0, depending on whether the square is attacked by a queen. bit 14: 1 or 0, depending on whether the square is attacked by a king. The last two bits are currently unused. The two attack table arrays are computed at all nodes of the tree. This is rather expensive, but you can extract lots of interesting information from them. Some examples: The lower 8 bits are useful for static echange evaluation and similar tasks. I use them to identify hanging pieces and the expected material gain by capturing them, to find the highest-valued piece for each side which can move to a given square, to cull losing captures and checks from my qsearch, and so on. Most of these tasks can be done either by using precomputed tables containing results for all the possible 8-bit vectors, by doing the necessary computations on the fly, or by some hybrid technique which stores the most common computations in a small hash table. Many engines have a mobility component in their evaluation function. They give each side some kind of bonus depending on how many pseudo-legal moves they have. With attack tables, you can do something a bit better: You can choose to count only the number of *safe* pseudo-legal moves for each side. In a similar way, you also get a reasonably accurate and cheap way to evaluate space. For each square of the board, you can decide which side controls the square by a table lookup or a fast and simple computation. Attack tables are also very useful in king safety evaluation. For each square around the king, you have complete information about the number and types of pieces which attack and defend the square. It is also easy to count the number of safe checking moves for the attacking side. I also use my attack tables to detect mate threats in the evaluation function. For instance, if black's king is on the back rank and the square directly in front of it is attacked by at least two white pieces, one of which is a queen, and the square is not defended by any black pieces except the king, I know that white almost certainly has a mate in 1. Most other common mating patterns can be detected in the same way. For some other ideas about what you can do with attack tables, take a look at Ed Schröder's Rebel pages (you will notice that the lower 8 bits of my attack tables look exactly like Ed's tables) or at the excellent open-source engine Phalanx (my favorite open-source engine, in fact). The nice thing about attack tables is that they contain lots of useful information coded in a very compact way. With bitboards, you can easily find a bitboard containing all pieces which attack a given square, but extracting information from this bitboard can be difficult and time-consuming. A 64-bit bitboard is obviously too big to be used as an index to a lookup table, unlike the lower 8 bits of my attack tables. At least in my engine, knowing the number and types of the attackers is usually much more important than knowing their locations. Of course, bitboards and attack tables are not mutually exclusive. It is perfectly possible (perhaps even a good idea) to use bitboards to compute the attack tables. Tord
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.