Bitboard Representation

[Carl Tillotson]

Is bitboard representation be the most logical choice when representing the
Chessboard and for further evalutation. ?

How is an the evaluation technique "fine-tuned", is it a case of placing a
number of specific weights whilst searching the tree.

Apologies, if I am sounding a little dumb, I am just trying to get a few
"buzz words" right in my head :-)

I seem to be stuck with the view that the bitboard representation is good for
seeing threats that are "close" but how does one go about "programming" such
things a deflection and x-ray attacks - particularly if for example the first
search indicates losing a Knight. I just can't think out a clear evaluation
technique which is not purely "materialistic".

Can someone point me in the direction of any useful "published" material on
the Internet. I have already visited the UCI site, and found David Eppstein's
lecture material very useful (BTW Does David contribute to this group ?)

I am not thinking of a "program" that is all powerful and can beat the shit
out of everyone, I am trying to get to one where the program learns with the
opponent. One where it starts knowing bugger all, but then builds up it's
intelligence by learning from the player. The aim is to arrive at a program,
that will always be a little stronger than the player, but as the player
improves, the program itself plays a little better also. Am I dreaming ?

I would have thought, it should be possible to implement a sophisticated
"learning function", maybe this is a pipe dream !

Carlos
******
Email Reply : Change "carl.tillotson" to "lca"
Lancashire Chess Association Homepage
http://www.netcomuk.co.uk/~lca/index.htm

Message Written Offline with Virtual Access 4.0 Wed, 17 Sep 1997 22:42 +0100

[Robert Hyatt]

Carl Tillotson (carl.ti...@netcomuk.co.uk) wrote:

: Is bitboard representation be the most logical choice when representing the

: Chessboard and for further evalutation. ?

really impossible to answer. bitmaps work fine. so do other representations
of the board. bitmaps make some things easier, while others are harder. So
I wouldn't say they are an overwhelming advantage or disadvantage at present.
64bit architectures do like them better, and the performance of such programs
tends to gain significantly on 64 bit machines, while normal programs don't
because they really don't need to pump 64 bits around...

: How is an the evaluation technique "fine-tuned", is it a case of placing a

: number of specific weights whilst searching the tree.

yes... basically asking "is this piece good on this square and how good
or bad is it"... but it does get more complicated when you start figuring
out how pieces coordinate and so forth...

: Apologies, if I am sounding a little dumb, I am just trying to get a few

: "buzz words" right in my head :-)

: I seem to be stuck with the view that the bitboard representation is good for
: seeing threats that are "close" but how does one go about "programming" such
: things a deflection and x-ray attacks - particularly if for example the first
: search indicates losing a Knight. I just can't think out a clear evaluation
: technique which is not purely "materialistic".

you are mixing two ideas. the search itself is independent of whether
you use bitmaps or something else. In fact, anything you can do with a
non-bitmap approach, I can do with a bitmap approach, and vice-versa. I
can do some things much more efficiently with them, but in general it is
probably a break-even deal.

: Can someone point me in the direction of any useful "published" material on

: the Internet. I have already visited the UCI site, and found David Eppstein's
: lecture material very useful (BTW Does David contribute to this group ?)

: I am not thinking of a "program" that is all powerful and can beat the shit
: out of everyone, I am trying to get to one where the program learns with the
: opponent. One where it starts knowing bugger all, but then builds up it's
: intelligence by learning from the player. The aim is to arrive at a program,
: that will always be a little stronger than the player, but as the player
: improves, the program itself plays a little better also. Am I dreaming ?

: I would have thought, it should be possible to implement a sophisticated
: "learning function", maybe this is a pipe dream !

there are a couple that are working on this. knightcap is one such
program. there are others. but learning is still in its infancy...

[Carl Tillotson]

<snip - a lot of useful comments>

Thanks Robert !

Carlos
******
Email Reply : Change "carl.tillotson" to "lca"
Lancashire Chess Association Homepage
http://www.netcomuk.co.uk/~lca/index.htm

Message Written Offline with Virtual Access 4.0 Thu, 18 Sep 1997 23:39 +0100

[Carl Tillotson]

[Komputer Korner]

Bob, there is one thing that you forgot that bitmaps cannot do. That is
provide a completely mirrored score evaluation.
--
- -
Komputer Korner

The inkompetent komputer

If you see a 1 in my email address, take it out before replying.
Please do not email both me and the r.g.c.c. at the same time. I read all
the postings on r.g.c.c.

Robert Hyatt <hy...@crafty.cis.uab.edu> wrote in article
<5vs32e$c...@juniper.cis.uab.edu>...

> Carl Tillotson (carl.ti...@netcomuk.co.uk) wrote:
>
> : Is bitboard representation be the most logical choice when representing
the
> : Chessboard and for further evalutation. ?
>

[Robert Hyatt]

Komputer Korner (kor...@netcom.ca) wrote:

: Bob, there is one thing that you forgot that bitmaps cannot do. That is

: provide a completely mirrored score evaluation.

: >

A mirrored score is easy, and I have one. The problem is a "mirrored"
search. IE if you set up a position with white to move and have Crafty
search that position, to a fixed depth, you will search N nodes. If you
reverse the colors, and set up the same position, but from the black side
of the board, and do the same search, you will search M nodes where
M != N, because move ordering will change a little. In theory, this
should not affect the search outcome at all. In practice, due to the
transposition table it does.

[Robert Hyatt]

Robert Hyatt (hy...@crafty.cis.uab.edu) wrote:
: Komputer Korner (kor...@netcom.ca) wrote:

Here is a sample to show what this means. I am setting up the position
"fine #70" first with WTM, then I am simply mirroring this about the
X-axis so that a1 becomes a8 and a8 becomes a1, and then flipping the
color of all the pieces. Here are the board diagrams, first:

+---+---+---+---+---+---+---+---+
8 | | | | | | | | |
+---+---+---+---+---+---+---+---+
7 | *K| | | | | | | |
+---+---+---+---+---+---+---+---+
6 | | | | *P| | | | |
+---+---+---+---+---+---+---+---+
5 | *P| | | P | | *P| | |
+---+---+---+---+---+---+---+---+
4 | P | | | P | | P | | |
+---+---+---+---+---+---+---+---+
3 | | | | | | | | |
+---+---+---+---+---+---+---+---+
2 | | | | | | | | |
+---+---+---+---+---+---+---+---+
1 | K | | | | | | | |
+---+---+---+---+---+---+---+---+
a b c d e f g h

White(1):

and

+---+---+---+---+---+---+---+---+
8 | *K| | | | | | | |
+---+---+---+---+---+---+---+---+
7 | | | | | | | | |
+---+---+---+---+---+---+---+---+
6 | | | | | | | | |
+---+---+---+---+---+---+---+---+
5 | *P| | | *P| | *P| | |
+---+---+---+---+---+---+---+---+
4 | P | | | *P| | P | | |
+---+---+---+---+---+---+---+---+
3 | | | | P | | | | |
+---+---+---+---+---+---+---+---+
2 | K | | | | | | | |
+---+---+---+---+---+---+---+---+
1 | | | | | | | | |
+---+---+---+---+---+---+---+---+
a b c d e f g h

Black(1):

next, for each position, I asked crafty to simply
give me the static eval for the position. I did this
from both side's perspective: for normal fine70:

wtm:
note: scores are for the white side
material evaluation................. 0.800
development......................... 0.000
pawn evaluation..................... -0.359
passed pawn evaluation.............. 0.000
passed pawn race evaluation......... 0.000
outside passed pawn evaluation...... 0.000
piece evaluation.................... -0.100
total evaluation.................... 0.341
White(1):

btm
note: scores are for the white side
material evaluation................. -0.800
development......................... 0.000
pawn evaluation..................... 0.359
passed pawn evaluation.............. 0.000
passed pawn race evaluation......... 0.000
outside passed pawn evaluation...... 0.000
piece evaluation.................... 0.100
total evaluation.................... -0.341
Black(1):

ok so far. scores mirror for both positions. In the first case, white
is up a pawn, and is better. in the second case, black is up a pawn and
is better by the same amount. symmetry so far...

now a 5 ply search for this position, first for wtm, then for btm:

depth time score variation (1)
1 0.00 0.916 Kb2
1-> 0.00 0.916 Kb2
2 0.00 0.716 Kb2 Kb6
2-> 0.00 0.716 Kb2 Kb6
3 0.00 0.916 Kb2 Kb6 Kc3
3-> 0.01 0.916 Kb2 Kb6 Kc3
4 0.01 0.916 Kb2 Kb6 Kc3 Kc7
4-> 0.01 0.916 Kb2 Kb6 Kc3 Kc7
5 0.01 1.016 Kb2 Kb6 Kc3 Kc7 Kc4
5-> 0.01 1.016 Kb2 Kb6 Kc3 Kc7 Kc4
time: 0.01 cpu:100% mat:1 n:228 nps:10000
ext-> checks:0 recaps:0 pawns:0 1rep:0
predicted:0 nodes:228 evals:183
endgame tablebase-> probes done: 0 successful: 0

depth time score variation (1)
1 0.00 0.916 Kb7
1-> 0.00 0.916 Kb7
2 0.00 0.716 Kb7 Kb3
2-> 0.00 0.716 Kb7 Kb3
3 0.00 0.916 Kb7 Kb3 Kc6
3-> 0.00 0.916 Kb7 Kb3 Kc6
4 0.00 0.916 Kb7 Kb3 Kc6 Kc2
4-> 0.00 0.916 Kb7 Kb3 Kc6 Kc2
5 0.01 1.016 Kb7 Kb3 Kc6 Kc2 Kc5
5-> 0.01 1.016 Kb7 Kb3 Kc6 Kc2 Kc5
time: 0.01 cpu:100% mat:1 n:228 nps:10000
ext-> checks:0 recaps:0 pawns:0 1rep:0
predicted:0 nodes:228 evals:183
endgame tablebase-> probes done: 0 successful: 0

