On the problem of solving multimove games under time deficit

Andrey V. Chernov

Matematičeskaâ teoriâ igr i eë priloženiâ, Tome 11 (2019) no. 2, pp. 96-120

Résumé

On example of antagonistic multimove game we consider the problem of choice by a first player of optimal by possibility strategy of behaviour under deficit of time available for him to make this choice. We suppose that each player makes his move in turn and before each move time available is insufficient to construct all the game tree from this move but it is sufficient to construct a subtree consisting of a limited amount of arcs. Thus we have the problem of a best choice of constructing strategy for this subtree and corresponding restriction of a subsequent game. We suppose that after the subtree pointed out above is constructed each player chooses his move on the base of calculations with the help of Kuhn algorithm for a game on this subtree. We consider two ways for constucting the subtree. The first one is naive way based on constructing a full tree for “uniform” restriction of the game to lesser amount of moves. The second one is based on probabilistic selection for subsequent branching of most “perspective” arcs with origin at current vertex. We prove that the first way can lead to arbitrary big miscalculations of a player. As to the second way we prove that the first player using it, in spite of rectricting his prior possibilities, forces the opponent player to act in the frame of a subgame selected and calculated for essentially larger amount of moves by the first player and this selection is made as expected best (in the probabilistic sense). Theoretical (obvious enough) reasoning is confirmed by some concrete example of antagonistic game on a tree graph and also by work results of an author computer program realizing the draughts game.

Détail

Keywords: multimove game under time deficit, Kuhn algorithm, expected best choice of game subtree.