Encoding tic-tac-toe in 15 bits(cbarrick.dev)
cbarrick.dev
Encoding tic-tac-toe in 15 bits
https://cbarrick.dev/posts/2024/02/19/tic-tac-toe
106 comments
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.)
(About halfway down the page. It's as an example application of binary decision diagrams.)
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.
Sorry, the article was finished in a bit of a hurry. (Not sure what you mean about a domain specific language.) Maybe if the writing's too bad, the tic-tac-toe code might still be readable, in the linked repo https://github.com/darius/mccarthy-to-bryant (tictactoe.py and ttt_*). Python 2 (I said it was old).
I read your comment a few times and I have no idea what you are are trying to say. Can you explain?
“Something something only use programming languages I like.”
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
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
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!
But, hey, Steve Huffman sent me a Reddit sticker!
Seems appropriate given that a Huffman code is a compression strategy.
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.
Is there an inaccuracy for https://www.craig-wood.com/nick/oxo2d/b2/ ?
I believe the optimal response to:
I believe the optimal response to:
X . .
. O .
. . .
X . .
. O .
. . X
X X .
. O .
. . .
The immediate threat offers the opponent 5/6 losing moves, whereas yours offers only 2/6 losing moves. The rationale is quite similar to your choice of the initial corner move rather than center: there are 7/8 losing responses to turn 1 corner, and only 4/8 losing responses to turn 1 center. But you'll probably get more humans to pick a losing side response to center than pick a losing non-center response to corner.
> The immediate threat offers the opponent 5/6 losing moves, whereas yours offers only 2/6 losing moves.
This would be relevant if humans made their choice with a significant amount of randomness. But I argue that in this specific situation, very nearly every human will play to block the obvious threat.
I believe humans will be more likely to pick one of the two losing moves in the slightly more abstract/delayed threat scenario, than they would be to pick one of the 5 losing moves in the immediate threat scenario.
This would be relevant if humans made their choice with a significant amount of randomness. But I argue that in this specific situation, very nearly every human will play to block the obvious threat.
I believe humans will be more likely to pick one of the two losing moves in the slightly more abstract/delayed threat scenario, than they would be to pick one of the 5 losing moves in the immediate threat scenario.
Yes, I believe this too.
I also believe humans are more likely to pick one of the 4/8 losing moves if you open center than one of the 7/8 losing moves if you open corner, though.
I also believe humans are more likely to pick one of the 4/8 losing moves if you open center than one of the 7/8 losing moves if you open corner, though.
Ah, this clarifies your other point above. Thank you!
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_...
Interesting. Only 304 unique permutations so 9 bits is more than anyone would ever need for a tic-tac-toe state?
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…
For something slightly more practical here's a printable PDF representation of googolplex: http://www.googolplexwrittenout.com/
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.)
(I don’t remember the exact details now so take it with a grain of salt.)
there are even more possible variations of chess games than there are atoms in the observable universe.
My favourite "big but comprehensible generation number" is the count of unique shuffles of a standard deck of 52 cards.
(this is my best recollection of the "this is how insane it is" story, numbers may be slightly off)
Iterate through a billion possible shuffles a second and every yearly anniversary, take a 1M pace around the equator. When you get back to your starting point (after 40,075 years), take 1cc out of the Pacific Ocean.
When the ocean is empty, put one A4 piece of 0.05mm paper on a pile. Now you start filling the ocean 1cc every circumnavigation. When it's full, A4 piece of paper on the pile. etc.
By the time you exhaust the list of shuffles, the pile will be 188 light years tall.
(this is my best recollection of the "this is how insane it is" story, numbers may be slightly off)
Iterate through a billion possible shuffles a second and every yearly anniversary, take a 1M pace around the equator. When you get back to your starting point (after 40,075 years), take 1cc out of the Pacific Ocean.
When the ocean is empty, put one A4 piece of 0.05mm paper on a pile. Now you start filling the ocean 1cc every circumnavigation. When it's full, A4 piece of paper on the pile. etc.
By the time you exhaust the list of shuffles, the pile will be 188 light years tall.
Yeah, I'd definitely have to delete some old emails.
The game can be super condensed if both players are assumed to play optimally.
The full state machine enumerated here:
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.
The full state machine enumerated here:
START
case YOU_ARE_FIRST_PLAYER == T: DRAW
case YOU_ARE_FIRST_PLAYER == F: 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.
See https://news.ycombinator.com/item?id=39456467, posted a few hours before your comment.
[deleted]
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.
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.
A list of actions/moves should be more compact. You'd replay from the initial state.
There are at most 9 moves in a game; after that the board is full. The first move has 9 options, the next 8, the next 7, etc. That's 9! sequences of moves. And this is an upper bound, because some prefixes lead to shorter games.
Computing ceil(log2(9!)), we get 19 bits -- not for a game-state, but for an entire play-history.
One could do better using an exact game-tree. You could think of it as a simple version of arithmetic coding. Or you could just think of it as assigning an index (0, 1, 2, ...) to each leaf visited in some specified tree-traversal order.
There are at most 9 moves in a game; after that the board is full. The first move has 9 options, the next 8, the next 7, etc. That's 9! sequences of moves. And this is an upper bound, because some prefixes lead to shorter games.
Computing ceil(log2(9!)), we get 19 bits -- not for a game-state, but for an entire play-history.
One could do better using an exact game-tree. You could think of it as a simple version of arithmetic coding. Or you could just think of it as assigning an index (0, 1, 2, ...) to each leaf visited in some specified tree-traversal order.
If you prune inaccessible parts of the game tree, you only save one bit. There are 255,168 leaf nodes; taking ceil(log2(.)) you get 18 bits.
I've devised a way to encode the entire game history in 18 bits. See https://news.ycombinator.com/item?id=39464824.
I think you could do it in at most 17 since rotated/reflected boards are not unique from the game perspective, so only 3 real states for the first move, etc.
This was my first "AI" project, back in high school!
I had a "win statistic" for each possible play, for each game state. It taught itself to play by playing partially random moves, then going back and updating the win statistic for each game state in the play chain.
I was mesmerized, watching it teach itself to play.
I had a "win statistic" for each possible play, for each game state. It taught itself to play by playing partially random moves, then going back and updating the win statistic for each game state in the play chain.
I was mesmerized, watching it teach itself to play.
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.
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.
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.)
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.)
This code encodes a board into [0, 6045] which fits in 13 bits:
https://gist.github.com/ashdnazg/5cca7de6bac0eef4532d0c635c6...
It follows the principle that one can represent a board by choosing k filled spots from 9 and then choosing k / 2 Os from k. These two combinations can be converted into an index, which can then be offset according to k to prevent collisions with indices from other ks. This offset is not pretty, but it works.
I haven't thoroughly tested my code, but the principle should work even if there's a bug or two :)
With some luck I'll find time to write a clearer explanation or a blog post.
It follows the principle that one can represent a board by choosing k filled spots from 9 and then choosing k / 2 Os from k. These two combinations can be converted into an index, which can then be offset according to k to prevent collisions with indices from other ks. This offset is not pretty, but it works.
I haven't thoroughly tested my code, but the principle should work even if there's a bug or two :)
With some luck I'll find time to write a clearer explanation or a blog post.
Ooo exciting. Keep me posted when you write it up!
> 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:
For pure functions taking finite inputs, the reverse is possible, too. For example, you can define and on booleans as a 2 × 2 array
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.
I don’t see how that makes a difference. You can always replace a lookup table by code, for example:
a = [832, 54, 743]
func a(i) =
if i = 0 return 832
if i = 1 return 54
return 743
(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)))
For pure functions taking finite inputs, the reverse is possible, too. For example, you can define and on booleans as a 2 × 2 array
and = [[false, false], [false, true]]
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.
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.
I agree that the challenge isn't rigorously defined. But the spirit is to not allow this kind of trick.
I thought the point of the article (actual working implementations) was fairly obvious, and I'm sorry to see people miss it!
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.
> 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.
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.
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-...
https://stackoverflow.com/questions/7466429/generate-a-list-...
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.
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]
Huh, dunno. Probably a dumb bug in my hacky script.
> 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?
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?
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
XOXYes, 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.
Tangential: I once shrunk a representation from 65 bits to 60 - it sped up my program considerably:
I wrote a solver (https://github.com/phimuemue/brainball_solver) for "brainball" (https://twistypuzzles.com/cgi-bin/puzzle.cgi?pkey=889), a (rubik-like) puzzle involving 13 cells arranged in a circle.
Each cell has: A number (from 1 to 13). - 4 bits. Two sides colored white resp. yellow. - 1 bit. The goal is to arrange the cells in number-ascending order, all white sides face up.
Representing each cell would lead to 13*(4+1)=65 bits. A "canonicalized" representation where the cell number 13 is implicitly at a certain position shrinks the representation to 12*(4+1)=60 bits and fits into a 64-bit integer (https://github.com/phimuemue/brainball_solver/blob/master/sr...).
This was one of the things that made my solver reasonably fast (others were lookup tables (https://github.com/phimuemue/brainball_solver/blob/master/bu...), and aggressive function inlining (e.g. https://github.com/phimuemue/brainball_solver/blob/master/sr...)).
I wrote a solver (https://github.com/phimuemue/brainball_solver) for "brainball" (https://twistypuzzles.com/cgi-bin/puzzle.cgi?pkey=889), a (rubik-like) puzzle involving 13 cells arranged in a circle.
Each cell has: A number (from 1 to 13). - 4 bits. Two sides colored white resp. yellow. - 1 bit. The goal is to arrange the cells in number-ascending order, all white sides face up.
Representing each cell would lead to 13*(4+1)=65 bits. A "canonicalized" representation where the cell number 13 is implicitly at a certain position shrinks the representation to 12*(4+1)=60 bits and fits into a 64-bit integer (https://github.com/phimuemue/brainball_solver/blob/master/sr...).
This was one of the things that made my solver reasonably fast (others were lookup tables (https://github.com/phimuemue/brainball_solver/blob/master/bu...), and aggressive function inlining (e.g. https://github.com/phimuemue/brainball_solver/blob/master/sr...)).
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.
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.
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:
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.
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"
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.
It doesn't work. There is no encoding for "OO".
You are right! Sorry totally overlooked this :) Thanks.
Wow good eye?
Indeed, this is wrong. However, 3^3 is 27, which is less than 32, so you can easily encode each row in 5 bits.
The encoding into those 5 bits is precisely the base-3 encoding from the article, so I'll leave it as an exercise for the reader.
The encoding into those 5 bits is precisely the base-3 encoding from the article, so I'll leave it as an exercise for the reader.
Good observation! Always useful to see things from a different angle, that was indeed what I was trying to say in the original post (even if it was wrong).
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
[1] https://tromp.github.io/c4/c4.html
> 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.
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.
> couple of extra bits
Two?
Two?
There are four ways to rotate, so yes exactly two bits, right?
Plus a third bit for rotationally flipped.
I.e.,
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:
But ... some arrangements have instance symmetry where only 1 bit of rotation symmetry is needed, and no rotation-flips:
And this field requires 0 symmetry bits, as all rotations and flips are identities (1 step to return = 0 bits)
I.e.,
[O X -]
[- - -]
[- - -]
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 - -]
[- - -]
But ... some arrangements have instance symmetry where only 1 bit of rotation symmetry is needed, and no rotation-flips:
[O - X]
[- - -]
[X - O]
And this field requires 0 symmetry bits, as all rotations and flips are identities (1 step to return = 0 bits)
[- - -]
[- X -]
[- - -]
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...
[1]https://web.archive.org/web/20020513063952/http://www.mathre...
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;
}
}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.
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.
Disregarding simplifications from symmetry, the first three moves comprise 9 * 8 * 7 = 504 possible combinations. Surely you can enumerate at least that. So you'd only need 9 bits, saving you a bit. And I'm not sure why you'd need to mark whether X or O starts: X always starts.
You can encode entire game history in 18 bits. https://news.ycombinator.com/item?id=39464824
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?
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
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.
https://news.ycombinator.com/item?id=39462056 claims that pruning saves only one bit which is not great. I don't know can you squeeze two bits from symmetries somehow?
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
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
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.
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.
The entire game history (all possible moves / state) from the first move to the 9th move can be encoded into 18 bits. This also allows reconstruction of the game state after every move. The trick is to use the encoding logic for video compressors, start with a keyframe and encode delta frames. In this case, a delta frame would be to determine the number of available spaces, and store the next move. The number of available spaces decrements after every move, so you need less bits. A further space optimisation can be to reuse unused bit values from subsequent moves. Eg. for the 3rd move, there are 7 available fields. This can be packed into 3 bits, with one value spare. The spare can be borrowed to move 1, which has 9 fields. This allows the following optimisation:
1st / 9 / 3 bits (-1)
2nd / 8 / 3 bits (0)
3rd / 7 / 3 bits (+1) (used to complete 1st)
4th / 6 / 3 bits (+2)
5th / 5 / 2 bits (-1) (use 4th extra)
6th / 4 / 2 bits (0)
7th / 3 / 1 bit (-1) use 4th extra
8th / 2 / 1 bit (0)
9th / 1 / 0 bits
Total = 18 bits. This is for the entire game history, from the first to last move, and every board state in between. Decoding this 18 bit mask is not really that challenging, since there are only 3 special cases, and the 9th move requires no bits to store the move (since there is only one possible move). To reconstruct the state at any given time, you need to start from the keyframe and move forward.
18 bits for entire game history.
1st / 9 / 3 bits (-1)
2nd / 8 / 3 bits (0)
3rd / 7 / 3 bits (+1) (used to complete 1st)
4th / 6 / 3 bits (+2)
5th / 5 / 2 bits (-1) (use 4th extra)
6th / 4 / 2 bits (0)
7th / 3 / 1 bit (-1) use 4th extra
8th / 2 / 1 bit (0)
9th / 1 / 0 bits
Total = 18 bits. This is for the entire game history, from the first to last move, and every board state in between. Decoding this 18 bit mask is not really that challenging, since there are only 3 special cases, and the 9th move requires no bits to store the move (since there is only one possible move). To reconstruct the state at any given time, you need to start from the keyframe and move forward.
18 bits for entire game history.
> Eg. for the 3rd move, there are 7 available fields. This can be packed into 3 bits, with one value spare. The spare can be borrowed to move 1, which has 9 fields.
This reasoning is not true. Let's say that the 1st move has 9 possible choices of A through I, while the 3rd move has 7 possible choices of 1 through 7 (which would depend on prior moves). When the 3rd move is made, your choice for the 3rd move has to be fixed and there is no "spare" choice available. If you chose to use that spare choice, you must use 3 bits allocated for the 1st move somehow differently so that both 1st and 3rd moves are uniquely determined.
As a concrete example, let's represent A/1 as 000, B/2 as 001, ..., G/7 as 110 and H as 111. Any combination of [A-G][1-7] should be trivial to encode. If the first move is I however, you have to use the spare choice for the 3rd position to represent that fact. The 3rd move itself then has to move into bits originally used by the 1st move. Note that this leaves one unused bit pattern: 111111, which demonstrates why your reasoning is incorrect---this happens because the number of possibilities muliplies, not adds, and 9 * 7 < 8 * 8. In general the optimal packing of 9 moves would need 9 * 8 * ... * 1 = 362 880 possibilities, which exceeds 2^18 = 262 144 possibilities which 18 bits can encode, so you actually need 19 bits. (Or 20 bits if you also account for 623 530 mid-game states.)
This reasoning is not true. Let's say that the 1st move has 9 possible choices of A through I, while the 3rd move has 7 possible choices of 1 through 7 (which would depend on prior moves). When the 3rd move is made, your choice for the 3rd move has to be fixed and there is no "spare" choice available. If you chose to use that spare choice, you must use 3 bits allocated for the 1st move somehow differently so that both 1st and 3rd moves are uniquely determined.
As a concrete example, let's represent A/1 as 000, B/2 as 001, ..., G/7 as 110 and H as 111. Any combination of [A-G][1-7] should be trivial to encode. If the first move is I however, you have to use the spare choice for the 3rd position to represent that fact. The 3rd move itself then has to move into bits originally used by the 1st move. Note that this leaves one unused bit pattern: 111111, which demonstrates why your reasoning is incorrect---this happens because the number of possibilities muliplies, not adds, and 9 * 7 < 8 * 8. In general the optimal packing of 9 moves would need 9 * 8 * ... * 1 = 362 880 possibilities, which exceeds 2^18 = 262 144 possibilities which 18 bits can encode, so you actually need 19 bits. (Or 20 bits if you also account for 623 530 mid-game states.)
Right, the logic of "take a spare representation from here and use it to encode an extra state from over there" doesn't work in general, and sinks GP's whole idea. But since 9×7 < 8×8, it does _in practice_ work to encode 9×7 states in 3+3 bits.
Where GP's idea breaks down pragmatically (as well as logically) is when he tries to take _two_ spare representations and use them to encode _two_ extra states, for bits 6, 5, and 3. It's true that 6 = 2^3 - 2, 5 = 2^2 + 1, 3 = 2^1 + 1; but you can't represent 6×5×3 = 90 states using only 2^(3+2+1) = 64 representations.
In short: If A = 2^a + k and B = 2^b - k, then we can cancel the k when adding A+B, but not when multiplying A×B.
Where GP's idea breaks down pragmatically (as well as logically) is when he tries to take _two_ spare representations and use them to encode _two_ extra states, for bits 6, 5, and 3. It's true that 6 = 2^3 - 2, 5 = 2^2 + 1, 3 = 2^1 + 1; but you can't represent 6×5×3 = 90 states using only 2^(3+2+1) = 64 representations.
In short: If A = 2^a + k and B = 2^b - k, then we can cancel the k when adding A+B, but not when multiplying A×B.
Regarding the first move, 3 bits store 8 values. However, the spare value on move 3 signals us to ignore any value in the original move 3 bits and treat it as a special case to give the 9th value we need.
I'm thinking that there may be a way to reduce that further if you consider symmetry/rotation or don't care much about the sequence, e.g. selecting any corner or edge on the first move is equivalent and since we know that the first move must happen we only need less than 2 bits (2 at most) to encode the first move i.e. 3 states: corner, edge, or center.
One could use variable length, as once some player wins the game is done.
There's a similar trick that you can use to store permutations, where you use a variable base representation.
For example, suppose that you need to store a permutation of 4 digits, [1,3,0,2]. The rightmost digit is base 4 and simply stores 1 directly. The second digit is base 3, but scale 4, and stores the position of 3 in [0,2,3] (because 1 has been removed from the set), i.e., 2. The third digit is 0 (base 2 scale 12) by similar reasoning, and the "fourth digit" would be base 1, which is always 0. Multiplying it out, you get 012 + 24 + 1 = 9.
Decoding follows a similar process:
This technique allows you to store permutations of up to 12 items in 32 bits, or 20 items in 64.
For example, suppose that you need to store a permutation of 4 digits, [1,3,0,2]. The rightmost digit is base 4 and simply stores 1 directly. The second digit is base 3, but scale 4, and stores the position of 3 in [0,2,3] (because 1 has been removed from the set), i.e., 2. The third digit is 0 (base 2 scale 12) by similar reasoning, and the "fourth digit" would be base 1, which is always 0. Multiplying it out, you get 012 + 24 + 1 = 9.
Decoding follows a similar process:
9 % 4 = 1 9 / 4 = 2 [0,1,2,3][1] = 1
2 % 3 = 2 2 / 3 = 0 [0,2,3][2] = 3
0 % 2 = 0 0 / 2 = 0 [0,2][0] = 0
[2][0] = 2
This technique allows you to store permutations of up to 12 items in 32 bits, or 20 items in 64.
In the 90s I wrote a Tic-Tac-Toe for Casio graphical calculators (fx7500G).
The main constraint was the code size, so I did heaving golfing.
To store the game state I did use 3 bits for each cell (0=empty, 1=X, 4=O), total 27 bits. That structure allowed to conveniently check if a win state was reached by multiplying the 3 cells values of the column/row/diagonal of the last move (multiplication required less code bytes than addition). 111=1 or 444=64 were winning states.
However I have a formula in the code that I fail to remember what was its use:
To store the game state I did use 3 bits for each cell (0=empty, 1=X, 4=O), total 27 bits. That structure allowed to conveniently check if a win state was reached by multiplying the 3 cells values of the column/row/diagonal of the last move (multiplication required less code bytes than addition). 111=1 or 444=64 were winning states.
However I have a formula in the code that I fail to remember what was its use:
15.5I-2.5I²-20
> 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.
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.
> 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).
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).
Try to extend it Super Tic Tac Toe :) - https://malkia.github.io/tictactoe/#/
It may be slightly faster to break the table into two and encode as 2 8-bit values. Each eight bit value can store the value of 5 cells. So two can encode the whole board (with one extra cell to use as you please).
And if this is a hot part of the code a lookup table for 256 values may be a speedup and is very manageable. Especially if you compress it to 128 bytes (although that may lose the performance you were after, calculating how much cache is worth using is a hard problem).
And if this is a hot part of the code a lookup table for 256 values may be a speedup and is very manageable. Especially if you compress it to 128 bytes (although that may lose the performance you were after, calculating how much cache is worth using is a hard problem).
> 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.
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.
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.
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.
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.
Not every transition, but all of the optimal ones https://xkcd.com/832/
Just a small nitpick, this isn't every possible combination, since each player picks the "best" choice at every stage.
There is also an equivalent set of "worst" choices, and even for the "best" choices, it has four rotations, since there are four corners that X could start from that are topographically the same.
Still cool though :-)
There is also an equivalent set of "worst" choices, and even for the "best" choices, it has four rotations, since there are four corners that X could start from that are topographically the same.
Still cool though :-)
I hadn't seen this before. Thanks for posting! My 8 year old will get a kick out of this!
[deleted]
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.
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.
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...
> 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...
Yes. That’s the same link as the article. Thanks?
It's a special "link to highlight" that jumps to and highlights the part of the article I quoted.
Only supported by a few browsers; maybe just Chrome?
- Works on Chrome/Chromium desktop
- Chrome for iPhone (highlights, but doesn't jump)
More info:
- https://support.google.com/chrome/answer/10256233?hl=en&co=G...
- https://hw.leftium.com/#/item/26848141
Only supported by a few browsers; maybe just Chrome?
- Works on Chrome/Chromium desktop
- Chrome for iPhone (highlights, but doesn't jump)
More info:
- https://support.google.com/chrome/answer/10256233?hl=en&co=G...
- https://hw.leftium.com/#/item/26848141
Even better info about "Scroll to Text Fragment" feature:
- https://stackoverflow.com/a/62162093/117030
- https://wicg.github.io/scroll-to-text-fragment/
- https://www.wikiwand.com/en/Fragment_identifier#Examples
- https://chromestatus.com/feature/4733392803332096
- https://stackoverflow.com/a/62162093/117030
- https://wicg.github.io/scroll-to-text-fragment/
- https://www.wikiwand.com/en/Fragment_identifier#Examples
- https://chromestatus.com/feature/4733392803332096
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.
An efficient method would be groupping 13 items into groups of 3, 3, 3, 3 and 1 item(s) each, and then encoding 5^3 = 125 possibilities into 7 bits. That leaves 4 bits which can be used to encode the last group without any additional coding. This kind of numerical coincidences is widely used in bitwise encoding (e.g. QR code's numeric and alphanumeric modes make use of the fact that 2^10 / 10^3 and 2^11 / 45^2 are both close to 1 while no less than 1).
It's closely related to baseN coding. The principle is same as more widely know base64 or base58 schemes.
my first thought is represent rows instead of cells
[deleted]
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.)
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.)
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!