I have thought about how many (really) different positions there is in a
say K+R vs K endgame. It is okay to include the inpossible (king next to
king), but a symmetrical position should only be counted once.

I.e. ka1, Rb2, Kc2 = ka1, Rb2, Kb3 and also in the other corners.

Jonas

Jonas Forsslund wrote:
I have thought about how many (really) different positions there is in
a say K+R vs K endgame. It is okay to include the inpossible (king next
to king), but a symmetrical position should only be counted once.

I.e. ka1, Rb2, Kc2 = ka1, Rb2, Kb3 and also in the other corners.

For symmetry's sake, we may assume that it is White who has the rook.

White's king could be on one of 64 squares, which leaves 63 for his rook
and 62 for the Black king. So, that's 64x63x62 basic positions. Now we
need to take symmetry into account. The board has four mirror symmetries
(the line between the d and e files, the line between the fourth and fifth
tanks and the two long diagonals) and rotating the board by ninety degrees
is also a symmetry so there are four rotational symmetries.

The total, then, is

64 x 63 x 62
------------ = 15,624.
4 x 4

That's physical arrangements of the pieces on the board, including illegal
positions. If you're ultra-pedantic and want to include information about
whether the player with the rook can castle, add two (one extra for Ra1
Ke1, White can castle long, the other for Rh1 Ke1, White can castle short)
If you want to count positions as different if the other
player has the move, multiply by two.

Actually legal positions will be a little bit less but rather harder to
count.


Dave.

--
David Richerby Incredible Smokes (TM): it's like
www.chiark.greenend.org.uk/~davidr/ a pack of cigarettes but it'll blow
your mind!

"David Richerby" wrote in message
...
Jonas Forsslund wrote:
I have thought about how many (really) different positions there is in
a say K+R vs K endgame. It is okay to include the inpossible (king next
to king), but a symmetrical position should only be counted once.

I.e. ka1, Rb2, Kc2 = ka1, Rb2, Kb3 and also in the other corners.

For symmetry's sake, we may assume that it is White who has the rook.

White's king could be on one of 64 squares, which leaves 63 for his rook
and 62 for the Black king. So, that's 64x63x62 basic positions. Now we
need to take symmetry into account. The board has four mirror symmetries
(the line between the d and e files, the line between the fourth and fifth
tanks and the two long diagonals) and rotating the board by ninety degrees
is also a symmetry so there are four rotational symmetries.

The total, then, is

64 x 63 x 62
------------ = 15,624.
4 x 4

According to your formula you can restrict lone king to

64
----- = 4 squares
4 x 4

using mirroring and rotations. I somewhat doubt that :-)

Thanks,
Eugene

That's physical arrangements of the pieces on the board, including illegal
positions. If you're ultra-pedantic and want to include information about
whether the player with the rook can castle, add two (one extra for Ra1
Ke1, White can castle long, the other for Rh1 Ke1, White can castle short)
If you want to count positions as different if the other
player has the move, multiply by two.

Actually legal positions will be a little bit less but rather harder to
count.


Dave.

--
David Richerby Incredible Smokes (TM): it's
like
www.chiark.greenend.org.uk/~davidr/ a pack of cigarettes but it'll
blow
your mind!

In article ,
"Eugene Nalimov" writes:

"David Richerby" wrote in message
...
64 x 63 x 62
------------ = 15,624.
4 x 4

According to your formula you can restrict lone king to

64
----- = 4 squares
4 x 4


Let's see where the problem is: Start with the full board.
Mirroring along the vertical between d and e file halves the
positions. 32 left.
Mirroring along the horizontal between 4 and 5 halves again.
16 left. (e.g., the a1-a4-d1-d4 square).
Mirroring along the diagonal projects the four fields a1-d4
onto themselves, reducing noting. The other 12 fields boil
down to 6, leaving a total of 10.
There is no other symmetry operation, since the long diagonal
a8-h1 is not independent: it can be generated from combinations
of the already used operations.
Thus you can restrict the king to 10 fields, a1-d1-d4 triangle.