ok so far. node counts are the same, evals are the same. on to 10
plies:

depth time score variation (1)
1 0.00 0.916 Kb2
1-> 0.00 0.916 Kb2
2 0.00 0.716 Kb2 Kb6
2-> 0.00 0.716 Kb2 Kb6
3 0.00 0.916 Kb2 Kb6 Kc3
3-> 0.00 0.916 Kb2 Kb6 Kc3
4 0.00 0.916 Kb2 Kb6 Kc3 Kc7
4-> 0.00 0.916 Kb2 Kb6 Kc3 Kc7
5 0.00 1.016 Kb2 Kb6 Kc3 Kc7 Kc4
5-> 0.00 1.016 Kb2 Kb6 Kc3 Kc7 Kc4
6 0.00 1.016 Kb2 Kb6 Kc3 Kc7 Kc4 Kb6
6-> 0.00 1.016 Kb2 Kb6 Kc3 Kc7 Kc4 Kb6
7 0.01 1.016 Kb2 Kb6 Kc3 Kc7 Kc4 Kb6 Kd3
7-> 0.01 1.016 Kb2 Kb6 Kc3 Kc7 Kc4 Kb6 Kd3
8 0.01 1.016 Kb2 Kb6 Kc3 Kc7 Kc4 Kb6 Kd3 Kc7
8-> 0.01 1.016 Kb2 Kb6 Kc3 Kc7 Kc4 Kb6 Kd3 Kc7
9 0.01 1.016 Kb2 Kb6 Kc3 Kc7 Kc4 Kb6 Kd3 Kc7 Kc4
9-> 0.01 1.016 Kb2 Kb6 Kc3 Kc7 Kc4 Kb6 Kd3 Kc7 Kc4
10 0.02 1.016 Kb2 Kb6 Kc3 Kc7 Kc4 Kb6 Kd3 Kc7 Ke3
Kb6
10-> 0.02 1.016 Kb2 Kb6 Kc3 Kc7 Kc4 Kb6 Kd3 Kc7 Ke3
Kb6
time: 0.02 cpu:100% mat:1 n:1681 nps:10000
ext-> checks:0 recaps:0 pawns:0 1rep:6
predicted:0 nodes:1681 evals:723
endgame tablebase-> probes done: 0 successful: 0
depth time score variation (1)
1 0.00 0.916 Kb7
1-> 0.00 0.916 Kb7
2 0.00 0.716 Kb7 Kb3
2-> 0.00 0.716 Kb7 Kb3
3 0.00 0.916 Kb7 Kb3 Kc6
3-> 0.00 0.916 Kb7 Kb3 Kc6
4 0.00 0.916 Kb7 Kb3 Kc6 Kc2
4-> 0.00 0.916 Kb7 Kb3 Kc6 Kc2
5 0.00 1.016 Kb7 Kb3 Kc6 Kc2 Kc5
5-> 0.00 1.016 Kb7 Kb3 Kc6 Kc2 Kc5
6 0.00 1.016 Kb7 Kb3 Kc6 Kc2 Kc5 Kb3
6-> 0.00 1.016 Kb7 Kb3 Kc6 Kc2 Kc5 Kb3
7 0.01 1.016 Kb7 Kb3 Kc6 Kc2 Kc5 Kb3 Kd6
7-> 0.01 1.016 Kb7 Kb3 Kc6 Kc2 Kc5 Kb3 Kd6
8 0.01 1.016 Kb7 Kb3 Kc6 Kc2 Kc5 Kb3 Kd6 Kc2
8-> 0.01 1.016 Kb7 Kb3 Kc6 Kc2 Kc5 Kb3 Kd6 Kc2
9 0.01 1.016 Kb7 Kb3 Kc6 Kc2 Kc5 Kb3 Kd6 Kc2 Kc5
9-> 0.01 1.016 Kb7 Kb3 Kc6 Kc2 Kc5 Kb3 Kd6 Kc2 Kc5
10 0.02 1.016 Kb7 Kb3 Kc6 Kc2 Kc5 Kb3 Kd6 Kc2 Ke6
Kb3
10-> 0.02 1.016 Kb7 Kb3 Kc6 Kc2 Kc5 Kb3 Kd6 Kc2 Ke6
Kb3
time: 0.02 cpu:100% mat:1 n:1693 nps:10000
ext-> checks:0 recaps:0 pawns:0 1rep:6
predicted:0 nodes:1693 evals:737
endgame tablebase-> probes done: 0 successful: 0

scores are the same, but notice the node counts are slightly different.

next comes ply=15:
depth time score variation (1)
1 0.00 0.916 Kb2
1-> 0.01 0.916 Kb2
2 0.01 0.716 Kb2 Kb6
2-> 0.01 0.716 Kb2 Kb6
3 0.01 0.916 Kb2 Kb6 Kc3
3-> 0.01 0.916 Kb2 Kb6 Kc3
4 0.01 0.916 Kb2 Kb6 Kc3 Kc7
4-> 0.01 0.916 Kb2 Kb6 Kc3 Kc7
5 0.01 1.016 Kb2 Kb6 Kc3 Kc7 Kc4
5-> 0.01 1.016 Kb2 Kb6 Kc3 Kc7 Kc4
6 0.06 1.016 Kb2 Kb6 Kc3 Kc7 Kc4 Kb6
6-> 0.06 1.016 Kb2 Kb6 Kc3 Kc7 Kc4 Kb6
7 0.06 1.016 Kb2 Kb6 Kc3 Kc7 Kc4 Kb6 Kd3
7-> 0.06 1.016 Kb2 Kb6 Kc3 Kc7 Kc4 Kb6 Kd3
8 0.06 1.016 Kb2 Kb6 Kc3 Kc7 Kc4 Kb6 Kd3 Kc7
8-> 0.06 1.016 Kb2 Kb6 Kc3 Kc7 Kc4 Kb6 Kd3 Kc7
9 0.06 1.016 Kb2 Kb6 Kc3 Kc7 Kc4 Kb6 Kd3 Kc7 Kc4
9-> 0.07 1.016 Kb2 Kb6 Kc3 Kc7 Kc4 Kb6 Kd3 Kc7 Kc4
10 0.07 1.016 Kb2 Kb6 Kc3 Kc7 Kc4 Kb6 Kd3 Kc7 Ke3
Kb6
10-> 0.07 1.016 Kb2 Kb6 Kc3 Kc7 Kc4 Kb6 Kd3 Kc7 Ke3
Kb6
11 0.07 1.016 Kb2 Kb6 Kc3 Kc7 Kc4 Kb6 Kd3 Kc7 Ke3
Kb6 Kd3
11-> 0.08 1.016 Kb2 Kb6 Kc3 Kc7 Kc4 Kb6 Kd3 Kc7 Ke3
Kb6 Kd3
12 0.08 1.016 Kb2 Kb6 Kc3 Kc7 Kc4 Kb6 Kd3 Kc7 Kc3
Kb6 Kc4 Kc7
12-> 0.08 1.016 Kb2 Kb6 Kc3 Kc7 Kc4 Kb6 Kd3 Kc7 Kc3
Kb6 Kc4 Kc7
13 0.09 1.016 Kb2 Kb6 Kc3 Kc7 Kc4 Kb6 Kd3 Kc7 Kc3
Kb6 Kc4 Kc7 Kd3
13-> 0.09 1.016 Kb2 Kb6 Kc3 Kc7 Kc4 Kb6 Kd3 Kc7 Kc3
Kb6 Kc4 Kc7 Kd3
14 0.11 1.016 Kb2 Kb6 Kc3 Kc7 Kb3 Kb6 Kc4 Ka6 Kd3
Kb6 Kd2 Kc7 Kd3 Kb6
14-> 0.11 1.016 Kb2 Kb6 Kc3 Kc7 Kb3 Kb6 Kc4 Ka6 Kd3
Kb6 Kd2 Kc7 Kd3 Kb6
15 0.12 1.016 Kb2 Kb6 Kc3 Kc7 Kb3 Kb6 Kc4 Ka6 Kd3
Kb6 Ke3 Kc7 Ke2 Kd7 Kd3
15-> 0.12 1.016 Kb2 Kb6 Kc3 Kc7 Kb3 Kb6 Kc4 Ka6 Kd3
Kb6 Ke3 Kc7 Ke2 Kd7 Kd3
time: 0.12 cpu:58% mat:1 n:6897 nps:10000
ext-> checks:0 recaps:0 pawns:0 1rep:16
predicted:0 nodes:6897 evals:1721
endgame tablebase-> probes done: 0 successful: 0

