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

Судоку (4×4)

Судоку (9×9)

Судоку (25×25)

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

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

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

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

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

См. также

Ссылки

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

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

П ≟ НП

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

[1] Райш, Стефан (1981), «Hex является PSPACE-полным», Acta Informatica , 15 (2): 167–191, doi : 10.1007/bf00288964 , S2CID 9125259

[2] Ивата, Сигеки; Касаи, Такуми (январь 1994 г.), «Игра Отелло на $n\times n$ доска является PSPACE-полной», Theoretical Computer Science , 123 (2): 329–340, doi : 10.1016/0304-3975(94)90131-7

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

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

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

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

[1]

[2]

[3]

[4]

[5]

[6]