Timeline for Complexity of transfinite 5-in-a-row and other games
Current License: CC BY-SA 4.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 6 at 0:56 | comment | added | Davide Leonessi | Since you mention Hex, I'd like to say that Ilkka Törmä showed that the complexity of the winning condition (i.e. the set of partial board colourings) of infinite Hex is arithmetic, at most $\Delta_5^0$. Note that infinite Hex does not allow ambiguous (illegal) board positions in which both players can claim a win, as in infinite 5-in-a-row. arxiv.org/abs/2310.08112v1 | |
| Mar 6 at 0:49 | comment | added | Davide Leonessi | You may want to clarify your initial question: the complexity of the set of (possibly infinite) winning end-positions, intended as partial board colourings, seems to be $\Sigma_2^0$: we only need to find 5 squares which are aligned and all assigned to the winner, and that there is no other 5-tuple of squares which are aligned and assigned to one player. The stricter no-overline condition can also be fitted in a $\Sigma_2^0$ winning condition. | |
| Mar 1 at 23:42 | comment | added | Dmytro Taranovsky | @JoshuaZ I do. I default to the variant where overlines win (while in most variants of Gomoku they do not), but a high complexity for any of the variants would work for an answer. | |
| Mar 1 at 23:37 | comment | added | JoshuaZ | By 5-in-a-row do you mean Gomoku? | |
| Mar 1 at 23:33 | history | asked | Dmytro Taranovsky | CC BY-SA 4.0 |