depth time score variation (1)
1 0.00 0.916 Kb7
1-> 0.00 0.916 Kb7
2 0.00 0.716 Kb7 Kb3
2-> 0.00 0.716 Kb7 Kb3
3 0.00 0.916 Kb7 Kb3 Kc6
3-> 0.00 0.916 Kb7 Kb3 Kc6
4 0.00 0.916 Kb7 Kb3 Kc6 Kc2
4-> 0.00 0.916 Kb7 Kb3 Kc6 Kc2
5 0.00 1.016 Kb7 Kb3 Kc6 Kc2 Kc5
5-> 0.00 1.016 Kb7 Kb3 Kc6 Kc2 Kc5
6 0.01 1.016 Kb7 Kb3 Kc6 Kc2 Kc5 Kb3
6-> 0.01 1.016 Kb7 Kb3 Kc6 Kc2 Kc5 Kb3
7 0.01 1.016 Kb7 Kb3 Kc6 Kc2 Kc5 Kb3 Kd6
7-> 0.01 1.016 Kb7 Kb3 Kc6 Kc2 Kc5 Kb3 Kd6
8 0.01 1.016 Kb7 Kb3 Kc6 Kc2 Kc5 Kb3 Kd6 Kc2
8-> 0.01 1.016 Kb7 Kb3 Kc6 Kc2 Kc5 Kb3 Kd6 Kc2
9 0.01 1.016 Kb7 Kb3 Kc6 Kc2 Kc5 Kb3 Kd6 Kc2 Kc5
9-> 0.02 1.016 Kb7 Kb3 Kc6 Kc2 Kc5 Kb3 Kd6 Kc2 Kc5
10 0.02 1.016 Kb7 Kb3 Kc6 Kc2 Kc5 Kb3 Kd6 Kc2 Ke6
Kb3
10-> 0.02 1.016 Kb7 Kb3 Kc6 Kc2 Kc5 Kb3 Kd6 Kc2 Ke6
Kb3
11 0.02 1.016 Kb7 Kb3 Kc6 Kc2 Kc5 Kb3 Kd6 Kc2 Ke6
Kb3 Kd6
11-> 0.03 1.016 Kb7 Kb3 Kc6 Kc2 Kc5 Kb3 Kd6 Kc2 Ke6
Kb3 Kd6
12 0.03 1.016 Kb7 Kb3 Kc6 Kc2 Kc5 Kb3 Kd6 Kc2 Kc6
Kb3 Kc5 Kc2
12-> 0.03 1.016 Kb7 Kb3 Kc6 Kc2 Kc5 Kb3 Kd6 Kc2 Kc6
Kb3 Kc5 Kc2
13 0.04 1.016 Kb7 Kb3 Kc6 Kc2 Kc5 Kb3 Kd6 Kc2 Kc6
Kb3 Kc5 Kc2 Kd6
13-> 0.04 1.016 Kb7 Kb3 Kc6 Kc2 Kc5 Kb3 Kd6 Kc2 Kc6
Kb3 Kc5 Kc2 Kd6
14 0.07 0.916 Kb7 Kb1 Kc6 Kb2 Kc5 Kb3 Kd6 Kc2 <HT>
14-> 0.07 0.916 Kb7 Kb1 Kc6 Kb2 Kc5 Kb3 Kd6 Kc2 <HT>
15 0.08 0.916 Kb7 Kb1 Kc6 Kb2 Kc5 Kb3 Kd6 Kc2 Kc5
Kb3 <HT>
15-> 0.08 0.916 Kb7 Kb1 Kc6 Kb2 Kc5 Kb3 Kd6 Kc2 Kc5
Kb3 <HT>
time: 0.08 cpu:100% mat:1 n:8783 nps:10000
ext-> checks:0 recaps:0 pawns:0 1rep:20
predicted:0 nodes:8783 evals:2221
endgame tablebase-> probes done: 0 successful: 0

scores still the same, but nodes are a little more separated due
to move ordering.

depth=20: (I am going to only show the last few plies of each
output from here on as they are getting long)

16 0.09 0.916 Kb2 Kb6 Kc3 Kc7 Kb3 Kb6 Kc4 Ka6 Kd3
Kb6 Ke3 Kc7 Ke2 Kd7 Kd2 Kc8 Ke3 Kd8
Kd3 Kc7 <HT>
16-> 0.09 0.916 Kb2 Kb6 Kc3 Kc7 Kb3 Kb6 Kc4 Ka6 Kd3
Kb6 Ke3 Kc7 Ke2 Kd7 Kd2 Kc8 Ke3 Kd8
Kd3 Kc7 <HT>
17 0.21 1.016 Kb2 Kb6 Kc3 Kc7 Kb3 Kb6 Kc4 Ka6 Kd3
Kb6 Ke3 Kc7 Ke2 Kd7 Kd2 Ke7 Ke3
17-> 0.21 1.016 Kb2 Kb6 Kc3 Kc7 Kb3 Kb6 Kc4 Ka6 Kd3
Kb6 Ke3 Kc7 Ke2 Kd7 Kd2 Ke7 Ke3
18 0.37 0.816 Kb2 Ka8 Kc3 Kb7 Kc4 <HT>
18-> 0.41 0.816 Kb2 Ka8 Kc3 Kb7 Kc4 <HT>
19 0.44 0.916 Kb2 Ka8 Kc3 Kb7 Kc4 Kb6 Kd3 Kc7 Ke3
Kd7 Ke2 Kd8 Kf3 Ke7 Kg3 Kf7 Kf2 Kf6
Ke3
19-> 0.44 0.916 Kb2 Ka8 Kc3 Kb7 Kc4 Kb6 Kd3 Kc7 Ke3
Kd7 Ke2 Kd8 Kf3 Ke7 Kg3 Kf7 Kf2 Kf6
Ke3
20 0.47 0.816 Kb2 Ka8 Kc3 Kb7 Kc4 Kb6 Kd3 Kc7 Ke3
Kd7 Ke2 Kd8 Kf3 Ke7 Kg3 Kf6 Kf2 Ke7
Kf3 Kf6
20 0.61 0.916 Kb1 Kb7 Kc1 Kc7 Kd1 Kd8 Kc2 Kc8 Kd2
Kc7 Kd3 Kb7 Kc3 Ka6 Kd2 Kb6 Ke3 Ka6
Kf3 Kb6
20-> 0.61 0.916 Kb1 Kb7 Kc1 Kc7 Kd1 Kd8 Kc2 Kc8 Kd2
Kc7 Kd3 Kb7 Kc3 Ka6 Kd2 Kb6 Ke3 Ka6
Kf3 Kb6
time: 0.61 cpu:50% mat:1 n:34572 nps:10000
ext-> checks:0 recaps:0 pawns:4 1rep:168
predicted:0 nodes:34572 evals:5208
endgame tablebase-> probes done: 0 successful: 0

Kb3 <HT>
16 0.25 0.916 Kb7 Kb1 Kc6 Kb2 Kc5 Kb3 Kd6 Kc2 Ke6
Kd2 Kd7 Ke2 Kd6 Kf2 Kc5 Kf3
16-> 0.25 0.916 Kb7 Kb1 Kc6 Kb2 Kc5 Kb3 Kd6 Kc2 Ke6
Kd2 Kd7 Ke2 Kd6 Kf2 Kc5 Kf3
17 0.27 1.016 Kb7 Kb1 Kc6 Kb2 Kc5 Kb3 Kd6 Kc2 Ke6
Kd2 Kd7 Kc1 Kc7 Kb1 Kb6 Kc2 Kc5
17-> 0.27 1.016 Kb7 Kb1 Kc6 Kb2 Kc5 Kb3 Kd6 Kc2 Ke6
Kd2 Kd7 Kc1 Kc7 Kb1 Kb6 Kc2 Kc5
18 0.40 1.016 Kb7 Ka1 Kc6 Kb2 Kc5 Kb3 Kd6 Kc2 <HT>
18 0.41 ++ Kb8!!
18-> 0.41 1.315 Kb8
19 0.43 1.016 Kb8 Kb1 Kc7 Kb2 Kc6 Kc2 Kd6 Kb3 Kc5
Ka3 Kc6 Kb2 Kc5 Kb3 Kd6 Kc2 <HT>
19-> 0.43 1.016 Kb8 Kb1 Kc7 Kb2 Kc6 Kc2 Kd6 Kb3 Kc5
Ka3 Kc6 Kb2 Kc5 Kb3 Kd6 Kc2 <HT>
20 0.44 ++ Kb8!!
20 0.48 3.087 Kb8 Kb1 Kc7 Kb2 Kc6 Kc2 Kd6 Kb3 Ke6
Kc2 Kf6 Kd2 Kg6 Ke2 Kh5 Kf3 Kh4 Ke2
Kg3 Kd2 Kxf4
20-> 0.49 3.087 Kb8 Kb1 Kc7 Kb2 Kc6 Kc2 Kd6 Kb3 Ke6
Kc2 Kf6 Kd2 Kg6 Ke2 Kh5 Kf3 Kh4 Ke2
Kg3 Kd2 Kxf4
time: 0.49 cpu:53% mat:2 n:28155 nps:10000
ext-> checks:2 recaps:0 pawns:16 1rep:135
predicted:0 nodes:28155 evals:4631
endgame tablebase-> probes done: 0 successful: 0

holy cow. notice that the normal wtm position is solved at ply=19,
but the score (kb1) is only slightly better. the same position with
BTM is solved at 18, while at 20 it is +3.

Just for fun, here is depth=29

(all of these are run on my p5/233/mmx notebook, which is about 10-15%
slower than my P6/200 running Crafty)

