Well done! I wonder if you can get better speeds by implementing the search in C/C++ - I did so with my 2048 bot (https://github.com/nneonneo/2048-ai) and was able to go from a few hundred thousand moves per second with Python, up to 10,000,000 moves per second with C++.
I'm curious to know what happens at 1000 moves. I'd play the game myself but I'm worried about dropping into a productivity black hole - as evidenced by my previous experience with 2048!
Author here. I really wasn’t very good at SPL-T before I changed gears to brute forcing it, so the whole strategy aspect is unexplored here. If you think you have a method that could be phrased in an algorithmic kind of way, please share! This topic is ripe for a more intelligent part 2, from me or someone else.
This would be a good opportunity for something like Alpha Go. Learn a heuristic function and then do tree search using the heuristic. You could start by hand-designing a heuristic and do best-first search to see how much better you do versus exhaustive exploration.
Oh, really so much faster with pypy3? That would have been very nice to know when putting this together, but in any case is good to know for the future. Thanks for the tip.
I’m wondering if the solution isn’t vaguely related to dynamic programming. IE, you can’t brute force the whole board, but you can easily brute force a small shape into a set of possible moves to fill it. You could then roll up these smaller shape move sequences into larger move sequences to optimize filling larger blocks.
With simple counting of vertical / horizontal moves required, you can easily fill the entire board with 1x1 filled squares. At that point you just need to optimize for filling squares while leaving the largest possible area open (to reduc me the new square counter) as well as optimize the order of which squares zero and clear first.
Awesome! I love SPL-T. I've found the best way to move forward is keeping a quarter free and focusing on minimizing the rest of the board. I usually lose when I misplace a horizontal split and end up creating manying vertical spits.
Nice write up and very well structured. Reminds me of when I did the complete tic-tac-toe analysis by hand back in the 80s while in elementary. It’s always interesting to see such simple ideas and game mechanics leading into such challenging games with (practically) infinitely number of end states.
Thanks for sharing your effort, will have a look at the notebook ;-)
[+] [-] nneonneo|7 years ago|reply
I'm curious to know what happens at 1000 moves. I'd play the game myself but I'm worried about dropping into a productivity black hole - as evidenced by my previous experience with 2048!
[+] [-] flashingleds|7 years ago|reply
[+] [-] TTPrograms|7 years ago|reply
[+] [-] tln|7 years ago|reply
I was curious about the speed comment... "computer with a newish 4-core CPU can simulate 2-3 million randomly played games in 24 hours"
On my old 2014 MBP (2.8ghz 4 core i5) I get 580k games per 24 hours on python3 and 12 million on pypy3.
On my work 2017 MBP (2.8 Ghz 8 core i7) I get 2 million games per 24 hours on python3 and 53 million games per 24 hours on pypy3.
Nice speedup to be had :)
[+] [-] flashingleds|7 years ago|reply
[+] [-] danielvf|7 years ago|reply
With simple counting of vertical / horizontal moves required, you can easily fill the entire board with 1x1 filled squares. At that point you just need to optimize for filling squares while leaving the largest possible area open (to reduc me the new square counter) as well as optimize the order of which squares zero and clear first.
[+] [-] alexkavon|7 years ago|reply
[+] [-] NKosmatos|7 years ago|reply
[+] [-] adinb|7 years ago|reply