I recently stumbled upon a blog post by Alejandra González (a.k.a @blyxyas) that seeks to compress a tic-tac-toe game state into as few bits as possible. She arrived at a solution in 18 bits. This got me thinking, can we do better?
This one class I took in college presented a problem with a custom puzzle that involved closing loops on points laid out in a checkerboard pattern. If you implemented your solution using Lisp, you got a letter grade bonus, where otherwise the only criterion for your score was the performance of your solution.
I’m reminded of this problem I faced years ago because having a compact representation that is useful was key to extracting maximum performance.
Ultimately, I hand coded in x86 SIMD instructions to solve many instances of the problem in parallel, packing about eight problem instances into one register. It was the highest performing solution in the class and it both angered and disappointed the professor.
A useful, compact representation is key to efficiently solving many problems.
This one class I took in college presented a problem with a custom puzzle that involved closing loops on points laid out in a checkerboard pattern. If you implemented your solution using Lisp, you got a letter grade bonus, where otherwise the only criterion for your score was the performance of your solution.
I’m reminded of this problem I faced years ago because having a compact representation that is useful was key to extracting maximum performance.
Ultimately, I hand coded in x86 SIMD instructions to solve many instances of the problem in parallel, packing about eight problem instances into one register. It was the highest performing solution in the class and it both angered and disappointed the professor.
A useful, compact representation is key to efficiently solving many problems.
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.)
Base-3: 15 bits
Legal states only: 13 bits
Redundancy due to symmetry eliminated: 12 bits
Combining the previous two: I estimate 10 bits
15 bits is possible if you encode the state in base-3, where each digit represents one of the cells