3 ms·
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
by kamens 3y ago
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.
- 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.
- nomel 3y agoThis 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.