Обобщенная игра - Википедия - Generalized game

Судоку (4 × 4)

Судоку (9 × 9)

Судоку (25 × 25)

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

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

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

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

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

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

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

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

Этот теория игры статья - это заглушка. Вы можете помочь Википедии расширяя это.

P ≟ NP

Этот теоретическая информатика –Связанная статья является заглушка. Вы можете помочь Википедии расширяя это.

[1] Райш, Стефан (1981), "Hex ist PSPACE-vollständig", Acta Informatica, 15 (2): 167–191, Дои:10.1007 / bf00288964

[2] Ивата, Шигеки; Касаи, Такуми (январь 1994 г.), "Игра Отелло на ${ Displaystyle п раз п}$ плата PSPACE-полная », Теоретическая информатика, 123 (2): 329–340, Дои:10.1016/0304-3975(94)90131-7

[3] Мишиба, Шохей; Такенага, Ясухико (02.07.2020). "QUIXO завершен EXPTIME". Письма об обработке информации: 105995. Дои:10.1016 / j.ipl.2020.105995. ISSN 0020-0190.

[4] Fraenkel, Aviezri S .; Лихтенштейн, Дэвид (сентябрь 1981 г.), "Вычисление идеальной стратегии для ${ Displaystyle п раз п}$ шахматы требуют экспоненциального времени в ${ displaystyle n}$ ", Журнал комбинаторной теории, Серия А, 31 (2): 199–214, Дои:10.1016/0097-3165(81)90016-9

[5] Робсон, Дж. М. (1983), «Сложность го», Материалы 9-го Всемирного компьютерного конгресса ИФИП по обработке информации: 413–417

[6] Робсон, Дж. М. (май 1984 г.) " ${ displaystyle N}$ к ${ displaystyle N}$ шашки завершен Exptime ", SIAM Журнал по вычислениям, Общество промышленной и прикладной математики ({SIAM}), 13 (2): 252–267, Дои:10.1137/0213018

[1]

[2]

[3]

[4]

[5]

[6]