[HN Gopher] Encoding tic-tac-toe in 15 bits
___________________________________________________________________
Encoding tic-tac-toe in 15 bits
Author : thunderbong
Score : 93 points
Date : 2024-02-21 16:48 UTC (6 hours ago)
(HTM) web link (cbarrick.dev)
(TXT) w3m dump (cbarrick.dev)
| mcraiha wrote:
| Scary part is that I had this exact idea yesterday. My plan was
| to create a graph where I can see all the possible "legal"
| transitions between board states.
| shmageggy wrote:
| Not every transition, but all of the optimal ones
| https://xkcd.com/832/
| thatnerdyguy wrote:
| I hadn't seen this before. Thanks for posting! My 8 year old
| will get a kick out of this!
| jerf wrote:
| This was a homework assignment in AI class in college.
| Explicitly stated that you had to do it with pencil and paper.
| Probably the ugliest homework problem I've ever handed in,
| since I did not correctly guess how wide it would get. Should
| have used the paper in landscape mode.
|
| However, upshot, taking account of the symmetries, this is
| doable on a single sheet of paper, though I'd suggest making
| the board smaller than you may initially think.
| h2odragon wrote:
| my first thought is represent rows instead of cells
| nickcw wrote:
| A very long time ago I used the idea that there aren't actually
| that many possible tic-tac-toe boards to make an HTML player that
| is just static web pages
|
| https://www.craig-wood.com/nick/oxo2d/
|
| I generated this with a C program that tried to minimise the
| number of boards. There are 427 pages including the index.
|
| This has been through quite a few revisions of my website and I
| lost the source to the C program so it remains a historical
| artifact only!
| kej wrote:
| That reminds me of a former coworker who wrote a paperback
| version of the game Nim (the math game where you remove
| sticks). It worked like a choose your own adventure where each
| possible move had a page number to jump to.
| abecedarius wrote:
| Since your C is lost here's Python code in an old article of
| mine: https://codewords.recurse.com/issues/four/the-language-
| of-ch... -- at least it gave the same number 427.
|
| (About halfway down the page. It's as an example application of
| binary decision diagrams.)
| ngcc_hk wrote:
| Totally lost when you use python to define a domain specific
| language. Cannot get that most quoted paper and its idea. I
| wonder whether a lisp based one would be better. Please no C
| as well.
| jgrahamc wrote:
| Oh man. This brought back memories. Back in 2007, I did this by
| embedding clickable boards in Reddit comments, with all the
| comments linked together. The idea was "playable tic-tac-toe
| inside Reddit comments". Reddit had to kill my account because
| the process doing comment indexing was blowing up.
|
| But, hey, Steve Huffman sent me a Reddit sticker!
| gumby wrote:
| Seems appropriate given that a Huffman code is a compression
| strategy.
| Biganon wrote:
| There's a book version of tic tac toe
|
| Every page is a grid state and each cell contains the number of
| the page you're supposed to go to if you pick this cell
| pimlottc wrote:
| This is a great example of how you can trade time for space.
| There's no reason you couldn't do the same thing for chess,
| except it would take, er, quite a bit of disk space...
| ithkuil wrote:
| there are even more possible variations of chess games than
| there are atoms in the observable universe.
| pimlottc wrote:
| Yeah, I'd definitely have to delete some old emails.
| koliber wrote:
| For something slightly more practical here's a printable PDF
| representation of googolplex:
| http://www.googolplexwrittenout.com/
| cpach wrote:
| I remember that 'idlewords once ran out of disk space on
| his server because a Pinboard user bookmarked some page
| that had written out a very large number (googolplex or
| similar) and the archived HTML was something like 50 GB or
| so :)
|
| (I don't remember the exact details now so take it with a
| grain of salt.)
| reaperman wrote:
| Is there an inaccuracy for https://www.craig-
| wood.com/nick/oxo2d/b2/ ?
|
| I believe the optimal response to: X . .
| . O . . . .
|
| Should be X . . . O . . . X
|
| Which offers a reasonable opportunity for "O" to mess up by
| choosing a corner. But instead your script plays
| X X . . O . . . .
|
| Which guides the human player to reflexively counter accurately
| without thinking.
| fhars wrote:
| There is a tic-tac-toe system that learns to play using
| reinforcement learning built of matchboxes. Designed in 1961.
| https://en.wikipedia.org/wiki/Matchbox_Educable_Noughts_and_...
| llimos wrote:
| > 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 wrote:
| > couple of extra bits
|
| Two?
| yjftsjthsd-h wrote:
| There are four ways to rotate, so yes exactly two bits,
| right?
| Nevermark wrote:
| 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 wrote:
| 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.
| mathre...
| npinsker wrote:
| 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 wrote:
| _> 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 wrote:
| 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-...
| munificent wrote:
| Huh, dunno. Probably a dumb bug in my hacky script.
| Supermancho wrote:
| > 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?
| taeric wrote:
| I think it would be fun to explore the 10 bit idea a bit more.
| Yes, you would have to have more code to work with it; but that
| is exactly what would be fun to explore.
|
| That is, I'd love to see an exploration of how big both the
| encoding and the executing program are and how they play against
| each other. As others have already noted, you could skip the
| encoding of the board as a "first class" piece of data and
| instead have a large program where the state of the board is
| implied by where in the code you are. In a sense, this is a
| complete minimization of the board's encoding and should result
| in a maximal sized code.
|
| It would be fun to plot how these two values interact with each
| other.
| nneonneo wrote:
| > Technically, we need 9.58 bits, but there is no good way to use
| that final fraction of a bit.
|
| Huffman or arithmetic coding can pretty easily provide that
| "fraction" of a bit, at the cost of making decoding more
| expensive (and not random access).
| Gare wrote:
| You could code the whole game sequence in only 22 bits.
|
| First bit to mark whether X or O starts, then 4 bits for the
| placement of the first symbol (9 empty squares numbered 0-8
| counting from top left), then only 3 bits for the second one (one
| square is already taken so there are only 8 possible positions
| left), etc. which gives us 4+3+3+3+3+2+2+1 = 21 bits for the 8
| moves before there is only one unfilled square left.
| thechao wrote:
| You could use a divider and just encode it in log(9!)/log(2) ~
| 19b? I think the point of the article is you can encode _every_
| game in something like a kilobyte of data, though, right?
| brandonpelfrey wrote:
| I'm fairly certain the entire game can be encoded in 16 bits.
| Thinking through this now. There are much less than 9! Games
| if you only include valid moves and actually end games that
| have three in a row. This is also before any symmetries are
| used.
| zokier wrote:
| To be able to represent arbitrary game states, do you need 3
| more bits to indicate the turn number? 19 bits works only if
| represent complete finished games, but not for in-progress
| games? So we are back to 22 bits
| notorandit wrote:
| 10 bits encoding is the way to go. The problem is that you want
| something human readable. This is basically wrong if the aim is
| efficiency. It will be the program to expand the infornation in a
| human readable form.
| cbarrick wrote:
| 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.)
| kqr wrote:
| I thought the point of the article (actual working
| implementations) was fairly obvious, and I'm sorry to see
| people miss it!
| Someone wrote:
| > without resorting to lookup tables!
|
| I don't see how that makes a difference. You can always replace
| a lookup table by code, for example: a = [832,
| 54, 743]
|
| vs func a(i) = if i = 0 return 832
| if i = 1 return 54 return 743
|
| The classic example of this are the definitions of _cons_ ,
| _car_ and _cdr_ in SICP as lambdas: (define
| (cons x y) (lambda (m) (m x y))) (define
| (car z) (z (lambda (p q) p))) (define (cdr
| z) (z (lambda (p q) q)))
|
| See https://stackoverflow.com/a/21769444 for an explanation.
|
| For pure functions taking finite inputs, the reverse is
| possible, too. For example, you can define _and_ on booleans as
| a 2 x 2 array and = [[false, false], [false,
| true]]
|
| and then do a _and[x, y]_ lookup to evaluate it. That's why
| some functional languages (for example scala) do not make a
| distinction between array indexing, hash table lookups, and
| function calls. After all, they all are mathematical functions
| taking a single value and producing one.
|
| I think I would judge solutions not on avoiding lookup tables,
| but on size of the encoding and, for programs that produce
| equal size encodings, the total number of bytes in the
| programs, using "less is better" as criterion for both.
| cbarrick wrote:
| I would consider an if-chain to be a lookup table. A
| sufficiently smart compiler would treat it as one.
|
| I agree that the challenge isn't rigorously defined. But the
| spirit is to not allow this kind of trick.
| kamens wrote:
| There's a really fun toy example of genetic algorithms that uses
| this compact representation of tictactoe gamestate (encoding each
| game into a concatenated list of ternary states, of which there
| are 19,682 possible values if completely unoptimized):
|
| Consider a "genome" for a tictactoe player to be a 19,682-long
| array that holds "next moves" at each slot in the array. For any
| given gamestate, look up the player's next move via their genome.
|
| Randomize genomes originally. Make tons of them. Compete w/ each
| other, then play around with all sorts of fun mating/mutation
| strategies for swapping different moves between genomes.
|
| Fun to see a perfect tictactoe player evolve, super approachable
| toy example.
| scottlamb wrote:
| > Is this any better? It depends, but probably not. ... But if
| you had some wild application where you needed to keep trillions
| of game states unpacked [1] in memory, then sure, use base-3.
|
| I think I'd want to represent those trillions of game states in
| the the 10-bit representation it mentioned earlier and keep
| around a uint32_t[765] to map that to the more practical 18-bit
| version. (or rather something like 13-bit and uint32_t[5477]
| because llimos pointed out that the 765 is after rotation.)
|
| [1] I think the word "unpacked" here is just carelessly chosen
| rather than a contrast to the "pack them tightly using 18 bits
| for the base-4 representation or 15 bits for the base-3
| representation" in the paragraph I elided.
| p4bl0 wrote:
| There are only 5478 game states (without even taking symmetries
| into account), so 13 bits should be enough actually.
|
| I did something like this a while ago here, to produce the
| smallest possible implementation of the game in pure HTML:
| https://code.up8.edu/-/snippets/6
| notfed wrote:
| > We could simply assign a number to all of the s[t]ates, which
| would take up 10 bits. [But] in practice we're going to need a
| lookup table to map each number to a larger, more structured
| representation, which defeats the whole idea behind a [10 bit]
| compressed representation
|
| Maybe? What if you brute forced a block cipher to encode/decode
| each 10-bit mapping into the raw 15-bit mapping (i.e., a 9-digit
| base-3 number).
|
| It may take some crunching to find it, but only once. Maybe
| someone else can tell me how feasible this is.
| Nevermark wrote:
| The game can be super condensed if both players are assumed to
| play optimally.
|
| The full state machine enumerated here: START
| case YOU_ARE_FIRST_PLAYER == T: DRAW case
| YOU_ARE_FIRST_PLAYER == F: DRAW
|
| Of course, for deterministic games and optimal play, either the
| first player always wins, the second play always wins, or it is
| always a draw.
|
| More interesting, if just one player (i.e. the computer player)
| always plays optimally, and favors the fewest states, that
| reduces the number of possible "valid" game states. So maybe less
| than 10 bits needed?
|
| 765 - 2^9 = 765 - 512 = 253 states would need to become
| unreachable for that to help.
| o_nate wrote:
| Here's a fairly intuitive 16-bit encoding:
|
| Use 9-bits to store positions of either blanks or Xs, depending
| on which there are more of. 1 extra bit to indicate which case it
| is. Then you have at most 6 remaining cells, so 6 more bits to
| indicate which of the two remaining options each contains. 16
| bits total.
|
| This also has the benefit that you can use fewer bits for many
| game states, e.g. a blank board can be represented in 10 bits.
| fngjdflmdflg wrote:
| You can also use %3 to evaluate the game for a win state from a
| given move. For example to detect the diagonal leftBottom -
| rightTop win state given some new move (row, col) it looks
| something like: int player = grid[row][col];
| if (row == (col+ col +2)%3){ if
| (grid[(row+1)%3][(col+2)%3] == player &&
| grid[(row+2)%3][(col+1)%3]==player){
| return true; } }
| pncnmnp wrote:
| Going off on a bit of a tangent here (thought it might be
| interesting!) - I first came across this topic in one of Russ
| Cox's blog posts (https://research.swtch.com/tictactoe). In TAOCP
| Volume 4A, Knuth discusses how optimal tic-tac-toe moves can be
| represented using boolean logic.
|
| I just went over the section again, and I'll do my best to break
| down his algorithm: He starts by picturing 2 3x3 grids - one for
| the X's and another for the O's. This setup introduces 18 boolean
| variables - x1 to x9 for the X's, and o1 to o9 for the O's. I
| think this can be neatly represented as a bit array (see
| https://github.com/denkspuren/BitboardC4/blob/master/Bitboar...).
|
| Now, creating a full-scale truth table for these 18 variables
| means we would be looking at 2^18, or 262,144 rows. However, it
| turns out only 4520 of those are legal inputs. So, the question
| becomes, how do we find patterns in this boolean chain to build
| our tic-tac-toe strategies.
|
| Knuth simplifies it by considering only the following strategies
| - (a.) winning - when putting an X in a cell wins the game - like
| when two cells in any line already have X's. (b.) blocking - when
| putting an X in a cell stops the other player from winning - like
| when two cells in any line have O's. (c.) forking - when putting
| an X in a cell opens up multiple winning moves - you store all
| the winning line possibilities (horizontal, vertical, and
| diagonal lines - all 9) in a set, and for each winning line (say
| {i, j, k}), you place an X on i, leave k empty, and see if a move
| on j creates two win chances. (d.) defending - similar, when
| putting an X in a cell stops the other player from creating
| multiple win chances. (e.) And just making any legal move - when
| a cell does not have an X or an O.
|
| The priority order of moves follows the order above. There's also
| a bit of priority within the legal moves - like the middle spot
| is best since it's part of more winning lines, while the edges
| are the last choice.
|
| As I am writing all this, I think it might not seem all that cool
| until you actually check out the boolean equations for yourself!
| Pretty neat stuff.
| demondemidi wrote:
| Dumb question: this didn't actually save any memory because the
| machine isn't trinary architecture. It's 15 trinary digits, not
| 15 bits, right? Obviously I'm not a CS guy.
| Leftium wrote:
| Only 9 trinary "trits" are needed, which fit in 15 binary bits.
|
| > we need nine base-3 digits... Representing this in binary
| will cost us... 15 bits!
|
| https://cbarrick.dev/posts/2024/02/19/tic-tac-toe#:~:text=we...
| te wrote:
| I had a very similar problem this week, trying to encode 5**13
| states in a 32-bit int. Should be doable with this. What is this
| encoding called? I haven't seen it before.
| zokier wrote:
| It's closely related to baseN coding. The principle is same as
| more widely know base64 or base58 schemes.
| antirez wrote:
| WARNING: This is wrong! 3^2 = 9, so we can't encode it in 8
| different symbols, but left here for history.
|
| The 15 bit encoding could be visualized in a different way, too,
| that is using 3 bits to represent two successive cells state:
| 000 "__" 001 "X_" 010 "_X" 011 "XX"
| 100 "XO" 101 "OX" 110 "O_" 111 "_O"
|
| There are 5 successive cells (4.5 actually, 9/2, but we need to
| be discrete here, and discard the last), so 5*3 = 15.
|
| However this encoding shows that if you want to represent
| multiple boards one after the other you are actually just using
| 13.5 bits for each board, as it should be in theory.
|
| Because to represent 18 total cells (two boards) you need 9*3
| bits = 27/2 = 13.5 bits per board.
| occamrazor wrote:
| It doesn't work. There is no encoding for "OO".
| antirez wrote:
| You are right! Sorry totally overlooked this :) Thanks.
| mturk wrote:
| I was listening to the audiobook of "The Future" by Naomi
| Alderman, and it spent a fair bit of time talking about MENACE:
| https://en.wikipedia.org/wiki/Matchbox_Educable_Noughts_and_...
| which I had not heard of before.
|
| Inspired by this I've spent some time thinking about how to
| encode games of battleship, and honestly it's genuinely a fun
| problem to explore. (I'm not going to share any of my ideas
| because I've deliberately _not_ looked into the literature on
| this and I 'm sure it's well-explored.)
| tromp wrote:
| In the game of connect-4, one doesn't need base 3 to make compact
| encodings. Gravity forces all non-empty squares in a column to be
| consecutive so a column of height n can be encoded in n+1 bits.
| For a column with h stones in it, set bit h to 1, all higher bits
| to 0, and then bits 0..h-1 can encode the h stones... This allows
| a 7x6 connect-4 board to be encoded in 7x7=49 bits. An 8x7 board
| still neatly fits into 64 bits. This is used in the Fhourstones
| connect-4 solver [1].
|
| [1] https://tromp.github.io/c4/c4.html
___________________________________________________________________
(page generated 2024-02-21 23:00 UTC)