21 0.55 0.916 Kb1 Kb7 Kc1 Kc7 Kd1 Kd8 Kc2 Kc8 Kd2
Kc7 Kd3 Kb7 Ke3 Kc8 Kf3 Kd7 Kg3 Ke7
Kf2 Kf6 Ke3
21-> 0.64 0.916 Kb1 Kb7 Kc1 Kc7 Kd1 Kd8 Kc2 Kc8 Kd2
Kc7 Kd3 Kb7 Ke3 Kc8 Kf3 Kd7 Kg3 Ke7
Kf2 Kf6 Ke3
22 0.70 ++ Kb1!!
22-> 0.72 1.215 Kb1 Kb7 Kc1 Kc7 Kd1 Kd8 Kc2 Kc8 Kd2
Kc7 Kd3 Kb7 Ke3 Kc8 Kf3 Kd7 Kg3 Ke7
Kf2 Kf6 Ke3
23 0.79 0.916 Kb1 Kb7 Kc1 Kc7 Kd1 Kd8 Kc2 Kc8 Kd2
Kc7 Kd3 Kb7 Ke3 Kc8 Kf3 Kd7 Kg3 Ke7
Kf2 Ke8 Kg2 Kf7 Kf3
23-> 0.79 0.916 Kb1 Kb7 Kc1 Kc7 Kd1 Kd8 Kc2 Kc8 Kd2
Kc7 Kd3 Kb7 Ke3 Kc8 Kf3 Kd7 Kg3 Ke7
Kf2 Ke8 Kg2 Kf7 Kf3
24 1.03 ++ Kb1!!
24 1.36 3.087 Kb1 Kb7 Kc1 Kc7 Kd1 Kd8 Kc2 Kc8 Kd2
<HT>
24-> 1.46 3.087 Kb1 Kb7 Kc1 Kc7 Kd1 Kd8 Kc2 Kc8 Kd2
<HT>
25 1.78 3.087 Kb1 Kb7 Kc1 Kc7 Kd1 Kd8 Kc2 Kc8 Kd2
Kd7 Kc3 Kc7 Kd3 Kb6 Ke3 Kc7 Kf3 Kb6
Kg3 Kc7 Kh4 Kb6 Kg5 Kc7 Kxf5
25-> 1.93 3.087 Kb1 Kb7 Kc1 Kc7 Kd1 Kd8 Kc2 Kc8 Kd2
Kd7 Kc3 Kc7 Kd3 Kb6 Ke3 Kc7 Kf3 Kb6
Kg3 Kc7 Kh4 Kb6 Kg5 Kc7 Kxf5
26 2.46 3.087 Kb1 Kb7 Kc1 Kc7 Kd1 Kd8 Kc2 Kc8 Kd2
Kd7 Kc3 Kc7 Kd3 Kb6 Ke3 Kc7 Kf3 Kb6
Kg3 Kc7 Kh4 Kb6 Kg5 Kc7 Kxf5 Kb6
26-> 2.63 3.087 Kb1 Kb7 Kc1 Kc7 Kd1 Kd8 Kc2 Kc8 Kd2
Kd7 Kc3 Kc7 Kd3 Kb6 Ke3 Kc7 Kf3 Kb6
Kg3 Kc7 Kh4 Kb6 Kg5 Kc7 Kxf5 Kb6
27 3.76 3.087 Kb1 Kb7 Kc1 Kc7 Kd1 Kd8 Kc2 Kc8 Kd2
Kd7 Kc3 Kc7 Kd3 Kb6 Ke3 Kc7 Kf3 Kd7
Kg3 Ke7 Kh4 Kf6 Kh5 Ke7 Kg6 Kd7 Kxf5
27-> 4.17 3.087 Kb1 Kb7 Kc1 Kc7 Kd1 Kd8 Kc2 Kc8 Kd2
Kd7 Kc3 Kc7 Kd3 Kb6 Ke3 Kc7 Kf3 Kd7
Kg3 Ke7 Kh4 Kf6 Kh5 Ke7 Kg6 Kd7 Kxf5
28 6.97 3.087 Kb1 Kb7 Kc1 Kc7 Kd1 Kd8 Kc2 Kc8 Kd2
Kd7 Kc3 Kc7 Kd3 Kb6 Ke3 Kc7 Kf3 Kd7
Kg3 Ke7 Kh4 Kf6 Kh5 Ke7 Kg6 Kd7 Kxf5
Ke7
28-> 7.53 3.087 Kb1 Kb7 Kc1 Kc7 Kd1 Kd8 Kc2 Kc8 Kd2
Kd7 Kc3 Kc7 Kd3 Kb6 Ke3 Kc7 Kf3 Kd7
Kg3 Ke7 Kh4 Kf6 Kh5 Ke7 Kg6 Kd7 Kxf5
Ke7
29 26.12 3.187 Kb1 Kb7 Kc1 Kc7 Kd1 Kd8 Kc2 Kc8 Kd2
Kd7 Kc3 Kc7 Kd3 Kb6 Ke3 Kc7 Kf3 Kd7
Kg3 Ke7 Kh4 Kf6 Kh5 Ke7 Kg6 Kd7 Kxf5
Ke7 Ke4
29-> 29.94 3.187 Kb1 Kb7 Kc1 Kc7 Kd1 Kd8 Kc2 Kc8 Kd2
Kd7 Kc3 Kc7 Kd3 Kb6 Ke3 Kc7 Kf3 Kd7
Kg3 Ke7 Kh4 Kf6 Kh5 Ke7 Kg6 Kd7 Kxf5
Ke7 Ke4
30 1:15 3.087 Kb1 Kb7 Kc1 Kc7 Kd1 Kd8 Kc2 Kc8 Kd2
Kd7 Kc3 Kc7 Kd3 Kb6 Ke3 Kc7 Kf3 Kd7
Kg3 Ke7 Kh4 Kf6 Kh5 Ke7 Kg6 Kd7 Kxf5
Ke7 Ke4 Kf6
30-> 1:22 3.087 Kb1 Kb7 Kc1 Kc7 Kd1 Kd8 Kc2 Kc8 Kd2
Kd7 Kc3 Kc7 Kd3 Kb6 Ke3 Kc7 Kf3 Kd7
Kg3 Ke7 Kh4 Kf6 Kh5 Ke7 Kg6 Kd7 Kxf5
Ke7 Ke4 Kf6
time: 1:22 cpu:76% mat:2 n:5244001 nps:82856
ext-> checks:593512 recaps:10648 pawns:170182 1rep:165727
predicted:0 nodes:5244001 evals:489268
endgame tablebase-> probes done: 68531 successful: 68531

21 0.56 3.087 Kb8 Kb1 Kc7 Kb2 Kc6 Kc2 Kd6 Kb3 Ke6
Kc2 Kf6 Kd2 Kg6 Ke2 Kh5 Kf3 Kh4 Ke2
Kg3 Kd2 Kxf4
21-> 0.61 3.087 Kb8 Kb1 Kc7 Kb2 Kc6 Kc2 Kd6 Kb3 Ke6
Kc2 Kf6 Kd2 Kg6 Ke2 Kh5 Kf3 Kh4 Ke2
Kg3 Kd2 Kxf4
22 0.68 3.087 Kb8 Kb1 Kc7 Kb2 Kc6 Kc2 Kd6 Kb3 Ke6
Kc2 Kf6 Kd2 Kg6 Ke2 Kh5 Kf3 Kh4 Ke2
Kg3 Kd2 Kxf4 Ke2
22-> 0.68 3.087 Kb8 Kb1 Kc7 Kb2 Kc6 Kc2 Kd6 Kb3 Ke6
Kc2 Kf6 Kd2 Kg6 Ke2 Kh5 Kf3 Kh4 Ke2
Kg3 Kd2 Kxf4 Ke2
23 0.94 3.160 Kb8 Kb1 Kc7 Kb2 Kc6 Kc2 Kd6 Kb3 Ke6
Kc2 Kf6 Kd2 Kg6 Ke2 Kh5 Kf2 Kg4 Kg2
Kxf4 Kf2 Kg4 Ke2 f4
23-> 0.98 3.160 Kb8 Kb1 Kc7 Kb2 Kc6 Kc2 Kd6 Kb3 Ke6
Kc2 Kf6 Kd2 Kg6 Ke2 Kh5 Kf2 Kg4 Kg2
Kxf4 Kf2 Kg4 Ke2 f4
24 1.18 3.160 Kb8 Kb1 Kc7 Kb2 Kc6 Kc2 Kd6 Kb3 Ke6
Kc2 Kf6 Kd2 Kg6 Ke2 Kh5 Kf2 Kg4 Kg2
Kxf4 Kf2 Kg4 Ke2 f4 Kd2
24-> 1.22 3.160 Kb8 Kb1 Kc7 Kb2 Kc6 Kc2 Kd6 Kb3 Ke6
Kc2 Kf6 Kd2 Kg6 Ke2 Kh5 Kf2 Kg4 Kg2
Kxf4 Kf2 Kg4 Ke2 f4 Kd2
25 1.91 ++ Kb8!!
25 2.16 3.753 Kb8 Kb1 Kc7 Kb2 Kc6 Kc2 Kd6 Kb3 Ke6
Ka3 Kf6 Kb3 Kg6 Kc2 Kh5 Kd2 Kg4 Ke2
Kxf4 Kf2 Kg4 Kg2 f4 Kg1 f3 Kf2
25-> 2.30 3.753 Kb8 Kb1 Kc7 Kb2 Kc6 Kc2 Kd6 Kb3 Ke6
Ka3 Kf6 Kb3 Kg6 Kc2 Kh5 Kd2 Kg4 Ke2
Kxf4 Kf2 Kg4 Kg2 f4 Kg1 f3 Kf2
26 3.45 3.953 Kb8 Kb1 Kc7 Kb2 Kc6 Kc2 Kd6 Kb3 Ke6
Ka3 Kf6 Kb3 Kg6 Kc2 Kh5 Kd2 Kg4 Ke2
Kxf4 Kf2 Kg4 Kg2 f4 Kg1 f3 Kf2 Kf4
26-> 3.58 3.953 Kb8 Kb1 Kc7 Kb2 Kc6 Kc2 Kd6 Kb3 Ke6
Ka3 Kf6 Kb3 Kg6 Kc2 Kh5 Kd2 Kg4 Ke2
Kxf4 Kf2 Kg4 Kg2 f4 Kg1 f3 Kf2 Kf4
27 5.79 3.953 Kb8 Kb1 Kc7 Kb2 Kc6 Kc2 Kd6 Kb3 Ke6
Ka3 Kf6 Kb3 Kg6 Kc2 Kh5 Kd2 Kg4 Ke2
Kxf4 Kf2 Kg4 Kg2 f4 Kf2 f3 Ke1 Kf4
Kf2
27-> 5.97 3.953 Kb8 Kb1 Kc7 Kb2 Kc6 Kc2 Kd6 Kb3 Ke6
Ka3 Kf6 Kb3 Kg6 Kc2 Kh5 Kd2 Kg4 Ke2
Kxf4 Kf2 Kg4 Kg2 f4 Kf2 f3 Ke1 Kf4
Kf2
28 8.91 ++ Kb8!!
28-> 9.78 4.252 Kb8 Kb1 Kc7 Kb2 Kc6 Kc2 Kd6 Kb3 Ke6
Ka3 Kf6 Kb3 Kg6 Kc2 Kh5 Kd2 Kg4 Ke2
Kxf4 Kf2 Kg4 Kg2 f4 Kf2 f3 Ke1 Kf4
Kf2
29 18.98 4.333 Kb8 Kb1 Kc7 Kb2 Kc6 Kc2 Kd6 Kb3 Ke6
Kc2 Kf6 Kd2 Kg6 Ke2 Kh5 Kf3 Kh4 Kf2
Kg4 Kg2 Kxf4 Kf2 Kg4 Kg2 f4 Kf2 f3
Kg1 Kg3 <HT>
29-> 19.16 4.333 Kb8 Kb1 Kc7 Kb2 Kc6 Kc2 Kd6 Kb3 Ke6
Kc2 Kf6 Kd2 Kg6 Ke2 Kh5 Kf3 Kh4 Kf2
Kg4 Kg2 Kxf4 Kf2 Kg4 Kg2 f4 Kf2 f3
Kg1 Kg3 <HT>
30 39.05 4.333 Kb8 Kb1 Kc7 Kb2 Kc6 Kc2 Kd6 Kb3 Ke6
Kc2 Kf6 Kd2 Kg6 Ke2 Kh5 Kf3 Kh4 Kf2
Kg4 Kg2 Kxf4 Kf2 Kg4 Kg2 f4 Kg1 f3
Kh1 Kf4 Kh2 Ke3
30-> 39.22 4.333 Kb8 Kb1 Kc7 Kb2 Kc6 Kc2 Kd6 Kb3 Ke6
Kc2 Kf6 Kd2 Kg6 Ke2 Kh5 Kf3 Kh4 Kf2
Kg4 Kg2 Kxf4 Kf2 Kg4 Kg2 f4 Kg1 f3
Kh1 Kf4 Kh2 Ke3
time: 39.36 cpu:70% mat:2 n:2602740 nps:93556
ext-> checks:236489 recaps:4103 pawns:103280 1rep:85858
predicted:0 nodes:2602740 evals:54260
endgame tablebase-> probes done: 27891 successful: 27891

