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.
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.
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.
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
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.
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).
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.
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…
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.
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.)
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.
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.
> 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.
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
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 :)
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.
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.
> 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?
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:
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.
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.
> 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).
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.
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?
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.
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
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.
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.
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]]
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.
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.
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.
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.
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.
> 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.
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
> 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.
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.
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.
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;
}
}
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.
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.
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).
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.
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).
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.)
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].
106 comments
[ 1.6 ms ] story [ 92.6 ms ] threadThere 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 :-)
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.
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!
(About halfway down the page. It's as an example application of binary decision diagrams.)
But, hey, Steve Huffman sent me a Reddit sticker!
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
(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.
(I don’t remember the exact details now so take it with a grain of salt.)
I believe the optimal response to:
Should be Which offers a reasonable opportunity for "O" to mess up by choosing a corner. But instead your script plays Which guides the human player to reflexively counter accurately without thinking.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.
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.
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.
Two?
I.e.,
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:
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:
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)
A representation that always uses the minimum number of bits but has a straightforward relationship to the actual playing field is illusive[1]https://web.archive.org/web/20020513063952/http://www.mathre...
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.
https://stackoverflow.com/questions/7466429/generate-a-list-...
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?
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.
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).
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.
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.)
I don’t see how that makes a difference. You can always replace a lookup table by code, for example:
vs The classic example of this are the definitions of cons, car and cdr in SICP as lambdas: 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 × 2 array
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.
I agree that the challenge isn't rigorously defined. But the spirit is to not allow this kind of trick.
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.
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.
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.
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 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 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
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.
The full state machine enumerated here:
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.
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.
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.
> 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...
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
- 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
The 15 bit encoding could be visualized in a different way, too, that is using 3 bits to represent two successive cells state:
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.
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.
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.)
[1] https://tromp.github.io/c4/c4.html