tetris

https://github.com/qntm/tetris/blob/7c108f1f676233da9f20d831... https://github.com/qntm/tetris/blob/7c108f1f676233da9f20d831... Just checking: are you leaving the holes intact, the fully-enclosed interior holes in the well? Because those never become relevant in the problem you've phrased -- the game ends after *one* line is filled. So interior structure never becomes visible again. You're caching the wells that have already been visited (in that 2nd/improved codebase). But I believe the sameWell() equality test can be looser: you can identify as equal two wells which differ only by interior holes. That would make the search tree much (?) smaller.

Yes, a strategy does exist which can force at least one line in a well of width 10 (and different strategies for 4, 6 and 8). I did a tedious brute-force calculation which demonstrated this a few years back. The code is not particularly presentable and the calculation takes about 11 days on a modern machine (it runs in a single thread), but here: https://github.com/qntm/tetris The limiting factor is headroom (the depth of the well). For wells of depth 0, 1 and 2, the AI clearly wins, but once the depth increases enough a strategy becomes possible. My belief is that such a strategy exists for all even well widths, although proving this is annoyingly hard.