A lot of data. what does it show?

1. the scores are symmetric for a while, but any slight change
in the move order during the search can let one program find
something that the other one didn't, due to the hash table (if
I disable hashing, the node counts change depending on black or
white, but the scores are identical all the way thru, except that
there is *no* way to search to 30 plies without hashing.

2. the node counts are symmetric for a while, but move ordering
changes this as the search goes deeper.

3. one interesting note: look at the stats for the 30 ply
searches. Crafty was doing thousands of successfull EGTB
probes, hitting the 3 and 4 man tablebases heavily, showing
that at depth=30, we have queens running amok and taking
everything in sight...

Hope that wasn't an information overload, but it does show just
how sensitive the search is to move ordering and hashing...

[Carl Tillotson]

In article <5vu5u3$5...@juniper.cis.uab.edu>, Robert Hyatt wrote:

> A mirrored score is easy, and I have one. The problem is a "mirrored"
> search.

Why would you need to do a "mirrored score" or "mirrored search" ?

Carlos
******
Email Reply : Change "carl.tillotson" to "lca"
Lancashire Chess Association Homepage
http://www.netcomuk.co.uk/~lca/index.htm

Message Written Offline with Virtual Access 4.0 Fri, 19 Sep 1997 18:46 +0100

[Komputer Korner]

Yes, but with hashing disabled, didn't you come to a conclusion awhile back
that even with a mirror position, if bitboards are involved, the score can
never be identical, or is hashing the complete problem discounting the
concept of asymmetry of course.

--
- -
Komputer Korner

The inkompetent komputer

If you see a 1 in my email address, take it out before replying.
Please do not email both me and the r.g.c.c. at the same time. I read all
the postings on r.g.c.c.

Robert Hyatt <hy...@crafty.cis.uab.edu> wrote in article

<5vu967$7...@juniper.cis.uab.edu>...

[Dan Thies]

On 19 Sep 1997 15:32:19 GMT, hy...@crafty.cis.uab.edu (Robert Hyatt)
wrote:

>Komputer Korner (kor...@netcom.ca) wrote:
>
>: Bob, there is one thing that you forgot that bitmaps cannot do. That is
>: provide a completely mirrored score evaluation.
>: >
>

>A mirrored score is easy, and I have one. The problem is a "mirrored"

>search. IE if you set up a position with white to move and have Crafty
>search that position, to a fixed depth, you will search N nodes. If you
>reverse the colors, and set up the same position, but from the black side
>of the board, and do the same search, you will search M nodes where
>M != N, because move ordering will change a little. In theory, this
>should not affect the search outcome at all. In practice, due to the
>transposition table it does.

It changes the score, that's all. What difference does it make,
unless you're trying to use the program to give you some kind of
absolute word-o-god magic number to tell you how good a position is?

Dan

[Robert Hyatt]

Komputer Korner (kor...@netcom.ca) wrote:
: Yes, but with hashing disabled, didn't you come to a conclusion awhile back

: that even with a mirror position, if bitboards are involved, the score can
: never be identical, or is hashing the complete problem discounting the
: concept of asymmetry of course.
: --
: - -
: Komputer Korner

No. If you take out hashing, then we can prove mathematically that move
ordering has *no* effect on the best score returned by alpha/beta minimax
search. But hashing lets things cross over from one path to another and
affect this...

[Robert Hyatt]

Carl Tillotson (c...@netcomuk.co.uk) wrote:

: In article <5vu5u3$5...@juniper.cis.uab.edu>, Robert Hyatt wrote:

: > A mirrored score is easy, and I have one. The problem is a "mirrored"
: > search.

: Why would you need to do a "mirrored score" or "mirrored search" ?

:)

You have missed KK's "non-symmetric" bandwagon I take it? The idea is
that a program *should* give the same analysis for a position without
regard to color. IE if a 7 ply search for white says +.2, then a 6 ply
search for black (after white plays that move) should say -.2...

The "symmetry" in search is an issue of sorts that has nothing at all
to do with how well a program plays. But if you look at the stuff I
posted this afternoon, the effect is noticable. Perhaps even unwanted
by some. But certainly benign in effect...

[Jim Caccamise]

Robert Hyatt <hy...@crafty.cis.uab.edu> wrote in article

<5vv4pf$h...@juniper.cis.uab.edu>...

If the goal is a mirrored search, why not just "reflect" the board
when it's black's move and then generate the moves so that you get
the same move ordering for postions from the black side as from the
white side. The eval. can also be done from this reflected board, so
that eval.'s are also guaranteed to be symmetrical for white and
black.
The performance penalty for this method of generating symmetry is
that the board representation needs to be reflected at each ply, or a
non-reflected and reflected board needs to be maintained and updated
for each ply.

Jim Caccamise

[Robert Hyatt]

Dan Thies (rt...@wt.net) wrote:
: On 19 Sep 1997 15:32:19 GMT, hy...@crafty.cis.uab.edu (Robert Hyatt)
: wrote:

: >Komputer Korner (kor...@netcom.ca) wrote:
: >
: >: Bob, there is one thing that you forgot that bitmaps cannot do. That is
: >: provide a completely mirrored score evaluation.

: >: >
: >

: >A mirrored score is easy, and I have one. The problem is a "mirrored"

: >search. IE if you set up a position with white to move and have Crafty

: >search that position, to a fixed depth, you will search N nodes. If you
: >reverse the colors, and set up the same position, but from the black side
: >of the board, and do the same search, you will search M nodes where
: >M != N, because move ordering will change a little. In theory, this
: >should not affect the search outcome at all. In practice, due to the
: >transposition table it does.

: It changes the score, that's all. What difference does it make,
: unless you're trying to use the program to give you some kind of
: absolute word-o-god magic number to tell you how good a position is?

: Dan

Don't preach to me... I'm already a "convert". :) But the point is
worth discussing... if someone takes the score a program gives and uses
it as an "absolute" number, they are already going where no sane man would
go. However, I happen to believe in asymmetry...

[Robert Hyatt]

Jim Caccamise (c...@magicnet.net) wrote:

: Robert Hyatt <hy...@crafty.cis.uab.edu> wrote in article

: <5vv4pf$h...@juniper.cis.uab.edu>...
: > Carl Tillotson (c...@netcomuk.co.uk) wrote:
: > : In article <5vu5u3$5...@juniper.cis.uab.edu>, Robert Hyatt wrote:
: >

: > : > A mirrored score is easy, and I have one. The problem is a
: "mirrored"
: > : > search.

: >
: > : Why would you need to do a "mirrored score" or "mirrored search"

: Jim Caccamise

It is much worse than you suspect when you use "rotated bitmaps" because
they don't "reflect" worth a flip...

[Komputer Korner]

Mirroring or the lack of same is a completely separate issue from
asymmetry. However if Bob is now claiming that all programs that use alpha
beta without hash tables in an analysis setting (discounting asymmetry
considerations) exhibit mirroring, then mirroring is only a problem with
hash tables and thus this issue will slink back under the table where it
belongs. BUT Bob, doesn't the discussion above contradict the discussion
below which you had with BRUCE.

> This is a problem. Let's take crafty, because this is easy to
explain.
> When I generate moves, I get a 64-bit map of all the squares that this

> particular piece attacks. Which one do I try first? I have two ways
wo
> do this: FirstOne() and LastOne(). for white, FirstOne() will move
the
> piece to the square that is numerically closest to A1, while LastOne()
will
> produce a target closest to H8. If you flip sides, but use the same
> move generator, the move order is different. I attempt to correct
this in
> Crafty by using LastOne() for white, and FirstOne() for black. But
that is
> only one crutch.

It also won't work, will it? If you go h8..a1 with black it is NOT the
same as going
a1..h8 with white. For instance, in the initial position you will
generate moves for
the king before you generate them for the queen, if you are searching
black's move,
and the other way around if you are searching white's move.

What you really want to do is go a8..h8, a7..h8, a6..h6, ..., a1..h1.

Not suggesting you do this though.

> : 6) Move number bounuses could apply here, but unlikely on move
number 1.
>
> I don't like this idea at all, because hashing will completely break
it.
> Remember the discussion about having path-dependent information in the

