4 ms·

> As Alejandra points out, there are 765 possible game states. We could simply assign a number to all of the states, which would take up 10 bits Looking at the

by llimos 3y ago

> As Alejandra points out, there are 765 possible game states. We could simply assign a number to all of the states, which would take up 10 bits Looking at the linked paper, 765 is after deduplicating the same state rotated. In a real game, you would need to know which orientation is used, so you'd need a couple of extra bits for that.

johnfn 3y ago
> couple of extra bits Two?
- yjftsjthsd-h 3y ago
  There are four ways to rotate, so yes exactly two bits, right?
  - Nevermark 3y ago
    Plus a third bit for rotationally flipped. I.e., [O X -] [- - -] [- - -] can be rotated 90 degrees 4 times (2 bits) to return to the same arrangement. It can also be rotationally flipped 2 times (1 bit), clockwise <--> counter-clockwise, to return again. With the dual state for the above non-rotated original: [O - -] [X - -] [- - -] So three bits to extract symmetry (or recreated the broken symmetry) But ... some arrangements have instance symmetry where only 1 bit of rotation symmetry is needed, and no rotation-flips: [O - X] [- - -] [X - O] So sometimes 3 bits of symmetry will contain redundant information. (i.e. rotations 0 and 2, and rotations 1 and 3, look the same. Rotation flip changes nothing. And this field requires 0 symmetry bits, as all rotations and flips are identities (1 step to return = 0 bits) [- - -] [- X -] [- - -] A representation that always uses the minimum number of bits but has a straightforward relationship to the actual playing field is illusive
    - pavon 3y ago
      And that double-counts board layouts that are symmetric. Digging through the references led me to this page[1] which has a nice discussion on different ways to compute the number of states. Without symmetry you have 5478 possible board states, which is less than the 6120 you would get by adding rotation/flip bits to the 765 states. Both require 13 bits though. Too bad, I was hoping it would fit into a 12-bit PDP-8 word :) [1]https://web.archive.org/web/20020513063952/http://www.mathrec.org/old/2002jan/solutions.html https://web.archive.org/web/20020513063952/http://www.mathre...

by llimos 3y ago

johnfn 3y ago

> couple of extra bits Two?

yjftsjthsd-h 3y ago
There are four ways to rotate, so yes exactly two bits, right?
- Nevermark 3y ago
  Plus a third bit for rotationally flipped. I.e., [O X -] [- - -] [- - -] can be rotated 90 degrees 4 times (2 bits) to return to the same arrangement. It can also be rotationally flipped 2 times (1 bit), clockwise <--> counter-clockwise, to return again. With the dual state for the above non-rotated original: [O - -] [X - -] [- - -] So three bits to extract symmetry (or recreated the broken symmetry) But ... some arrangements have instance symmetry where only 1 bit of rotation symmetry is needed, and no rotation-flips: [O - X] [- - -] [X - O] So sometimes 3 bits of symmetry will contain redundant information. (i.e. rotations 0 and 2, and rotations 1 and 3, look the same. Rotation flip changes nothing. And this field requires 0 symmetry bits, as all rotations and flips are identities (1 step to return = 0 bits) [- - -] [- X -] [- - -] A representation that always uses the minimum number of bits but has a straightforward relationship to the actual playing field is illusive
  - pavon 3y ago
    And that double-counts board layouts that are symmetric. Digging through the references led me to this page[1] which has a nice discussion on different ways to compute the number of states. Without symmetry you have 5478 possible board states, which is less than the 6120 you would get by adding rotation/flip bits to the 765 states. Both require 13 bits though. Too bad, I was hoping it would fit into a 12-bit PDP-8 word :) [1]https://web.archive.org/web/20020513063952/http://www.mathrec.org/old/2002jan/solutions.html https://web.archive.org/web/20020513063952/http://www.mathre...