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

Математики играют в Конане на семинаре по теории комбинаторных игр

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

Описание

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

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

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

Литература

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

Ссылки

• История сёги и их вариантов