I recently stumbled upon a blog post by Alejandra González (a.k.a @blyxyas) that seeks to compress a tic-tac-toe game state into as few bits as possible. She arrived at a solution in 18 bits. This got me thinking, can we do better?
  • glibg10b@lemmy.ml
    1·
    3 years ago

    15 bits is possible if you encode the state in base-3, where each digit represents one of the cells

  • glibg10b@lemmy.ml
    1·
    3 years ago

    Base-3: 15 bits
    Legal states only: 13 bits
    Redundancy due to symmetry eliminated: 12 bits
    Combining the previous two: I estimate 10 bits

  • cbarrick@lemmy.worldOPEnglish
    11·
    3 years ago

    OP here! People are rightfully pointing out that this can be compressed further.

    My challenge to you: Implement a compressed representation along with the get_cell and set_cell methods, without resorting to lookup tables!

    Also, check out Alejandra’s blog at https://goose.love/!

    (And yeah, you need 12 or 13 bits, not 10, if you don’t want to eliminate symmetries.)