> evaluation, yet the hashing is position-based. This is going to lead
to
> wrong results, even without changing sides...

--
- -
Komputer Korner

The inkompetent komputer

If you see a 1 in my email address, take it out before replying.
Please do not email both me and the r.g.c.c. at the same time. I read all
the postings on r.g.c.c.

Robert Hyatt <hy...@crafty.cis.uab.edu> wrote in article

[Komputer Korner]

Could you expand on your answer Bob?

--
- -
Komputer Korner

The inkompetent komputer

If you see a 1 in my email address, take it out before replying.
Please do not email both me and the r.g.c.c. at the same time. I read all
the postings on r.g.c.c.

Robert Hyatt <hy...@crafty.cis.uab.edu> wrote in article

<5vvcdj$k...@juniper.cis.uab.edu>...

[Robert Hyatt]

Komputer Korner (kor...@netcom.ca) wrote:
: Could you expand on your answer Bob?

: The inkompetent komputer

: >
: >

Imagine flipping the normal occupied squares bitmap somehow. All you have
to do is a few shifts and OR operations to take the first rank, and slide it
to the 8th, the second to the 7th and so forth. But what about a rotated
bitmap that is turned up on one corner to align the diagonals in a
horizontal way? there is no simpls shift/and/or approach to mirroring that
to match the normal board. It would have to be done bit by bit, and there
are 3 rotated bitmaps. *very* slow process...

[Jim Caccamise]

There are other advantages, besides "mirrored score"and "mirrored
search", for programs that can efficiently operate with a "reflected"
board for black's moves. (Perhaps programs that don't rely heavily
on bitmaps can do this more efficiently.) Using tablebases becomes
easier since all information can be considered from a common "White"
point of view. (i.e. for endgame databases. ) Also, opening and
learning databases can benefit from recognizing positions already
known from the other players point of view.
If 2 copies of board representations (rotated and non-rotated) are
kept and up-dateded for each ply, then this will half the performance
for move/board generation. Reflecting a bit-map involves "moving"
rows (ranks) of data, i.e. a =>h, b=>g, c=>f, d=>e, e=>d, f=>c, g=>b,
h=>a. Is it possible to take advantage of some memory indexing
tricks so the data doesn't actually have to be "moved"? If so, then
the symmetry advantages could be utilized without a significant
performance penalty.

Jim Caccamise

[Robert Hyatt]

Komputer Korner (kor...@netcom.ca) wrote:
: Mirroring or the lack of same is a completely separate issue from

: asymmetry. However if Bob is now claiming that all programs that use alpha
: beta without hash tables in an analysis setting (discounting asymmetry
: considerations) exhibit mirroring, then mirroring is only a problem with
: hash tables and thus this issue will slink back under the table where it
: belongs. BUT Bob, doesn't the discussion above contradict the discussion
: below which you had with BRUCE.

No. the problem is caused by bitmaps producing moves in a different order
after you mirror the position. Because I use a FirstOne() function for
one side and a LastOne() function for the other. an example is a bishop
at e4 that has only 4 moves, d3, f3, d5 and f5. Using the current
approach, I generate the moves (assuming white bishop) of f5, d5, f3 and
d3. If you mirror this so a black bishop is on e5, you get 4 moves of
d4, f4, d6 and f6. Using the opposite function (FirstOne) I get the
moves in the order d4, f4, d6 and f6. Notice the order is *not* the
same.

*but* that causes no problem if you don't use a hash table, because the
order an alpha/beta tree is searched in only affects the size of the tree,
*not* the score of the best move. But with hashing, perturbing the move
ordering can also affect the score as the analysis I posted shows...

[Urban Koistinen]

20 Sep 1997 06:34:11 GMT Robert Hyatt wrote:
! Komputer Korner (kor...@netcom.ca) wrote:
! : Could you expand on your answer Bob?
! : --
! : - -
! : Komputer Korner

! : The inkompetent komputer

! : If you see a 1 in my email address, take it out before replying.
! : Please do not email both me and the r.g.c.c. at the same time. I read all
! : the postings on r.g.c.c.

! : Robert Hyatt <hy...@crafty.cis.uab.edu> wrote in article
! : <5vvcdj$k...@juniper.cis.uab.edu>...
! : >
! : > It is much worse than you suspect when you use "rotated bitmaps" because
! : > they don't "reflect" worth a flip...

! Imagine flipping the normal occupied squares bitmap somehow. All you have
! to do is a few shifts and OR operations to take the first rank, and slide it
! to the 8th, the second to the 7th and so forth. But what about a rotated
! bitmap that is turned up on one corner to align the diagonals in a
! horizontal way? there is no simpls shift/and/or approach to mirroring that
! to match the normal board. It would have to be done bit by bit, and there
! are 3 rotated bitmaps. *very* slow process...

It ain't necessarily so.

Flipping the regular bitmap:
t1 = (0xffffffffull&(b>>32)) | (0xffffffff00000000ull&(b<<32));
t2 = (0xffff0000ffffull&(t1>>16)) | (0xffff0000ffff0000ull&(t1<<16));
result = (0xff00ff00ff00ffull&(t2>>8)) | (0xff00ff00ff00ff00ull&(t2<<8));

Flipping the 90 degrees bitmap:
t1 = (0xf0f0f0f0f0f0f0full&(b>>4)) | (0xf0f0f0f0f0f0f0f0ull&(b<<4));
t2 = (0x3333333333333333ull&(t1>>2)) | (0xccccccccccccccccull&(t1<<2));
result = (0x5555555555555555ull&(t2>>1)) | (0xaaaaaaaaaaaaaaaaull&(t2<<1));

Flipping the diagonal bitmaps:
How about swapping the two diagonal bitmaps?
That should do it.

Upright bitmap: (is there a better name?)
a1..h8,
a2..g8, h1
a3..f8, g1..h2
a4..e8, f1..h3
a5..d8, e1..h4
a6..c8, d1..h5
a7..b8, c1..h6
a8, b1..h7

Downright bitmap: (is there a better name?)
a8..h1,
a7..g1, h8
a6..f1, g8..h7
a5..e1, f8..h6
a4..d1, e8..h5
a3..c1, d8..h4
a2..b1, c8..h3
a1, b8..h2

When you swap them the old Upright becoms the new Downright
and the old Downright becomes the new Upright.

See the symmetry of the beautiful rotations,
Urban Koistinen

[Robert Hyatt]

Jim Caccamise (c...@magicnet.net) wrote:

: There are other advantages, besides "mirrored score"and "mirrored

: search", for programs that can efficiently operate with a "reflected"
: board for black's moves. (Perhaps programs that don't rely heavily
: on bitmaps can do this more efficiently.) Using tablebases becomes
: easier since all information can be considered from a common "White"
: point of view. (i.e. for endgame databases. )

this isn't a problem for bitmappers either, because the bitmaps are
useless for probing. The database probes are made by using a "Godel"
number formed by concatenating the square numbers for all the pieces.
This square number is obtained by finding where each piece stands, and
isn't helped or hurt by bitmaps..

: Also, opening and

: learning databases can benefit from recognizing positions already
: known from the other players point of view.

Same thing here as above. I don't use bitmaps to probe the opening
database, I use the hash signature, which is the most common way of
getting into an opening database. This can easily be computed for
mirrored positions if needed to probe such a database, to pick up
openings like e3 e5 e4 where we are now in a normal opening position
but with side-to-move reversed.

: If 2 copies of board representations (rotated and non-rotated) are

: kept and up-dateded for each ply, then this will half the performance
: for move/board generation. Reflecting a bit-map involves "moving"
: rows (ranks) of data, i.e. a =>h, b=>g, c=>f, d=>e, e=>d, f=>c, g=>b,
: h=>a. Is it possible to take advantage of some memory indexing
: tricks so the data doesn't actually have to be "moved"? If so, then
: the symmetry advantages could be utilized without a significant
: performance penalty.

I already keep 4 bitmaps: non-rotated (rook rank attacks); rotated left
90 degrees (rook file attacks); rotated left 45 degress (bishop diagonal
attacks on a8-h1 diagonal); and rotated right 45 degrees (bishop diagonal
attacks on a1-h8 diagonal). The problem lies in mirroring the rotated
bitmaps, which is doable, but not on a move-by-move basis as it would be
way too expensive..

: Jim Caccamise

:

[Robert Hyatt]

Urban Koistinen (m10...@abc.se) wrote:

: ! : The inkompetent komputer

cute. It becomes easier than I thought. There is a down-side in that
"Dark Thought" uses a different approach, that rather than rotating, they
remap, so that the effect is still the same. IE, they remap using a cute
function, to turn diagonal squares into adjacent bits. They would have
trouble with this, although I seem to get by with little difficulty...

[Carl Tillotson]

Hope I haven't started a war with my question about "bitboards" :-)

Carl Tillotson
=============

Lancashire Chess Association Homepage
http://www.netcomuk.co.uk/~lca/index.htm

For the latest news, reviews and events happening on the
Lancashire Chess scene, visit the Lancashire Chess Association
homepage.

[Urban Koistinen]

21 Sep 1997 03:21:24 EDT Komputer Korner wrote:
! So does this mean that the cost of rotation/remapping is low enough to do
! it on every move so as to get correct mirroring with hash tables?

It depends on your goals and on your data structures.

Your friendly mosquito,
Urban Koistinen

[Robert Hyatt]

Komputer Korner (kor...@netcom.ca) wrote:
: So does this mean that the cost of rotation/remapping is low enough to do
: it on every move so as to get correct mirroring with hash tables?

depends. It is not horribly expensive. It is *not* free either. So
there is a cost in computation that has to be weighed against the gains
in chess-playing strength. In that comparison, the cost is measurable
and would have an effect on strength because of slowing the program
down. There would not be any gain in playing strength from getting
move ordering the same for both sides..

Ie, it would be a waste of time and effort...

: --
: - -
: Komputer Korner

: The inkompetent komputer

: If you see a 1 in my email address, take it out before replying.

