Been doing a PERFT on Othello, using kogge-stone move generator. Not yet fully convinced my PERFT count is correct, but with a full minimax from start position to depth 10, and saving all nodes (leaf and internal), it counts 28030302.
Obviously some of these are non-unique, and cutting back to unique nodes only, the count is 13985937 (about 50%). I wasn't expecting so many duplicates - does anybody else have a similar PERFT and UNIQUE count?
Just for fun, and here's the naively unexpected bit, I added all reflections and rotations of these unique nodes. Count becomes 111887496, 8x more unsurprisingly. Then did the unique function on all these nodes, and unique count = 27778086, or about 2x the uniques from PERFT.
Why 2x? Well, not 8x because we already have the full possible legal move set in the original uniques, suggesting the reflections/rotations unique result should be 1x. So, why 2x? And why not exactly 2x?
Just how symmetrical is Othello?
Symmetry for 8x8 board games
Moderator: Ras
-
chrisw
- Posts: 4624
- Joined: Tue Apr 03, 2012 4:28 pm
- Location: Midi-Pyrénées
- Full name: Christopher Whittington
-
abulmo2
- Posts: 460
- Joined: Fri Dec 16, 2016 11:04 am
- Location: France
- Full name: Richard Delorme
Re: Symmetry for 8x8 board games
According to my engine Edax, here are the number for perft in Othello:
and the number of unique position, taking into account the 16 symmetries of the game:
For Othello, the symmetries are:
- vertical mirroring
- horizontal mirroring
- transposition (symetry % A1-H8 diagonal)
- color inversion: flip all the discs and change the color of the player to play.
When you combine all of them, you get the 16 symmetries.
For other depths, you can download Edax on my github account and try by yourself:
https://github.com/abulmo/edax-reversi
Code: Select all
$ edax -count games 10
A B C D E F G H
1 - - - - - - - - 1
2 - - - - - - - - 2 * to move
3 - - - . - - - - 3
4 - - . O * - - - 4 *: discs = 2 moves = 4
5 - - - * O . - - 5 O: discs = 2 moves = 4
6 - - - - . - - - 6 empties = 60 ply = 1
7 - - - - - - - - 7
8 - - - - - - - - 8
A B C D E F G H
ply moves passes wins draws losses mobility time speed
------------------------------------------------------------------------------------------------------------------
1, 4, 0, 0, 0, 0, 4 - 4, 0:00.000, 5.0 Kmoves/s, (h_tries = 0, h_hits = 0)
2, 12, 0, 0, 0, 0, 3 - 3, 0:00.000, 17.0 Kmoves/s, (h_tries = 0, h_hits = 0)
3, 56, 0, 0, 0, 0, 4 - 5, 0:00.000, 73.0 Kmoves/s, (h_tries = 1, h_hits = 0)
4, 244, 0, 0, 0, 0, 2 - 6, 0:00.000, 317.0 Kmoves/s, (h_tries = 5, h_hits = 3)
5, 1396, 0, 0, 0, 0, 3 - 9, 0:00.000, 1.713 Mmoves/s, (h_tries = 8, h_hits = 3)
6, 8200, 0, 0, 0, 0, 1 - 11, 0:00.000, 9.913 Mmoves/s, (h_tries = 22, h_hits = 3)
7, 55092, 0, 0, 0, 0, 2 - 12, 0:00.000, 65.0 Mmoves/s, (h_tries = 83, h_hits = 4)
8, 390216, 0, 0, 0, 0, 1 - 14, 0:00.000, 455.2 Mmoves/s, (h_tries = 423, h_hits = 22)
9, 3005288, 24, 0, 0, 0, 0 - 15, 0:00.002, 1.154 Gmoves/s, (h_tries = 2316, h_hits = 142)
10, 24571056, 0, 0, 0, 228, 0 - 16, 0:00.014, 1.869 Gmoves/s, (h_tries = 14222, h_hits = 1399)
Total 28031565
------------------------------------------------------------------------------------------------------------------
Code: Select all
$ edax -count positions 10
A B C D E F G H
1 - - - - - - - - 1
2 - - - - - - - - 2 * to move
3 - - - . - - - - 3
4 - - . O * - - - 4 *: discs = 2 moves = 4
5 - - - * O . - - 5 O: discs = 2 moves = 4
6 - - - - . - - - 6 empties = 60 ply = 1
7 - - - - - - - - 7
8 - - - - - - - - 8
A B C D E F G H
discs nodes total time speed
----------------------------------------------------------
4, 1, 1, 0:00.000, 1.0 KN/s
5, 1, 2, 0:00.000, 2.0 KN/s
6, 3, 5, 0:00.000, 5.0 KN/s
7, 14, 19, 0:00.000, 19.0 KN/s
8, 60, 79, 0:00.000, 79.0 KN/s
9, 322, 401, 0:00.000, 401.0 KN/s
10, 1773, 2174, 0:00.000, 2.174 MN/s
11, 10649, 12823, 0:00.004, 2.565 MN/s
12, 67245, 80068, 0:00.024, 3.203 MN/s
13, 434029, 514097, 0:00.168, 3.042 MN/s
14, 2958586, 3472683, 0:01.227, 2.828 MN/s
----------------------------------------------------------
- vertical mirroring
- horizontal mirroring
- transposition (symetry % A1-H8 diagonal)
- color inversion: flip all the discs and change the color of the player to play.
When you combine all of them, you get the 16 symmetries.
For other depths, you can download Edax on my github account and try by yourself:
https://github.com/abulmo/edax-reversi
Richard Delorme
-
chesskobra
- Posts: 347
- Joined: Thu Jul 21, 2022 12:30 am
- Full name: Chesskobra
Re: Symmetry for 8x8 board games
I have an explanation for the 'about (but not exactly) 2x' positions in your counting. I think this is what is happening.
When you apply reflections or rotations to the start position, you get 2 distinct positions (one is the 'official position' with north-west and south-east central squares lite and the other two central squares dark, and the other position (let us call it the unofficial position) with the colours of central squares reversed ). If you produce game trees from these two positions, the two trees would have some common positions, which is why you get fewer than twice unique positions. You may want to check this for 3-4 plies.
A side comment about the term 'symmetries'. In algebra we talk about a group G acting on a set X. (Here G is the dihedral group with 8 elements (obtained from rotations and reflections of a square) and the set X is the set of positions. The group action defines what happens to an element x when acted upon by a group element g (we may write xg = y). In case of Othello positions, for very few positions x we have some g for which xg = x, but for most positions, we have xg = y that is different from x. The set of elements g that fix x is a subgroup of G (called the stabilizer subgroup of x). For most positions, the stabilizer subgroup is trivial. This may be called the group of symmetries of x. For example, the stabilizer of the official start position has 4 elements. On the other hand, you may consider the set {xg | g in G} for a given element x. It is called the orbit of x. Orbit of the official position has 2 elements (the official start position and the unofficial start position). We have, for all x in X, the number of elements in the orbit of x times the number of stabilizers of x = the number of elements in the group, i.e., |Stab(x)| |Orbit(x)| = |G|. So if the stabilizer of an element is trivial, its orbit would have |G| elements. This is the case for most Othello positions.
When you apply reflections or rotations to the start position, you get 2 distinct positions (one is the 'official position' with north-west and south-east central squares lite and the other two central squares dark, and the other position (let us call it the unofficial position) with the colours of central squares reversed ). If you produce game trees from these two positions, the two trees would have some common positions, which is why you get fewer than twice unique positions. You may want to check this for 3-4 plies.
A side comment about the term 'symmetries'. In algebra we talk about a group G acting on a set X. (Here G is the dihedral group with 8 elements (obtained from rotations and reflections of a square) and the set X is the set of positions. The group action defines what happens to an element x when acted upon by a group element g (we may write xg = y). In case of Othello positions, for very few positions x we have some g for which xg = x, but for most positions, we have xg = y that is different from x. The set of elements g that fix x is a subgroup of G (called the stabilizer subgroup of x). For most positions, the stabilizer subgroup is trivial. This may be called the group of symmetries of x. For example, the stabilizer of the official start position has 4 elements. On the other hand, you may consider the set {xg | g in G} for a given element x. It is called the orbit of x. Orbit of the official position has 2 elements (the official start position and the unofficial start position). We have, for all x in X, the number of elements in the orbit of x times the number of stabilizers of x = the number of elements in the group, i.e., |Stab(x)| |Orbit(x)| = |G|. So if the stabilizer of an element is trivial, its orbit would have |G| elements. This is the case for most Othello positions.
-
chrisw
- Posts: 4624
- Joined: Tue Apr 03, 2012 4:28 pm
- Location: Midi-Pyrénées
- Full name: Christopher Whittington
Re: Symmetry for 8x8 board games
Thanks for those. My search matches exactly, but the PERFT didn't (forgot to include "pass" in the PERFT), now fixed.abulmo2 wrote: ↑Mon Feb 17, 2025 9:02 am According to my engine Edax, here are the number for perft in Othello:and the number of unique position, taking into account the 16 symmetries of the game:Code: Select all
$ edax -count games 10 A B C D E F G H 1 - - - - - - - - 1 2 - - - - - - - - 2 * to move 3 - - - . - - - - 3 4 - - . O * - - - 4 *: discs = 2 moves = 4 5 - - - * O . - - 5 O: discs = 2 moves = 4 6 - - - - . - - - 6 empties = 60 ply = 1 7 - - - - - - - - 7 8 - - - - - - - - 8 A B C D E F G H ply moves passes wins draws losses mobility time speed ------------------------------------------------------------------------------------------------------------------ 1, 4, 0, 0, 0, 0, 4 - 4, 0:00.000, 5.0 Kmoves/s, (h_tries = 0, h_hits = 0) 2, 12, 0, 0, 0, 0, 3 - 3, 0:00.000, 17.0 Kmoves/s, (h_tries = 0, h_hits = 0) 3, 56, 0, 0, 0, 0, 4 - 5, 0:00.000, 73.0 Kmoves/s, (h_tries = 1, h_hits = 0) 4, 244, 0, 0, 0, 0, 2 - 6, 0:00.000, 317.0 Kmoves/s, (h_tries = 5, h_hits = 3) 5, 1396, 0, 0, 0, 0, 3 - 9, 0:00.000, 1.713 Mmoves/s, (h_tries = 8, h_hits = 3) 6, 8200, 0, 0, 0, 0, 1 - 11, 0:00.000, 9.913 Mmoves/s, (h_tries = 22, h_hits = 3) 7, 55092, 0, 0, 0, 0, 2 - 12, 0:00.000, 65.0 Mmoves/s, (h_tries = 83, h_hits = 4) 8, 390216, 0, 0, 0, 0, 1 - 14, 0:00.000, 455.2 Mmoves/s, (h_tries = 423, h_hits = 22) 9, 3005288, 24, 0, 0, 0, 0 - 15, 0:00.002, 1.154 Gmoves/s, (h_tries = 2316, h_hits = 142) 10, 24571056, 0, 0, 0, 228, 0 - 16, 0:00.014, 1.869 Gmoves/s, (h_tries = 14222, h_hits = 1399) Total 28031565 ------------------------------------------------------------------------------------------------------------------For Othello, the symmetries are:Code: Select all
$ edax -count positions 10 A B C D E F G H 1 - - - - - - - - 1 2 - - - - - - - - 2 * to move 3 - - - . - - - - 3 4 - - . O * - - - 4 *: discs = 2 moves = 4 5 - - - * O . - - 5 O: discs = 2 moves = 4 6 - - - - . - - - 6 empties = 60 ply = 1 7 - - - - - - - - 7 8 - - - - - - - - 8 A B C D E F G H discs nodes total time speed ---------------------------------------------------------- 4, 1, 1, 0:00.000, 1.0 KN/s 5, 1, 2, 0:00.000, 2.0 KN/s 6, 3, 5, 0:00.000, 5.0 KN/s 7, 14, 19, 0:00.000, 19.0 KN/s 8, 60, 79, 0:00.000, 79.0 KN/s 9, 322, 401, 0:00.000, 401.0 KN/s 10, 1773, 2174, 0:00.000, 2.174 MN/s 11, 10649, 12823, 0:00.004, 2.565 MN/s 12, 67245, 80068, 0:00.024, 3.203 MN/s 13, 434029, 514097, 0:00.168, 3.042 MN/s 14, 2958586, 3472683, 0:01.227, 2.828 MN/s ----------------------------------------------------------
- vertical mirroring
- horizontal mirroring
- transposition (symetry % A1-H8 diagonal)
- color inversion: flip all the discs and change the color of the player to play.
When you combine all of them, you get the 16 symmetries.
For other depths, you can download Edax on my github account and try by yourself:
https://github.com/abulmo/edax-reversi
We are using the term unique differently. Hence the unique count mismatch. I think you define it Unique=any match formed by any board symmetry. Whereas mine is: Unique=any match with any other board. So you find many more "symmetries". Yours is better of course.
Did you manage to find a way to include symmetries to reduce the tree size?
-
chrisw
- Posts: 4624
- Joined: Tue Apr 03, 2012 4:28 pm
- Location: Midi-Pyrénées
- Full name: Christopher Whittington
Re: Symmetry for 8x8 board games
Yes, that's what I figured too. It seems to imply that the unofficial positions are not reachable by search from the start position. Does that figure?chesskobra wrote: ↑Mon Feb 17, 2025 11:48 am I have an explanation for the 'about (but not exactly) 2x' positions in your counting. I think this is what is happening.
When you apply reflections or rotations to the start position, you get 2 distinct positions (one is the 'official position' with north-west and south-east central squares lite and the other two central squares dark, and the other position (let us call it the unofficial position) with the colours of central squares reversed ). If you produce game trees from these two positions, the two trees would have some common positions, which is why you get fewer than twice unique positions. You may want to check this for 3-4 plies.
A side comment about the term 'symmetries'. In algebra we talk about a group G acting on a set X. (Here G is the dihedral group with 8 elements (obtained from rotations and reflections of a square) and the set X is the set of positions. The group action defines what happens to an element x when acted upon by a group element g (we may write xg = y). In case of Othello positions, for very few positions x we have some g for which xg = x, but for most positions, we have xg = y that is different from x. The set of elements g that fix x is a subgroup of G (called the stabilizer subgroup of x). For most positions, the stabilizer subgroup is trivial. This may be called the group of symmetries of x. For example, the stabilizer of the official start position has 4 elements. On the other hand, you may consider the set {xg | g in G} for a given element x. It is called the orbit of x. Orbit of the official position has 2 elements (the official start position and the unofficial start position). We have, for all x in X, the number of elements in the orbit of x times the number of stabilizers of x = the number of elements in the group, i.e., |Stab(x)| |Orbit(x)| = |G|. So if the stabilizer of an element is trivial, its orbit would have |G| elements. This is the case for most Othello positions.
-
chrisw
- Posts: 4624
- Joined: Tue Apr 03, 2012 4:28 pm
- Location: Midi-Pyrénées
- Full name: Christopher Whittington
Re: Symmetry for 8x8 board games
Thinking a bit more on this .....abulmo2 wrote: ↑Mon Feb 17, 2025 9:02 am According to my engine Edax, here are the number for perft in Othello:and the number of unique position, taking into account the 16 symmetries of the game:Code: Select all
$ edax -count games 10 A B C D E F G H 1 - - - - - - - - 1 2 - - - - - - - - 2 * to move 3 - - - . - - - - 3 4 - - . O * - - - 4 *: discs = 2 moves = 4 5 - - - * O . - - 5 O: discs = 2 moves = 4 6 - - - - . - - - 6 empties = 60 ply = 1 7 - - - - - - - - 7 8 - - - - - - - - 8 A B C D E F G H ply moves passes wins draws losses mobility time speed ------------------------------------------------------------------------------------------------------------------ 1, 4, 0, 0, 0, 0, 4 - 4, 0:00.000, 5.0 Kmoves/s, (h_tries = 0, h_hits = 0) 2, 12, 0, 0, 0, 0, 3 - 3, 0:00.000, 17.0 Kmoves/s, (h_tries = 0, h_hits = 0) 3, 56, 0, 0, 0, 0, 4 - 5, 0:00.000, 73.0 Kmoves/s, (h_tries = 1, h_hits = 0) 4, 244, 0, 0, 0, 0, 2 - 6, 0:00.000, 317.0 Kmoves/s, (h_tries = 5, h_hits = 3) 5, 1396, 0, 0, 0, 0, 3 - 9, 0:00.000, 1.713 Mmoves/s, (h_tries = 8, h_hits = 3) 6, 8200, 0, 0, 0, 0, 1 - 11, 0:00.000, 9.913 Mmoves/s, (h_tries = 22, h_hits = 3) 7, 55092, 0, 0, 0, 0, 2 - 12, 0:00.000, 65.0 Mmoves/s, (h_tries = 83, h_hits = 4) 8, 390216, 0, 0, 0, 0, 1 - 14, 0:00.000, 455.2 Mmoves/s, (h_tries = 423, h_hits = 22) 9, 3005288, 24, 0, 0, 0, 0 - 15, 0:00.002, 1.154 Gmoves/s, (h_tries = 2316, h_hits = 142) 10, 24571056, 0, 0, 0, 228, 0 - 16, 0:00.014, 1.869 Gmoves/s, (h_tries = 14222, h_hits = 1399) Total 28031565 ------------------------------------------------------------------------------------------------------------------For Othello, the symmetries are:Code: Select all
$ edax -count positions 10 A B C D E F G H 1 - - - - - - - - 1 2 - - - - - - - - 2 * to move 3 - - - . - - - - 3 4 - - . O * - - - 4 *: discs = 2 moves = 4 5 - - - * O . - - 5 O: discs = 2 moves = 4 6 - - - - . - - - 6 empties = 60 ply = 1 7 - - - - - - - - 7 8 - - - - - - - - 8 A B C D E F G H discs nodes total time speed ---------------------------------------------------------- 4, 1, 1, 0:00.000, 1.0 KN/s 5, 1, 2, 0:00.000, 2.0 KN/s 6, 3, 5, 0:00.000, 5.0 KN/s 7, 14, 19, 0:00.000, 19.0 KN/s 8, 60, 79, 0:00.000, 79.0 KN/s 9, 322, 401, 0:00.000, 401.0 KN/s 10, 1773, 2174, 0:00.000, 2.174 MN/s 11, 10649, 12823, 0:00.004, 2.565 MN/s 12, 67245, 80068, 0:00.024, 3.203 MN/s 13, 434029, 514097, 0:00.168, 3.042 MN/s 14, 2958586, 3472683, 0:01.227, 2.828 MN/s ----------------------------------------------------------
- vertical mirroring
- horizontal mirroring
- transposition (symetry % A1-H8 diagonal)
- color inversion: flip all the discs and change the color of the player to play.
When you combine all of them, you get the 16 symmetries.
For other depths, you can download Edax on my github account and try by yourself:
https://github.com/abulmo/edax-reversi
with a low stone count on the board the number of actual unique moves is very low, with branching factor 1, but as soon as the board begins to fill, the unique move count from any node tends to equal the actual legal move count. Which implies that trying to use symmetry to reduce branching factor rapidly fails to give any gains. Does that figure?
-
chesskobra
- Posts: 347
- Joined: Thu Jul 21, 2022 12:30 am
- Full name: Chesskobra
Re: Symmetry for 8x8 board games
Yes. Since your number of unique positions is close to twice the number for official, it seems that there is only a small fraction of positions that are reachable from both official and unofficial starting position.
-
abulmo2
- Posts: 460
- Joined: Fri Dec 16, 2016 11:04 am
- Location: France
- Full name: Richard Delorme
Re: Symmetry for 8x8 board games
In Edax's opening book, I include all symmetries to reduce the size of the opening book. During the search, only the color inversion is taken into account at no price, as the structure to store the position is color blind. As you noticed the symmetries reduce a lot the tree size at the start of the game, but once a move is played it is more unlikely to get symmetrical positions during the search.
Richard Delorme
-
chrisw
- Posts: 4624
- Joined: Tue Apr 03, 2012 4:28 pm
- Location: Midi-Pyrénées
- Full name: Christopher Whittington
Re: Symmetry for 8x8 board games
For game play that figures, but if one wants an opening book that would give largest possible test games by autoplay (tuning or NN development), isn’t it best to have the full book with all symmetrical positions included to give widest coverage?abulmo2 wrote: ↑Mon Feb 17, 2025 5:20 pmIn Edax's opening book, I include all symmetries to reduce the size of the opening book. During the search, only the color inversion is taken into account at no price, as the structure to store the position is color blind. As you noticed the symmetries reduce a lot the tree size at the start of the game, but once a move is played it is more unlikely to get symmetrical positions during the search.
-
abulmo2
- Posts: 460
- Joined: Fri Dec 16, 2016 11:04 am
- Location: France
- Full name: Richard Delorme
Re: Symmetry for 8x8 board games
I do not think so. It would be very easy to develop all symmetrical positions of an opening book, but this will give redundant information.
Richard Delorme