Author: Ed Schröder
Date: 11:16:44 04/10/04
Go up one level in this thread
On April 10, 2004 at 12:51:28, martin fierz wrote:
>hi ed,
>
>you posted the stuff below a day or two ago, and i have a question about it:
>
>you suggest creating a "translation table" to get an unbroken and continuous
>string of characters and then use this in a switch statement. if i understand
>this right, i'd have to make a rather large first table which does something
>like
>
>material-signature = function(pieces); somewhere in the 0...~4000 range (as far
>as i can see, you need to be able to represent any combination of 1 vs 1 or
>better 2 vs 2 pieces)
>
>X=conversiontable[material-signature] ~ somewhere in the 0...20 range for all
>special cases you want to consider.
>
>then you do switch(X) - now how does the compiler know that the conversiontable
>values are in a single range?? i don't understand how it can possibly know this
>:-(
>
>cheers
> martin
>
>*******************************************************************************
>I think I misread, I thought one of your worry was all the time-consuming
>compares and jumps to go to the relevant parts of eval depending of the material
>on the board. If so, create a 2-dimensional translation table that converts the
>present material to an unbroken and continuous string of characters
>(0,1,2,3,4,5.....) and then use the result with switch-case.
>
>I have such an endgame table with over 30 entries (KPK, KRK, KBNK, KQKR, KNKPP,
>KBKPPP, KRPKR etc.) and instead of doing 30 expensive compares I just have to do
>2 initialization instructions, get the value of the translation table and then
>the switch-case will move me with just one assembler instruction to the right
>place (label). Imagine the speed gain.
>
> switch (val) { case 0 : goto KPK;
> case 1 : goto KRK;
> case 2 : goto KNBK;
> case 3 : goto KQKR;
> ...................
> case 99 : goto whatever;
> }
>
>Again, the compiler will translate this to just *one* instruction, even if you
>have 200 entries and thus save 200 compares.
>
>Ed
>*****************************************************************************
Hi Martin,
Let me give you some example code (by head) for fast end-game type
identification.
In eval you maintain 2 vars representing the white and black material, "wm" and
"bm".
wm (bit 0-2) no of white pawns
wm (bit 3-4) no of white knights
wm (bit 5-6) no of white bishops
wm (bit 7-8) no of white rooks
wm (bit 9-10) no of white queens
You also can do the above in make_move incremently, which is faster.
Now create 2 translation tables for white and black (called wtt and btt) with
all the 2048 combinations with the following meanings:
value < 0 // no endgame
value >=0 // pointer to a decision table (dt)
So with 2 instructions you filter out all the material combinations you don't
have code for.
if (wtt[wm]<0 || btt[bm]<0) -> no endgame stuff
Then the "dt" decision table, it contains the final conversion to the range
(0,1,2,3,4,5.....) for the switch-case statement, meaning you get the following
final code:
if (wtt[wm]<0 || btt[bm]<0) goto no; // no endgame stuff
x=wtt[wm]+btt[wm]]; // entry to "dt"
if (x<0) goto no; // no valid combination
switch (dt[x]) { case 0 : goto KPK;
case 1 : goto KRK;
case 2 : goto KNBK;
case 3 : goto KQKR;
...................
case 99 : goto whatever;
}
The trick is that by adding the "wtt" and "btt" pointers you end-up in a valid
(>=0) or non valid entry (<0) of the "dt" (decision) table.
It is a lot of work and a very precise job to create the "wtt" and "btt" tables
with the right values (pointers) but is worth all the trouble because the
compiler translates the whole switch-case statement into 1 jump. Actually what
the compiler does is something like this:
goto dt[x];
Isn't life wonderful?
Ed
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.