: Please do not email both me and the r.g.c.c. at the same time. I read all

: the postings on r.g.c.c.

: Robert Hyatt <hy...@crafty.cis.uab.edu> wrote in article

: <600pus$7...@juniper.cis.uab.edu>...
: > Urban Koistinen (m10...@abc.se) wrote:
: > >
: > : When you swap them the old Upright becoms the new Downright

: >
: >

[Komputer Korner]

So does this mean that the cost of rotation/remapping is low enough to do
it on every move so as to get correct mirroring with hash tables?

[Urban Koistinen]

20 Sep 1997 15:26:20 GMT Robert Hyatt wrote:
! Urban Koistinen (m10...@abc.se) wrote:
! : 20 Sep 1997 06:34:11 GMT Robert Hyatt wrote:
! : ! Komputer Korner (kor...@netcom.ca) wrote:
! : ! : Could you expand on your answer Bob?
! : ! : Robert Hyatt <hy...@crafty.cis.uab.edu> wrote in article
! : ! : <5vvcdj$k...@juniper.cis.uab.edu>...

! : ! : >
! : ! : > It is much worse than you suspect when you use

! : ! : > "rotated bitmaps" because
! : ! : > they don't "reflect" worth a flip...

! : ! Imagine flipping the normal occupied squares bitmap somehow.
! : ! All you have
! : ! to do is a few shifts and OR operations to take the first
! : ! rank, and slide it
! : ! to the 8th, the second to the 7th and so forth.
! : ! But what about a rotated
! : ! bitmap that is turned up on one corner to align the diagonals in a
! : ! horizontal way?
! : ! there is no simpls shift/and/or approach to mirroring that
! : ! to match the normal board.
! : ! It would have to be done bit by bit, and there
! : ! are 3 rotated bitmaps. *very* slow process...

! : It ain't necessarily so.

! : Flipping the regular bitmap:
! : t1 = (0xffffffffull&(b>>32)) | (0xffffffff00000000ull&(b<<32));
! : t2 = (0xffff0000ffffull&(t1>>16)) | (0xffff0000ffff0000ull&(t1<<16));
! : result = (0xff00ff00ff00ffull&(t2>>8)) | (0xff00ff00ff00ff00ull&(t2<<8));

! : Flipping the 90 degrees bitmap:
! : t1 = (0xf0f0f0f0f0f0f0full&(b>>4)) | (0xf0f0f0f0f0f0f0f0ull&(b<<4));
! : t2 = (0x3333333333333333ull&(t1>>2)) | (0xccccccccccccccccull&(t1<<2));
! : result=(0x5555555555555555ull&(t2>>1)) | (0xaaaaaaaaaaaaaaaaull&(t2<<1));

! : Flipping the diagonal bitmaps:
! : How about swapping the two diagonal bitmaps?
! : That should do it.

! : Upright bitmap: (is there a better name?)
! : a1..h8,
! : a2..g8, h1
! : a3..f8, g1..h2
! : a4..e8, f1..h3
! : a5..d8, e1..h4
! : a6..c8, d1..h5
! : a7..b8, c1..h6
! : a8, b1..h7

! : Downright bitmap: (is there a better name?)
! : a8..h1,
! : a7..g1, h8
! : a6..f1, g8..h7
! : a5..e1, f8..h6
! : a4..d1, e8..h5
! : a3..c1, d8..h4
! : a2..b1, c8..h3
! : a1, b8..h2

! : When you swap them the old Upright becoms the new Downright
! : and the old Downright becomes the new Upright.

! : See the symmetry of the beautiful rotations,
! : Urban Koistinen

! cute. It becomes easier than I thought. There is a down-side in that
! "Dark Thought" uses a different approach, that rather than rotating, they
! remap, so that the effect is still the same. IE, they remap using a cute
! function, to turn diagonal squares into adjacent bits. They would have
! trouble with this, although I seem to get by with little difficulty...

I don't understand the downside.

Urban Koistinen

[Urban Koistinen]

21 Sep 1997 13:55:46 GMT Robert Hyatt wrote:
! Urban Koistinen (m10...@abc.se) wrote:

! : 20 Sep 1997 15:26:20 GMT Robert Hyatt wrote:

! : ! cute. It becomes easier than I thought.
! : ! There is a down-side in that
! : ! "Dark Thought" uses a different approach,
! : ! that rather than rotating, they
! : ! remap, so that the effect is still the same.
! : ! IE, they remap using a cute
! : ! function, to turn diagonal squares into adjacent bits.
! : ! They would have
! : ! trouble with this, although I seem to
! : ! get by with little difficulty...

! : I don't understand the downside.

! Dark Thought doesn't "rotate", they "remap". IE rather than rotating
! left/right as I do, they remap the bits in the maps so that they are
! in adjacent bits. But it is not symmetric like the rotations are, so
! you can't just "interchange" the bitmaps as you suggested in Crafty.

Sorry, I wasn't thinking of Crafty.
It is best to chose mapping depending on what you want to do.
For instance, my mapping would not be so good if you want symmetry
for left and right instead of up&down.

! They would have to be remapped... which would take a significant
! amount of time, although the above "mirroring" is quite expensive as
! it is...

What is the advantage of the Dark Thought mapping compared to mine?

Urban Koistinen

[Robert Hyatt]

Urban Koistinen (m10...@abc.se) wrote:
: 20 Sep 1997 15:26:20 GMT Robert Hyatt wrote:

: ! Urban Koistinen (m10...@abc.se) wrote:
: ! : 20 Sep 1997 06:34:11 GMT Robert Hyatt wrote:

: ! cute. It becomes easier than I thought. There is a down-side in that
: ! "Dark Thought" uses a different approach, that rather than rotating, they
: ! remap, so that the effect is still the same. IE, they remap using a cute
: ! function, to turn diagonal squares into adjacent bits. They would have
: ! trouble with this, although I seem to get by with little difficulty...

: I don't understand the downside.

Dark Thought doesn't "rotate", they "remap". IE rather than rotating

left/right as I do, they remap the bits in the maps so that they are

in adjacent bits. But it is not symmetric like the rotations are, so

you can't just "interchange" the bitmaps as you suggested in Crafty.

They would have to be remapped... which would take a significant

amount of time, although the above "mirroring" is quite expensive as

it is...

[Robert Hyatt]

Urban Koistinen (m10...@abc.se) wrote:

: 21 Sep 1997 13:55:46 GMT Robert Hyatt wrote:
: ! Urban Koistinen (m10...@abc.se) wrote:

: ! : 20 Sep 1997 15:26:20 GMT Robert Hyatt wrote:

: ! : ! cute. It becomes easier than I thought.
: ! : ! There is a down-side in that
: ! : ! "Dark Thought" uses a different approach,
: ! : ! that rather than rotating, they
: ! : ! remap, so that the effect is still the same.
: ! : ! IE, they remap using a cute
: ! : ! function, to turn diagonal squares into adjacent bits.
: ! : ! They would have
: ! : ! trouble with this, although I seem to
: ! : ! get by with little difficulty...

: ! : I don't understand the downside.

: ! Dark Thought doesn't "rotate", they "remap". IE rather than rotating
: ! left/right as I do, they remap the bits in the maps so that they are
: ! in adjacent bits. But it is not symmetric like the rotations are, so
: ! you can't just "interchange" the bitmaps as you suggested in Crafty.

: Sorry, I wasn't thinking of Crafty.

: It is best to chose mapping depending on what you want to do.
: For instance, my mapping would not be so good if you want symmetry
: for left and right instead of up&down.

: ! They would have to be remapped... which would take a significant
: ! amount of time, although the above "mirroring" is quite expensive as
: ! it is...

: What is the advantage of the Dark Thought mapping compared to mine?

: Urban Koistinen

When I first thought about doing the rotated bitmap idea, I discussed it
with Peter G. of the Dark Thought team. He thought (as I did) that the
idea was pretty neat and worth trying. I (from the first thought) had
always planned on updating the rotated bitmaps by the following approach:

I have a set of 64 bitmaps callet set_mask[n]. To set bit 32, I simply
AND(bit-map,set_mask[32]). If I have a rotated-90 bitmap, then I also
create a rotated-90 set_mask, and do this: AND(bit-map-R90,set_mask_R90[32])
and I am done.