BTW, if I'm not mistaken Eugene's indexing scheme actually
exploits the fact that king-next-to-king is not possible,
thus reducing the 63 somewhat. (More precise, this should leave
you with only one factor for both kings, and it's somewhat
smaller than 10x63).

Werner

I am not convinced that you can reduce the positions only by looking
at the mirrors. (That is, for more than one piece)

For example, there is eight positions of (ka1, Rb2, Kc2)
(= ka1, Rb2, Kb3 and also in the other corners.)
but only four of (ka1,Rb2,Kc3). I belive this must be
taking into count.

The reason I became curious is that I am reading discrete
mathematics right now at university. A similar problem we
learned about (In book "Biggs, Norman: Discrete Mathematics" SE) is
"How many identity cards of size 3x3 with two holes can we make,
so that they can be rotaded and fliped over"? The answere is 8.
The theorem used is:

Number of orbits of G on X is
___
_1_ \ | F(g)|
|G| /__
g{G

Or, the number of orbits is equal to the average size of the sets F(g)
We have 8 symmetries I belive, as in the card-problem:
identity (card: 9 over 2, chess 64*63*62)
clockwise rotation 90' (card 0, chess ?)
clockwise rotation 180' (card 4, chess ?)
clockwise rotation 270' (card 0, chess ?)
Reflection diagonal 1 (card 6, chess ?)
Reflection diagonal 2 (card 6, chess ?)
Reflection in perpendicular bisector a1-a8 (card 6, chess ?)
Reflection of perpendicular bisector a1-h1 (card 6, chess ?)


I do belive this is a way to count, or is it too hard to figure out
those numbers?




Werner Mühlpfordt wrote:
Let's see where the problem is: Start with the full board.
Mirroring along the vertical between d and e file halves the
positions. 32 left.
Mirroring along the horizontal between 4 and 5 halves again.
16 left. (e.g., the a1-a4-d1-d4 square).
Mirroring along the diagonal projects the four fields a1-d4
onto themselves, reducing noting. The other 12 fields boil
down to 6, leaving a total of 10.
There is no other symmetry operation, since the long diagonal
a8-h1 is not independent: it can be generated from combinations
of the already used operations.
Thus you can restrict the king to 10 fields, a1-d1-d4 triangle.

Yes I agree, there is 10 fields for one king. Is it possible to use
this method to extend it with another piece? If so, how?

/Jonas Forsslund
Msc Comp. Sci. Student, Sweden

In article ,
Jonas Forsslund writes:
I am not convinced that you can reduce the positions only by looking
at the mirrors. (That is, for more than one piece)
There are several ways ("representations") to combine symmetry
operations to yield the same reduction. Some of the
include rotations. But you will always end up with the same
two-dimensional point symmetry group. It has 8-fold symmetry
for the "normal" case, and 4-fold symmetry for diagonal fields
(for a really central field, it would be only 1 - but there is
no d..e 4..5 ;-) Thus: 16 diagonal fields divided by 4 yields 4,
48 normal fields divided by 8 yields 6. Same result.

For example, there is eight positions of (ka1, Rb2, Kc2)
(= ka1, Rb2, Kb3 and also in the other corners.)
but only four of (ka1,Rb2,Kc3). I belive this must be
taking into count.
You can pick any piece - but I believe for an indexing scheme
you must pick the same all the time.

Yes I agree, there is 10 fields for one king. Is it possible to use
this method to extend it with another piece? If so, how?

You could apply further symmetry in case of an on-diagonal "first"
piece. I.e., with white King on a1, black king on h7 or g8 is
the same position. Put the white king on a2, however, bKh7/g8
are different.
This can be extended: with wKb2, bKd4, the positions with Ra8
and Rh1 are identical. And so on.

Werner

(Werner Mühlpfordt) wrote in message ...
In article ,
Jonas Forsslund writes:
There are several ways ("representations") to combine symmetry
operations to yield the same reduction. Some of the
include rotations. But you will always end up with the same
two-dimensional point symmetry group. It has 8-fold symmetry
for the "normal" case, and 4-fold symmetry for diagonal fields

Sounds good to me. So just looking at arrangements (white with the
rook), there are 64*63*62 total, with 16*7*6 of them along diagonals
right?

Diag: WK*BK*WR
16* 7* 6 = 672

(WK*BK*WR - diag) / 8 + diag / 4
(64*63*62 - 672) / 8 + 672 / 4 = 31,332

To eliminate king-by-king positions, there are 4 corners where the WK
takes away 4 squares, 24 edge squares where he takes 6, and on the
remaining 36 squares he takes 9. On the diagonals, he has 4 corners
where he takes away 2, and 12 squares where he takes away 3:

Diag: 4*(8-2)*6 + 12*(8-3)*6 = 504 positions with only 4-fold symmetry

(4*(64-4)*62 + 24*(64-6)*62 + 36*(64-9)*62 - 504) / 8 + 504 / 4 =
28,056

Assuming that the computer played the game up to the position, it
shouldn't need to consider draw by repetition or 50-move rule, but
there would be the two additional positions where white has castling
rights (but would it matter?).

So I get 28,058 unique positions with Black to move. White to move is
a lot more complicated because any position where Black is in check by
the Rook would be illegal.

Benjamin Jordan

Hi,

without pawns there is 462 king - king positions.

you can also mirror on the diagonal

i don't reduce for checks in diep.
egtb command (or help): list
NR NAME KEY #ENTRIES EXISTS (disk,ram)
1 kpk 00008000 84012 -- -- -- --
2 knk 00040000 28644 -- -- -- --
3 kbk 00200000 28644 -- -- -- --
4 krk 01000000 28644 -- -- -- --
5 kqk 08000000 28644 -- -- -- --
6 kppk 00010000 1912372 -- -- -- --
7 knpk 00048000 5124732 -- -- -- --
8 knnk 00080000 873642 -- -- -- --
9 kbpk 00208000 5124732 -- -- -- --
10 kbnk 00240000 1747284 -- -- -- --
11 kbbk 00400000 873642 -- -- -- --
12 krpk 01008000 5124732 -- -- -- --
13 krnk 01040000 1747284 -- -- -- --

That's why i have 28644 positions for KRK.


so if you reduce with symmetry and such then it's pretty small egtb.

62 * 462 = 28644.

Just use a simple lookup table for those 462 positions. I generate it at
startup of DIEP.

Reducing for checks like nalimov does you can get it down further.

"Benjamin Jordan" wrote in message
om...
(Werner Mühlpfordt) wrote in message
...
In article ,
Jonas Forsslund writes:
There are several ways ("representations") to combine symmetry
operations to yield the same reduction. Some of the
include rotations. But you will always end up with the same
two-dimensional point symmetry group. It has 8-fold symmetry
for the "normal" case, and 4-fold symmetry for diagonal fields

Sounds good to me. So just looking at arrangements (white with the
rook), there are 64*63*62 total, with 16*7*6 of them along diagonals
right?

Diag: WK*BK*WR
16* 7* 6 = 672

(WK*BK*WR - diag) / 8 + diag / 4
(64*63*62 - 672) / 8 + 672 / 4 = 31,332

To eliminate king-by-king positions, there are 4 corners where the WK
takes away 4 squares, 24 edge squares where he takes 6, and on the
remaining 36 squares he takes 9. On the diagonals, he has 4 corners
where he takes away 2, and 12 squares where he takes away 3:

Diag: 4*(8-2)*6 + 12*(8-3)*6 = 504 positions with only 4-fold symmetry

(4*(64-4)*62 + 24*(64-6)*62 + 36*(64-9)*62 - 504) / 8 + 504 / 4 =
28,056

Assuming that the computer played the game up to the position, it
shouldn't need to consider draw by repetition or 50-move rule, but
there would be the two additional positions where white has castling
rights (but would it matter?).

So I get 28,058 unique positions with Black to move. White to move is
a lot more complicated because any position where Black is in check by
the Rook would be illegal.

Benjamin Jordan

Thanks alot, I got the exact same numbers by calculating like this:
K-K is 3612 positions (identity)
on the two diagonal reflection there is 42.

so there is 1/8(3612+42+42) = 462 K-K as Diepeveen mentioned.

if we add a rook, the identity is 3612*62, and diagonal reflection is 42*6.

so we have 1/8(3612*62+42*6+42*6) = 28056

Nice :-)


