Комбинаторная теория игр

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Математики играют в Конане[англ.] на семинаре по теории комбинаторных игр

Комбинаторная теория игр — раздел математики и теоретической информатики, который обычно изучает последовательные игры с идеальной информацией.

Обучение в основном ограничивается играми для двух игроков, в которых игроки по очереди обмениваются определёнными ходами, чтобы достичь определённого условия выигрыша. Традиционно не изучает азартные игры или те, которые используют несовершенную информацию. Однако по мере развития математических методов типы игр, которые можно математически анализировать, расширяются, поэтому границы изучения постоянно меняются. Учёные, как правило, определяют, что они подразумевают под «игрой» в начале статьи, и эти определения часто меняются, поскольку они специфичны для анализируемой игры и не предназначены для представления всего объёма области изучения.

Комбинаторные игры включают в себя известные игры, такие как шахматы, шашки и го, которые считаются нетривиальными, и крестики-нолики, которые считаются тривиальными в смысле «простоты решения». Некоторые комбинаторные игры также могут иметь неограниченную игровую зону, например, бесконечные шахматы[англ.]. В комбинаторной теории игр ходы в этих и в других играх представлены в виде игрового дерева[англ.].

Комбинаторные игры также включают в себя комбинаторные головоломки для одного игрока, такие как судоку, и автоматические игры не для игроков, такие как игра «Жизнь» (хотя в самом строгом определении для «игр» требуется более одного участника, таким образом, появляются обозначения «головоломка» и «автомат»).[1]

Литература

[править | править код]
  • Фролов И. С. Введение в теорию комбинаторных игр. Простейшие комбинаторные игры. Матем. обр., 2012, выпуск 3(63), страницы 38–52.[2]
  • Деорнуа П. Комбинаторная теория игр. М.: МЦНМО, 2017. — 40 с. ISBN 978-5-4439-1172-4.

Примечания

[править | править код]