5 ms·
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 squ
by Gare 3y ago
You could code the whole game sequence in only 22 bits.
First bit to mark whether X or O starts, then 4 bits for the placement of the first symbol (9 empty squares numbered 0-8 counting from top left), then only 3 bits for the second one (one square is already taken so there are only 8 possible positions left), etc. which gives us 4+3+3+3+3+2+2+1 = 21 bits for the 8 moves before there is only one unfilled square left.
- thechao 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.
- smallstepforman 3y agoYou can encode entire game history in 18 bits. https://news.ycombinator.com/item?id=39464824 https://news.ycombinator.com/item?id=39464824