Benjamin Jordan wrote:

(Werner Mühlpfordt) wrote in message
...
In article ,
Jonas Forsslund writes:
There are several ways ("representations") to combine symmetry
operations to yield the same reduction. Some of the
include rotations. But you will always end up with the same
two-dimensional point symmetry group. It has 8-fold symmetry
for the "normal" case, and 4-fold symmetry for diagonal fields

Sounds good to me. So just looking at arrangements (white with the
rook), there are 64*63*62 total, with 16*7*6 of them along diagonals
right?

Diag: WK*BK*WR
16* 7* 6 = 672

(WK*BK*WR - diag) / 8 + diag / 4
(64*63*62 - 672) / 8 + 672 / 4 = 31,332

To eliminate king-by-king positions, there are 4 corners where the WK
takes away 4 squares, 24 edge squares where he takes 6, and on the
remaining 36 squares he takes 9. On the diagonals, he has 4 corners
where he takes away 2, and 12 squares where he takes away 3:

Diag: 4*(8-2)*6 + 12*(8-3)*6 = 504 positions with only 4-fold symmetry

(4*(64-4)*62 + 24*(64-6)*62 + 36*(64-9)*62 - 504) / 8 + 504 / 4 =
28,056

Assuming that the computer played the game up to the position, it
shouldn't need to consider draw by repetition or 50-move rule, but
there would be the two additional positions where white has castling
rights (but would it matter?).

