Обобщенная игра

Игра обобщена, так что в нее можно играть на доске или сетке любого размера.

Обобщенное судоку включает в себя головоломки разных размеров.

В теории сложности вычислений обобщенная игра — это игра или головоломка, обобщенная так, что в нее можно играть на доске или сетке любого размера. Например, обобщенные шахматы — это игра в шахматы на доске с фигурами на каждой стороне. Обобщенное судоку включает судоку, построенное по сетке. ${\displaystyle n\times n}$ ${\displaystyle 2n}$ ${\displaystyle n\times n}$

Теория сложности изучает асимптотическую сложность задач, поэтому необходимы обобщения игр, поскольку игры на доске фиксированного размера являются конечными задачами.

Для многих обобщенных игр, которые длятся в течение количества ходов, полиномиального размера доски, проблема определения того, есть ли выигрыш для первого игрока в данной позиции, является PSPACE-полной . Обобщенный шестнадцатеричный формат и реверси являются PSPACE-полными. ^{[1] [2]}

Для многих обобщенных игр, которые могут длиться несколько ходов, экспоненциально зависящих от размера доски, проблема определения того, есть ли выигрыш для первого игрока в данной позиции, является EXPTIME-полной . Обобщенные шахматы , го (с японскими правилами ко), Кихо, ^[3] и шашки являются EXPTIME-полными. ^{[4] [5] [6]}

Смотрите также

• Сложность игры
• Комбинаторная теория игр

Рекомендации

1. Райш, Стефан (1981), «Hex ist PSPACE-vollständig», Acta Informatica , 15 (2): 167–191, doi : 10.1007/bf00288964, S2CID  9125259
2. Ивата, Сигеки; Касаи, Такуми (январь 1994 г.), «Игра Отелло на доске является PSPACE-полной», Theoretical Computer Science , 123 (2): 329–340, doi : 10.1016/0304-3975(94)90131-7 ${\displaystyle n\times n}$
3. Мишиба, Шохей; Такенага, Ясухико (2 июля 2020 г.). «QUIXO завершен по EXPTIME». Письма об обработке информации . 162 : 105995. doi : 10.1016/j.ipl.2020.105995 . ISSN  0020-0190.
4. Френкель, Авиезри С.; Лихтенштейн, Дэвид (сентябрь 1981 г.), «Вычисление идеальной стратегии в шахматах требует экспоненты времени », Журнал комбинаторной теории , серия A, 31 (2): 199–214, doi : 10.1016/0097-3165(81)90016- 9 ${\displaystyle n\times n}$ ${\displaystyle n}$
5. Робсон, Дж. М. (1983), «Сложность Го», Труды 9-го Всемирного компьютерного конгресса ИФИП по обработке информации : 413–417
6. Робсон, Дж. М. (май 1984 г.), « по шашкам завершено время Exptime», SIAM Journal on Computing , Общество промышленной и прикладной математики ({SIAM}), 13 (2): 252–267, doi : 10.1137/0213018 ${\displaystyle N}$ ${\displaystyle N}$