Обобщенная игра - Generalized game - Wikipedia

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

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

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

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

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

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

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

  1. ^ Райш, Стефан (1981), "Hex ist PSPACE-vollständig", Acta Informatica, 15 (2): 167–191, Дои:10.1007 / bf00288964
  2. ^ Ивата, Шигеки; Касаи, Такуми (январь 1994 г.), "Игра Отелло на плата 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 г.), "Вычисление идеальной стратегии для шахматы требуют экспоненциального времени в ", Журнал комбинаторной теории, Серия А, 31 (2): 199–214, Дои:10.1016/0097-3165(81)90016-9
  5. ^ Робсон, Дж. М. (1983), «Сложность го», Материалы 9-го Всемирного компьютерного конгресса ИФИП по обработке информации: 413–417
  6. ^ Робсон, Дж. М. (май 1984 г.) " к шашки завершен Exptime ", SIAM Журнал по вычислениям, Общество промышленной и прикладной математики ({SIAM}), 13 (2): 252–267, Дои:10.1137/0213018