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

Судоку (9 × 9)

Судоку (25 × 25)

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

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

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

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

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

См. Также [ править ]

Ссылки [ править ]

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

Эта статья по теории игр - незавершенная . Вы можете помочь Википедии, расширив ее .

P ≟ NP

Эта статья по теоретической информатике незавершена . Вы можете помочь Википедии, расширив ее .

[1] Reisch, Стефан (1981), "Hex ист PSPACE-vollständig", Acta Informatica , 15 (2): 167-191, DOI : 10.1007 / bf00288964

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

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

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

[5] Робсон, JM (1983), «Сложность Go», Труды 9-го Всемирного компьютерного конгресса IFIP по обработке информации : 413–417

[6] Робсон, JM (май 1984 г.), « по шашкам завершено Exptime», SIAM Journal on Computing , Society for Industrial & Applied Mathematics ({SIAM}), 13 (2): 252–267, doi : 10.1137 / 0213018 ${\ displaystyle N}$ ${\ displaystyle N}$

[1]