Author: Heiner Marxen
Date: 05:17:35 02/05/02
Go up one level in this thread
On February 04, 2002 at 21:42:49, martin fierz wrote:
>aloha!
Hi!
>my question is related to checkers, but it would be the same in computer chess
>with bitboards:
>
>i represent a board with 4 32-bit ints (checkers has 4 piece types, 32 squares).
>in my evaluation i would like to add some patterns, which crop up every now and
>then.
Looking at your code below, which does not amount to hundreds of instructions,
I would not be bothered, first. Have you profiled your program?
And found this to be a hot spot?
Ok, lets assume such code is needed several times, and we are concerned
about its efficiency...
> let's say, i want to find all positions with the property that a specific
>subset of every bitboard is present:
>p is a position structure with the elements bm, bk, wm, wk for black men, kings
>and their white counterparts.
>
>my program looks like this:
>
>// version I
>if( ((p.bm&pattern.bm)==pattern.bm) &&
> ((p.bm&pattern.bk)==pattern.bk) &&
^^ bk
> ((p.bm&pattern.wm)==pattern.wm) &&
^^ wm
> ((p.bm&pattern.wk)==pattern.wk) )
^^ wk
> eval += value;
Typos like this can be overlooked easily and may stay undetected for a long
time. One more reason to introduce an abstraction (e.g. a macro),
the usage of which avoids to repeatedly write the same thing again,
with increased chances of getting it wrong. E.g.:
#define match1(p,patt,k) (((p).k) == ((patt).k))
#define match4(p,patt,c1,c2,c3,c4) ( match1(p,patt,c1) \
&& match1(p,patt,c2) \
&& match1(p,patt,c3) \
&& match1(p,patt,c4) )
#define match(p,patt) match4(p,patt,bm,bk,wm,wk)
if( match(p,pattern) )
eval += value;
Now you can try different implementations of match(), without changing
your main code. E.g. you can experiment, which of bm,bk,wm and wk should
be tested first.
Inline functions may also work well.
>is this any good? i thought of an alternative, let's say,
>my total pattern consists of 7 stones. so i define the array
>
>// version II
>int seven[8] = {0,0,0,0,0,0,0,1};
>and do
> x = p.bm&pattern.bm | p.bk&pattern.bk | p.wm&pattern.wm | p.wk&pattern.wk;
> eval += value*bitcount(x);
I don't see "seven[]" to be used?!
Anyhow, this one differs from the others semantically, it counts partial
matches, also. This may or may not be a good idea, but should not be
decided by implementation aspects, but rather by functional demand.
>// version III
>or, last alternative:
> x = p.bm&pattern.bm | p.bk&pattern.bk | p.wm&pattern.wm | p.wk&pattern.wk;
> if( x == pattern.bm|pattern.bk|pattern.wm|pattern.wk)
> eval+=value;
>
>any ideas on these? looking at them now, version 3 looks best to me. is there
>any difference on different processors? e.g. version II needs no if, thus no
>branches, and i think different processors have different penalties for branch
>misprediction? or does anybody have a suggestion for a more efficient version to
>solve this? real patterns usually include only 3 bitboards (black men, white
>men, and unoccupied squares).
>
>any thoughts are appreciated :-)
> cheers
> martin
The two important aspects here, which are expensive, are memory fetches
and (conditional) branches. Currently branches are even more expensive
than memory fetches (IMO). Of course, one should measure the alternatives.
That should be done with the real application, and not with a toy program,
since the overall cache usage will be important (in the toy program all
memory fetches will be L1-cache hits and appear to be cheap).
Of course, the tradeoffs may change drastically with another processor.
They may as well change drastically over time... I remember times when
memory fetches were clearly more expensive than branches.
That technology will not come back, but technology will continue to change.
Yet another idea: if you have a lot of such patterns to evaluate, you may
want to build a decision tree, to avoid repeated evaluation of the first
component(s).
Just my 2 cents. Cheers,
Heiner
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.