Timeline for Is there a strongly solved game with infinite possible board arrangements?
Current License: CC BY-SA 4.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 11, 2020 at 9:53 | history | edited | Cohensius | CC BY-SA 4.0 |
added 1 character in body
|
| Dec 15, 2018 at 19:03 | comment | added | PJTraill | @BenjaminCosman: Even if Nim were only solved for arbitrarily large states, the ‘board’ is some equipment whose configurations represent the state space of the game; this equipment must either be infinitely large or infinitely finely divided. The question also refers to “infinite possible board arrangements”, which Nim matches. | |
| Jul 10, 2017 at 3:04 | comment | added | Thunderforge | Exactly. We know how to play infinite Nim, but infinite Chess isn't really well defined, so we'd have to figure out what that means before we even consider it for anything larger than a standard 8x8 board. | |
| Jul 10, 2017 at 2:28 | comment | added | Benjamin Cosman | Oh, didn't realize that, but I guess Nim does have a reasonable infinite version. Most games don't though, so the overall point stands. | |
| Jul 10, 2017 at 0:04 | comment | added | Gabriel C. Drummond-Cole | @BenjaminCosman isn't nim also solved for infinite ordinals? | |
| Jul 9, 2017 at 19:02 | comment | added | Benjamin Cosman | Note the difference between "infinite" and "arbitrarily large". Nim is solved for arbitrarily large states - with 10 piles, 100, 1000, etc, the winning strategy is known. Thus Nim is solved for an infinite number of different states. Yet no individual Nim state is infinite. Most games aren't well-defined on infinite boards, and depending on how you define them they might be trivially solved even if the normal game isn't - e.g. in infinite checkers (using the first definition I think of), all moves are equally optimal since the game can never end. | |
| Jul 9, 2017 at 18:10 | history | edited | Thunderforge | CC BY-SA 3.0 |
Adding a caveat
|
| Jul 9, 2017 at 18:08 | comment | added | Thunderforge | @ImmortalPlayer I've added a bit more to this. I'm not an expert in this field, but my understanding is that the problem set grows too big as we approach infinity to completely solve the problem such that we can never feasibly solve the problem. PSPACE-complete grows at a slower rate than EXPTIME-complete. Nim is in a different category of complexity in that we have an algorithm that doesn't depend on the size of the game. | |
| Jul 9, 2017 at 17:59 | history | edited | Thunderforge | CC BY-SA 3.0 |
added 870 characters in body
|
| Jul 9, 2017 at 16:50 | comment | added | Sensebe | Thank you for the answer. Is it that the optimal moves at every stage of an infinite sized board game exist, but we are not able to know them now, because of computational low power? I am going through the links now. | |
| Jul 9, 2017 at 15:25 | history | edited | Thunderforge | CC BY-SA 3.0 |
added 689 characters in body
|
| Jul 9, 2017 at 15:12 | history | edited | Thunderforge | CC BY-SA 3.0 |
deleted 1 character in body
|
| Jul 9, 2017 at 14:35 | history | answered | Thunderforge | CC BY-SA 3.0 |