7 ms·
Encoding tic-tac-toe in 15 bits
- mcraiha 3y agoScary 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 3y agoNot every transition, but all of the optimal ones https://xkcd.com/832/ https://xkcd.com/832/
- thatnerdyguy 3y agoI hadn't seen this before. Thanks for posting! My 8 year old will get a kick out of this!
- pwagland 3y agoJust 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 :-)
- jerf 3y agoThis 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 3y agomy first thought is represent rows instead of cells
- nickcw 3y agoA 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/ 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 3y agoThat 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 3y agoSince your C is lost here's Python code in an old article of mine: https://codewords.recurse.com/issues/four/the-language-of-choice 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 3y agoTotally 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.
- canadianfella 3y agoI read your comment a few times and I have no idea what you are are trying to say. Can you explain?
- sodapopcan 3y ago“Something something only use programming languages I like.”
- llimos 3y ago> 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 3y ago> couple of extra bits Two?
- yjftsjthsd-h 3y agoThere are four ways to rotate, so yes exactly two bits, right?
- Nevermark 3y agoPlus 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 3y agoAnd 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.mathrec.org/old/2002jan/solutions.html https://web.archive.org/web/20020513063952/http://www.mathre...
- npinsker 3y agoThere’s further you can go — e.g. by taking advantage of the turn-based nature (there won’t ever be 4 Xs and two Os). Can save almost another bit by assuming X always goes first.
- munificent 3y ago> by taking advantage of the turn-based nature (there won’t ever be 4 Xs and two Os). Also by discarding any boards that are only reachable after some winning solution. Honestly, the most efficient solution is probably to enumerate all valid reachable board states, and then just encode them in a look-up table. It's a tiny game. Damn it, I nerd sniped myself. After hacking together a little program, it looks like there's 5,620 valid reachable board states, so 13 bits is enough to encode them all.
- tyingq 3y agoMight be an interesting exercise to see why some people get 5477, and you're getting 5,620: https://stackoverflow.com/questions/7466429/generate-a-list-of-all-unique-tic-tac-toe-boards https://stackoverflow.com/questions/7466429/generate-a-list-...
- munificent 3y agoHuh, dunno. Probably a dumb bug in my hacky script.
- penwielder 3y agoThis sounded like an interesting puzzle to me. I doubt it's the only way, but I arrive at 5620 if I both count the empty position and leave out detection of diagonal wins.
- munificent 3y agoAh, you're right. I had a bug in the code to detect diagonal wins. With that fixed, I get 5,478 unique reachable boards.
- taeric 3y agoI 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 3y ago> 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 3y agoYou 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 3y agoYou 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 3y agoI'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 3y agohttps://news.ycombinator.com/item?id=39462056 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?
- zokier 3y agoTo 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
- SeanLuke 3y agoDisregarding 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.
- notorandit 3y ago10 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.
- deleted 3y ago[deleted]
- cbarrick 3y agoOP 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/ https://goose.love/! (And yeah, you need 12 or 13 bits, not 10, if you don't want to eliminate symmetries.)
- kqr 3y agoI thought the point of the article (actual working implementations) was fairly obvious, and I'm sorry to see people miss it!
- Someone 3y ago> 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 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 = [[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 3y agoI 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 3y agoThere'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.
- FooBarBizBazz 3y agoA 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.
- FooBarBizBazz 3y agoIf 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.
- smallstepforman 3y agoI've devised a way to encode the entire game history in 18 bits. See https://news.ycombinator.com/item?id=39464824 https://news.ycombinator.com/item?id=39464824.
- ufocia 3y agoI 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.
- scottlamb 3y ago> 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 3y agoThere 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 https://code.up8.edu/-/snippets/6
- notfed 3y ago> 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 3y agoThe 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.
- deleted 3y ago[deleted]
- ghusbands 3y agoSee https://news.ycombinator.com/item?id=39456467 https://news.ycombinator.com/item?id=39456467, posted a few hours before your comment.
- o_nate 3y agoHere'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 3y agoYou 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 3y agoGoing 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 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/BitboardDesign.md 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 3y agoDumb 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 3y agoOnly 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%20need%20nine,us%E2%80%A6%2015%20bits https://cbarrick.dev/posts/2024/02/19/tic-tac-toe#:~:text=we...
- demondemidi 3y agoYes. That’s the same link as the article. Thanks?
- Leftium 3y agoIt'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=GENIE.Platform%3DDesktop&oco=1 https://support.google.com/chrome/answer/10256233?hl=en&co=G... - https://hw.leftium.com/#/item/26848141 https://hw.leftium.com/#/item/26848141
- Leftium 3y agoEven better info about "Scroll to Text Fragment" feature: - https://stackoverflow.com/a/62162093/117030 https://stackoverflow.com/a/62162093/117030 - https://wicg.github.io/scroll-to-text-fragment/ https://wicg.github.io/scroll-to-text-fragment/ - https://www.wikiwand.com/en/Fragment_identifier#Examples https://www.wikiwand.com/en/Fragment_identifier#Examples - https://chromestatus.com/feature/4733392803332096 https://chromestatus.com/feature/4733392803332096
- te 3y agoI 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 3y agoIt's closely related to baseN coding. The principle is same as more widely know base64 or base58 schemes.
- lifthrasiir 3y agoAn 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).
- antirez 3y agoWARNING: 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 3y agoIt doesn't work. There is no encoding for "OO".
- antirez 3y agoYou are right! Sorry totally overlooked this :) Thanks.
- AgentOrange1234 3y agoWow good eye?
- thequux 3y agoIndeed, 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.
- antirez 3y agoGood 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).
- mturk 3y agoI 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_Crosses_Engine 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 3y agoIn 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 https://tromp.github.io/c4/c4.html
- malkia 3y agoTry to extend it Super Tic Tac Toe :) - https://malkia.github.io/tictactoe/#/ https://malkia.github.io/tictactoe/#/
- deleted 3y ago[deleted]
- thequux 3y agoThere'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: 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 The particularly observant reader will notice that the decoding algorithm is simply a deterministic Fisher-Yates shuffle, and the common optimization where you swap items from the source list instead of shifting them applies here as well. This technique allows you to store permutations of up to 12 items in 32 bits, or 20 items in 64.
- smallstepforman 3y agoThe 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.
- ufocia 3y agoI'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.
- lifthrasiir 3y ago> 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.)
- phimuemue 3y agoTangential: 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 https://github.com/phimuemue/brainball_solver) for "brainball" (https://twistypuzzles.com/cgi-bin/puzzle.cgi?pkey=889 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/src/main.rs#L95-L120 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/build.rs#L38-L79 https://github.com/phimuemue/brainball_solver/blob/master/bu...), and aggressive function inlining (e.g. https://github.com/phimuemue/brainball_solver/blob/master/src/main.rs#L247-L253 https://github.com/phimuemue/brainball_solver/blob/master/sr...)).
- kevincox 3y agoIt 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).
- dolmen 3y agoIn 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: 15.5I-2.5I²-20 Full source is here: https://web.archive.org/web/20010517135352/http://www.multimania.com/dolmen/productions/casio/MORPION.TXT https://web.archive.org/web/20010517135352/http://www.multim...