Сложность игры

• Сложности комбинаторной теории игр

  • Сложность пространства состояний: количество допустимых позиций 
  • Размер игрового дерева: количество возможных игр 
  • Сложность принятия решения: количество конечных узлов в дереве решений 
  • Сложность игрового дерева: количество конечных узлов в полноразмерном дереве решений 
  • Вычислительная сложность: асимптотическая сложность игры 

• Показатели сложности

  • Размер игрового дерева: количество конечных узлов в дереве 

• Примеры игр и их сложности

  • Крестики-нолики: сложность пространства состояний 39, размер игрового дерева 9! 
  • Обобщенные крестики-нолики: сложность PSPACE 
  • Другие известные игры: сложность варьируется в зависимости от правил и размера игрового дерева