So I get 28,058 unique positions with Black to move. White to move is
a lot more complicated because any position where Black is in check by
the Rook would be illegal.

Benjamin Jordan

Hi
Is it for implemention purposes you stay with 28644 instead of 28056?
(28058 with o-o and o-o-o) The winning is not much, just curious.

For KNNK i would say we have
id = 3612*(62*61)/2 = 6830292
diagonal reflection = 52*(6*5)/2 + 42*28 = 1806

1/8( 6830292+1806+1806) = 854238 positions.

Jonas Forsslund




Vincent Diepeveen wrote:

Hi,

without pawns there is 462 king - king positions.

you can also mirror on the diagonal

i don't reduce for checks in diep.
egtb command (or help): list
NR NAME KEY #ENTRIES EXISTS (disk,ram)
1 kpk 00008000 84012 -- -- -- --
2 knk 00040000 28644 -- -- -- --
3 kbk 00200000 28644 -- -- -- --
4 krk 01000000 28644 -- -- -- --
5 kqk 08000000 28644 -- -- -- --
6 kppk 00010000 1912372 -- -- -- --
7 knpk 00048000 5124732 -- -- -- --
8 knnk 00080000 873642 -- -- -- --
9 kbpk 00208000 5124732 -- -- -- --
10 kbnk 00240000 1747284 -- -- -- --
11 kbbk 00400000 873642 -- -- -- --
12 krpk 01008000 5124732 -- -- -- --
13 krnk 01040000 1747284 -- -- -- --

That's why i have 28644 positions for KRK.


so if you reduce with symmetry and such then it's pretty small egtb.

62 * 462 = 28644.