Peter didn't like this, and wanted to get rid of the extra memory load
for the rotated set_mask variable. (note there are actually 4 of these
loads needed, for each of the rotated bitmaps). So he thought about it
a bit and found a cute mathematical transformation based on shifts, AND's
and OR's (I won't give it here since it is his idea) that avoide needing
the set_mask_Rxx masks (note that on some machines, even the set_mask
itself is not needed. to set bit 32 you just start with "1" and shift it
to the right position avoiding the memory load altogether.

However, the effect of Peter's approach is to map diagonal bits on the real
bitmap to adjacent bits in a "psuedo-rotated" bitmap, without needing the
set_mask_R90 stuff at all. Is it better? I'm not sure. My tests on the P6
said NO. My tests on the alpha with big cache also said NO. Peter's tests
on the machine he used said YES. It definitely takes more instructions to
do what Peter is doing. On a machine with a huge memory latency, like the
PC, my memory loading can be slow. But with a decent sized cache, the 64
words X 8 bytes per word (512 bytes) really tucks into a corner in cache
and doesn't hurt at all, particularly since a cache hit on the P6 operates
at CPU speed. The PII is a different case since the cache operates at 1/2
CPU speed, which might swing things in his favor.

For the record, they are *close* under all cases. We are not talking
10% here...one might be 2% faster on one machine, the other 3% faster on
another machine...

But the "mapping" is really odd and would not let us just simply swap the
L45 and R45 maps...

[Urban Koistinen]

21 Sep 1997 17:29:51 GMT Robert Hyatt wrote:
! Urban Koistinen (m10...@abc.se) wrote:

! : 21 Sep 1997 13:55:46 GMT Robert Hyatt wrote:
! : ! Urban Koistinen (m10...@abc.se) wrote:
! : ! : 20 Sep 1997 15:26:20 GMT Robert Hyatt wrote:

! : ! : ! cute. It becomes easier than I thought.
! : ! : ! There is a down-side in that
! : ! : ! "Dark Thought" uses a different approach,
! : ! : ! that rather than rotating, they
! : ! : ! remap, so that the effect is still the same.
! : ! : ! IE, they remap using a cute
! : ! : ! function, to turn diagonal squares into adjacent bits.
! : ! : ! They would have
! : ! : ! trouble with this, although I seem to
! : ! : ! get by with little difficulty...

! : ! : I don't understand the downside.

! : ! Dark Thought doesn't "rotate", they "remap". IE rather than rotating
! : ! left/right as I do, they remap the bits in the maps so that they are
! : ! in adjacent bits. But it is not symmetric like the rotations are, so
! : ! you can't just "interchange" the bitmaps as you suggested in Crafty.

! : Sorry, I wasn't thinking of Crafty.
! : It is best to chose mapping depending on what you want to do.
! : For instance, my mapping would not be so good if you want symmetry
! : for left and right instead of up&down.

! : ! They would have to be remapped... which would take a significant
! : ! amount of time, although the above "mirroring" is quite expensive as
! : ! it is...

! : What is the advantage of the Dark Thought mapping compared to mine?

! When I first thought about doing the rotated bitmap idea, I discussed it
! with Peter G. of the Dark Thought team. He thought (as I did) that the
! idea was pretty neat and worth trying. I (from the first thought) had
! always planned on updating the rotated bitmaps by the following approach:

! I have a set of 64 bitmaps callet set_mask[n]. To set bit 32, I simply
! AND(bit-map,set_mask[32]). If I have a rotated-90 bitmap, then I also
! create a rotated-90 set_mask, and do this:
! AND(bit-map-R90,set_mask_R90[32])
! and I am done.

! Peter didn't like this, and wanted to get rid of the extra memory load
! for the rotated set_mask variable. (note there are actually 4 of these
! loads needed, for each of the rotated bitmaps).

He got a 16-bit machine or you got a typo(for each rotated bitmap).

! So he thought about it
! a bit and found a cute mathematical transformation based on shifts, AND's
! and OR's (I won't give it here since it is his idea) that avoide needing
! the set_mask_Rxx masks (note that on some machines, even the set_mask
! itself is not needed. to set bit 32 you just start with "1" and shift it
! to the right position avoiding the memory load altogether.

! However, the effect of Peter's approach is to map diagonal bits on the real
! bitmap to adjacent bits in a "psuedo-rotated" bitmap, without needing the
! set_mask_R90 stuff at all. Is it better? I'm not sure. My tests on the P6
! said NO. My tests on the alpha with big cache also said NO. Peter's tests
! on the machine he used said YES. It definitely takes more instructions to
! do what Peter is doing. On a machine with a huge memory latency, like the
! PC, my memory loading can be slow. But with a decent sized cache, the 64
! words X 8 bytes per word (512 bytes) really tucks into a corner in cache
! and doesn't hurt at all, particularly since a cache hit on the P6 operates
! at CPU speed. The PII is a different case since the cache operates at 1/2
! CPU speed, which might swing things in his favor.

! For the record, they are *close* under all cases. We are not talking
! 10% here...one might be 2% faster on one machine, the other 3% faster on
! another machine...

! But the "mapping" is really odd and would not let us just simply swap the
! L45 and R45 maps...

I think calculating the offset can be done all right for my mapping too.

Upright:
result = 077 & (sq-(sq<<3));

Downright:
result = 077 & (sq+(sq<<3));

Simple 8x8 algebra.
Not very odd.

Uses:
1 shift
1 add or sub
1 and
0 or

You might be able to skip the and depending on the CPU.
If you are doing both Upright and Downright you can share
the shift. (also 1 of 2 for the Onside (90 degrees) where
1 or would be needed)

Is it cute because it is small?

I am assuming a 64-bit machine but something similar is
possible on, for example, 6502 (old chess micro favourite).

Urban Koistinen

[Marcel van Kervinck]

Robert Hyatt <hy...@crafty.cis.uab.edu> wrote:

> When I first thought about doing the rotated bitmap idea, I discussed it

> with Peter G. of the Dark Thought team. He thought (as I did) that the

> idea was pretty neat and worth trying. I (from the first thought) had

> always planned on updating the rotated bitmaps by the following approach:

> I have a set of 64 bitmaps callet set_mask[n]. To set bit 32, I simply

> AND(bit-map,set_mask[32]). If I have a rotated-90 bitmap, then I also

> create a rotated-90 set_mask, and do this: AND(bit-map-R90,set_mask_R90[32])
> and I am done.

You use an AND to set bits? Typo...?

> Peter didn't like this, and wanted to get rid of the extra memory load

> for the rotated set_mask variable. (note there are actually 4 of these

> loads needed, for each of the rotated bitmaps). So he thought about it

> a bit and found a cute mathematical transformation based on shifts, AND's

> and OR's (I won't give it here since it is his idea) that avoide needing

> the set_mask_Rxx masks (note that on some machines, even the set_mask

> itself is not needed. to set bit 32 you just start with "1" and shift it

> to the right position avoiding the memory load altogether.

Sounds they have something too expensive. There is a very simple mapping
that does the same. After puzzling on Urban's mapping, I found next one:

ordinary square number:
unsigned sq;

to rotate right:
sq -= sq << 3;
sq &= 63;

to rotate left:
sq += sq << 3;
sq &= 63;

Or visualized:
sq right left
0 1 2 3 4 5 6 7 0 57 50 43 36 29 22 15 0 9 18 27 36 45 54 63
8 9 10 11 12 13 14 15 8 1 58 51 44 37 30 23 8 17 26 35 44 53 62 7
16 17 18 19 20 21 22 23 16 9 2 59 52 45 38 31 16 25 34 43 52 61 6 15
24 25 26 27 28 29 30 31 24 17 10 3 60 53 46 39 24 33 42 51 60 5 14 23
32 33 34 35 36 37 38 39 32 25 18 11 4 61 54 47 32 41 50 59 4 13 22 31
40 41 42 43 44 45 46 47 40 33 26 19 12 5 62 55 40 49 58 3 12 21 30 39
48 49 50 51 52 53 54 55 48 41 34 27 20 13 6 63 48 57 2 11 20 29 38 47
56 57 58 59 60 61 62 63 56 49 42 35 28 21 14 7 56 1 10 19 28 37 46 55

You may even drop the AND statement on some architectures: Sometimes
that is done implicitly by the BITSET and BITCLEAR instructions. (They
often simply ignore the higher order bits of the operand) Now, the last
two rotations don't really rotate as Crafty does, but they remap so that
diagonally connected squares have adjacent bits. In fact, they seem
to yield the same remappings Urban has suggested in an earlier post.

Just a thought.

Marcel
-- _ _
_| |_|_|
|_ |_ mar...@stack.nl
|_| Marcel van Kervinck

[Robert Hyatt]

Marcel van Kervinck (mar...@unox.hak.nl) wrote:

[Robert Hyatt]

Urban Koistinen (m10...@abc.se) wrote:

: He got a 16-bit machine or you got a typo(for each rotated bitmap).

No, I didn't explain very clearly. there are *four* occupied_square bitmaps
(including the normal non-rotated one). So, to set or clear a bit in each
one requires a 64-bit load to get the set or clear mask for that rotation.

Peter's approach computes this set/clear mask by computing the proper
shift for a "1" bit, which takes more instructions, but one less memory
load. I didn't find it worked to save any time at all on the machines
I had access to, but Peter said it was faster on his hardware...

: ! So he thought about it
: ! a bit and found a cute mathematical transformation based on shifts, AND's
: ! and OR's (I won't give it here since it is his idea) that avoide needing
: ! the set_mask_Rxx masks (note that on some machines, even the set_mask
: ! itself is not needed. to set bit 32 you just start with "1" and shift it
: ! to the right position avoiding the memory load altogether.

: ! However, the effect of Peter's approach is to map diagonal bits on the real

yep... similar to Peter's code..

: I am assuming a 64-bit machine but something similar is

[Dan Thies]

On 20 Sep 1997 02:28:10 GMT, hy...@crafty.cis.uab.edu (Robert Hyatt)
wrote:

>: It changes the score, that's all. What difference does it make,

>: unless you're trying to use the program to give you some kind of
>: absolute word-o-god magic number to tell you how good a position is?
>
>: Dan
>
>Don't preach to me... I'm already a "convert". :)

Testify, brother!

KK backed off of the assymmetry thing when he understood that
getting both scores meant doing both searches. This looks the
same to me.

>But the point is
>worth discussing...

The discussion of how to mirror the rotated bitmaps has proved very
enlightening - before this the only model I had for implementing them
was from Crafty - now I have all these exciting clues about other
methods to think about.

Dan

[Dan Thies]

On Sat, 20 Sep 1997 23:05:14 +0100, Carl Tillotson
<anti...@anti.spam.somewhere.com> wrote:
>Hope I haven't started a war with my question about "bitboards" :-)

No, it's a good question.

We've been into the related question of _assymmetry_ before.
KK wanted all of us to have both an assymetrical and a symmetrical
evaluation function, and give both scores after every search. After
I pointed out that since different evaluation functions would cause
the search to take different paths and be shaped differently, and that
this meant that you'd have to do two searches to use two evals, and
that the two searches might return different moves to go along with
the different scores, he stopped on that.

After a lengthy retreat with the Dalai Lama, KK came back and wanted
mirroring instead. This is more interesting, since it represents a
more "real" problem. But to me, the reason for writing the program is
to make something that plays good chess, not something that pretends
to give you an exact score. Mirroring isn't a problem in my program
anyway, but since it doesn't return a numeric score (just a move with
a few expected variations attached) I doubt KK will find it useful
anyway.

Dan