2 ms·

Quixo (the game this seems to be based on) is also deceptively simple but Exptime complete (https://www.sciencedirect.com/science/article/pii/S002001902030082X

Quixo (the game this seems to be based on) is also deceptively simple but Exptime complete (https://www.sciencedirect.com/science/article/pii/S002001902030082X https://www.sciencedirect.com/science/article/pii/S002001902...) and was solved after 2 decades (draw at optimal play on a 5x5 board, win for first player on smaller boards): https://arxiv.org/abs/2007.15895 https://arxiv.org/abs/2007.15895

amenghra 4y ago
Never heard of Quixo, thanks for sharing. My domain name was picked randomly a decade ago among the remaining short-ish names -- being similar in name is a coincidence.
- captn3m0 4y ago
  I assume that the name was a nod to the original game, my bad. I looked a bit for similar puzzles, and it seems this class of puzzles has a better name: A “Toroidal Sliding Block Puzzle”[1] [1]: https://puzzlingiphone.wordpress.com/2008/11/22/toroidal-sliding-block-puzzles/ https://puzzlingiphone.wordpress.com/2008/11/22/toroidal-sli...
  - amenghra 4y ago
    Toroidal Sliding Puzzle => chefkiss emoji
dane-pgp 4y ago
> (draw at optimal play on a 5x5 board, win for first player on smaller boards) Somewhat relatedly, I keep wondering how board size affects the game of chess in particular. It seems that a 1x8 board definitely leads to a stalemate (because the pawns in front of the kings would block each other), but at some point adding new columns (with the relevant pieces) makes the game impossible to exhaustively search, and at least plausibly introduces the ability for one of the players (presumably white) to win with perfect play. That ability for a winning strategy to emerge just beyond our ability to compute is somehow tantalising.
- captn3m0 4y ago
  There’s some interesting variants listed here: https://en.m.wikipedia.org/wiki/Minichess https://en.m.wikipedia.org/wiki/Minichess Without changing the rules somewhat, it appears that the odds change dramatically enough to make easy wins for one of the players on such smaller boards. Hence, variants include some weird stuff. On the other extreme, you get https://en.m.wikipedia.org/wiki/Infinite_chess https://en.m.wikipedia.org/wiki/Infinite_chess

amenghra 4y ago

Never heard of Quixo, thanks for sharing. My domain name was picked randomly a decade ago among the remaining short-ish names -- being similar in name is a coincidence.

captn3m0 4y ago
I assume that the name was a nod to the original game, my bad. I looked a bit for similar puzzles, and it seems this class of puzzles has a better name: A “Toroidal Sliding Block Puzzle”[1] [1]: https://puzzlingiphone.wordpress.com/2008/11/22/toroidal-sliding-block-puzzles/ https://puzzlingiphone.wordpress.com/2008/11/22/toroidal-sli...
- amenghra 4y ago
  Toroidal Sliding Puzzle => chefkiss emoji

dane-pgp 4y ago

> (draw at optimal play on a 5x5 board, win for first player on smaller boards) Somewhat relatedly, I keep wondering how board size affects the game of chess in particular. It seems that a 1x8 board definitely leads to a stalemate (because the pawns in front of the kings would block each other), but at some point adding new columns (with the relevant pieces) makes the game impossible to exhaustively search, and at least plausibly introduces the ability for one of the players (presumably white) to win with perfect play. That ability for a winning strategy to emerge just beyond our ability to compute is somehow tantalising.

captn3m0 4y ago
There’s some interesting variants listed here: https://en.m.wikipedia.org/wiki/Minichess https://en.m.wikipedia.org/wiki/Minichess Without changing the rules somewhat, it appears that the odds change dramatically enough to make easy wins for one of the players on such smaller boards. Hence, variants include some weird stuff. On the other extreme, you get https://en.m.wikipedia.org/wiki/Infinite_chess https://en.m.wikipedia.org/wiki/Infinite_chess