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

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

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

В теории вычислительной сложности обобщенная игра — это игра или головоломка, обобщенная таким образом, что в нее можно играть на доске или сетке любого размера. Например, обобщенные шахматы — это игра в шахматы, в которую играют на доске с фигурами на каждой стороне. Обобщенные судоку включают судоку, построенные на сетке. ${\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-полной», Теоретическая информатика , 123 (2): 329–340, doi :10.1016/0304-3975(94)90131-7 ${\displaystyle n\times n}$
3. Mishiba, Shohei; Takenaga, Yasuhiko (2020-07-02). «QUIXO is EXPTIME-complete». Information Processing Letters . 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-го Всемирного компьютерного конгресса IFIP по обработке информации : 413–417
6. Робсон, Дж. М. (май 1984 г.), « by checkers is Exptime complete», SIAM Journal on Computing , 13 (2), Общество промышленной и прикладной математики ({SIAM}): 252–267, doi :10.1137/0213018 ${\displaystyle N}$ ${\displaystyle N}$