Author: scott farrell
Date: 23:06:28 01/19/03
Go up one level in this thread
On January 20, 2003 at 01:10:23, Russell Reagan wrote: >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... That last idea of your sounds outragously good to me. I have a small amount of ordering based on: - MVVLVA + whether it defended or not with a called to isAttacked (being bitboard it is very very fast isAttacked). - moving from enpris squares is good eg. isAttacked(white)&&!isAttacked(Black) - moving to squares that make an enprise piece are bad (opposite of the above) - moving to sqaures that are already atacked are bad - this one is not real smart Overall the above gives a boost of 5-10% in my move ordering over plain MVVLVA. And keeps my move ordering over 90% in most cases. I could make a function like: isAttacked(side,int defender) With your ideas I could make the above faster, and smarter, and add a few new ones. Without do the whole SEE, it can probably detect better when 2 pieces are attacking or defending, and end up with a smarter MVVLVA. Like you said, I need a big bit of paper, and start to try to draw this all up. I'd say the above might be good for another 1% for move ordering, plus maybe a bit faster. Scott
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.