3 ms·

There’s further you can go — e.g. by taking advantage of the turn-based nature (there won’t ever be 4 Xs and two Os). Can save almost another bit by assuming X

There’s further you can go — e.g. by taking advantage of the turn-based nature (there won’t ever be 4 Xs and two Os). Can save almost another bit by assuming X always goes first.

munificent 3y ago
> by taking advantage of the turn-based nature (there won’t ever be 4 Xs and two Os). Also by discarding any boards that are only reachable after some winning solution. Honestly, the most efficient solution is probably to enumerate all valid reachable board states, and then just encode them in a look-up table. It's a tiny game. Damn it, I nerd sniped myself. After hacking together a little program, it looks like there's 5,620 valid reachable board states, so 13 bits is enough to encode them all.
- tyingq 3y ago
  Might be an interesting exercise to see why some people get 5477, and you're getting 5,620: https://stackoverflow.com/questions/7466429/generate-a-list-of-all-unique-tic-tac-toe-boards https://stackoverflow.com/questions/7466429/generate-a-list-...
  - munificent 3y ago
    Huh, dunno. Probably a dumb bug in my hacky script.
  - penwielder 3y ago
    This sounded like an interesting puzzle to me. I doubt it's the only way, but I arrive at 5620 if I both count the empty position and leave out detection of diagonal wins.
    - munificent 3y ago
      Ah, you're right. I had a bug in the code to detect diagonal wins. With that fixed, I get 5,478 unique reachable boards.
      - deleted 3y ago
        [deleted]
- Supermancho 3y ago
  > Also by discarding any boards that are only reachable after some winning solution. In tic tac toe, I'm not sure there is a such a board. The information being encoded does not track order of play. Any board could be formed with the final move being the center to win?
  - munificent 3y ago
    Yes, there are definitely boards with multiple winning solutions. But you should never see a valid board that has winning solutions for both players or that has multiple disjoint winning solutions.
  - masfuerte 3y ago
    If a single player has two winning lines then they must have a cell in common, and that could be played last. But a board where both players have a winning line is unreachable: XXX OOO XOX

There’s further you can go — e.g. by taking advantage of the turn-based nature (there won’t ever be 4 Xs and two Os). Can save almost another bit by assuming X always goes first.

munificent 3y ago

> by taking advantage of the turn-based nature (there won’t ever be 4 Xs and two Os). Also by discarding any boards that are only reachable after some winning solution. Honestly, the most efficient solution is probably to enumerate all valid reachable board states, and then just encode them in a look-up table. It's a tiny game. Damn it, I nerd sniped myself. After hacking together a little program, it looks like there's 5,620 valid reachable board states, so 13 bits is enough to encode them all.

tyingq 3y ago
Might be an interesting exercise to see why some people get 5477, and you're getting 5,620: https://stackoverflow.com/questions/7466429/generate-a-list-of-all-unique-tic-tac-toe-boards https://stackoverflow.com/questions/7466429/generate-a-list-...
- munificent 3y ago
  Huh, dunno. Probably a dumb bug in my hacky script.
- penwielder 3y ago
  This sounded like an interesting puzzle to me. I doubt it's the only way, but I arrive at 5620 if I both count the empty position and leave out detection of diagonal wins.
  - munificent 3y ago
    Ah, you're right. I had a bug in the code to detect diagonal wins. With that fixed, I get 5,478 unique reachable boards.
    - deleted 3y ago
      [deleted]
Supermancho 3y ago
> Also by discarding any boards that are only reachable after some winning solution. In tic tac toe, I'm not sure there is a such a board. The information being encoded does not track order of play. Any board could be formed with the final move being the center to win?
- munificent 3y ago
  Yes, there are definitely boards with multiple winning solutions. But you should never see a valid board that has winning solutions for both players or that has multiple disjoint winning solutions.
- masfuerte 3y ago
  If a single player has two winning lines then they must have a cell in common, and that could be played last. But a board where both players have a winning line is unreachable: XXX OOO XOX