О проблеме решения многошаговых игр в условиях дефицита времени

На примере антагонистической многошаговой игры рассматривается проблема выбора первым игроком по возможности оптимальной стратегии поведения в условиях дефицита времени, которым он располагает для осуществления этого выбора. Предполагается, что игроки делают ходы поочередно и перед началом каждого хода времени, которое имеется в их распоряжении для его выбора, недостаточно для построения всего дерева развития игры, а достаточно лишь для построения поддерева, состоящего из ограниченного количества дуг. Поэтому встает проблема наилучшего выбора стратегии построения этого поддерева и соответствующего сужения дальнейшей игры. Предполагается, что после построения указанного поддерева каждый игрок производит выбор своего хода на основании расчетов по алгоритму Куна для игры на этом поддереве. Рассматривается два способа построения поддерева. Первый — наивный способ, основанный на построении полного дерева для «равномерного» сужения игры на меньшее количество ходов. Второй способ основан на вероятностном отборе для дальнейшего ветвления наиболее «перспективных» дуг, исходящих из текущей вершины. Доказывается, что первый способ может приводить к сколь угодно большим просчетам игрока. Для второго способа доказывается, что игрок, хотя и сужает свои априорные возможности, вынуждает другого игрока действовать в рамках выбранной первым игроком подыгры, для которой им произведен полный расчет на существенно большее количество ходов вперед и при этом выбор поддерева произведен как ожидаемо наилучший (в вероятностном смысле). Теоретические (довольно прозрачные) рассуждения подкрепляются конкретным примером антагонистической игры на древовидном графе, а также результатами работы авторской программы, реализующей игру в шашки.