Author: Russell Reagan
Date: 22:10:23 01/19/03
Go up one level in this thread
On January 20, 2003 at 00:15:31, Scott Gasch wrote: >Hi all, > >I'm pondering a major code overhaul of the engine to implement some ideas I've >been thinking about for a while. One of these is attack tables. So I wanted to >seek the advice of those of you who have attack tables in your engines already. > >First, I assume attack tables are things you want to do incrementally. This >seems really expensive though -- not only do you have to update the squares >attacked by the moving piece but also you have to look for attacks exposed by >the vacated square and attacks blocked by the destination square. I'm not >missing any more clever way to handle this incrementally am I? > >Next, on Ed's page he talks a little about attack tables in Rebel. He said he >generates them non-incrementally (in eval from scratch) and he says he only uses >a few bits per side. Like a single P, N, B, R, Q, K bit and a count. I wonder >why not burn a few extra bits and have P, P, N, N, B, R, R, Q, K (10 total): it >would make the square control lookup table much more accurate and not too big (I >get 1M entries)? > >Any feedback / advice appreciated. >Scott I haven't implemented attack tables (at least not in 0x88 or array based board representations), but I have wondered some of the same things you ask. I got the (possibly incorrect) impression that Ed generated the attack tables at every node and used them to improve move ordering by finding winning captures and losing captures (and probably other things). He said earlier that he sorts "winning captures" pretty high in his move ordering. I don't remember if I read that he uses the attack tables for detecting that, or if I just assumed that is how he detected "winning captures". Maybe he can comment. As for your table idea, I too have done some thinking about this, because Ed's implementation will work *most* of the time, but sometimes not (like in a crazy position where you have tons of pieces attacking a single square, you could get erroneous results). This is another reason why I assumed that he only used this for move ordering (and hince at every node), because if you get a bad result back, it doesn't mean you evaluate a position wrong by several pawns worth (or more), but only that your move ordering isn't optimal, which isn't great, but also isn't fatal. Anyway, about your idea to use 10 bits, I don't think we're talking about 1MB, because Ed's 8-bit approach is close to 1MB already. Ed's is a 12 x 256 x 256 array, which comes out to 786,432 elements at one byte each. I calculate 12 x 1024 x 1024 which comes out to 12,582,912 bytes using 10-bit keys. So you're talking about 12 MB of space, which is ok except for the cache unfriendliness of it. At least with Ed's approach you can store a good chunk of it in the cache if needed. I have also fiddled around with (on paper) an idea to use an algorithm to work on the attack data that you compute, rather than using a lookup table. A memory access will take maybe up to 100 cycles, so if you can do something to compute that data on the fly in under that many cycles (or close to it) it might work just as well. A lot of the time you should be able to compute the result pretty quick. For instance, if you have a piece of greater value than a pawn, and it is attacked by an enemy pawn, you can expect that it is not a good idea to move that piece there (or leave it there, or whatever you are computing). So in trying to determine if a move is bad, you can take the value of the piece (say, 3 for a knight), and then find the LVA from the bits that you computed (the same bits you would have used in the lookup table), and if it's a pawn (value 1), that move is a move that loses material. You could develop some sort of on the fly qsearch based on the values of the defenders, values of the attackers, and the value of the piece on the square in question. Basically this seems to be turning into a SSE. Just some thoughts...
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.