Departmental Bulletin Paper Sure Ways to Win a Game ? Nondeterministic Dynamic Programming Approach ?

Fujita, Toshiharu

62pp.1 - 14 , 2015-03-31
Surefire strategies for winning a two-player pyramid game are found by a nondeterministic dynamic programming approach. The game is simple. Initially, vertical bars are arranged as a lower triangular matrix whose nonzero elements are 1. Two players take turns in marking the bars on the basis of a given set of rules. The player marking the last bar loses. In our dynamic programming formulation, a state denotes the current situation of the player who moves first. The next state depends on the opponent’s unknown decision. In general, the first player must simultaneously consider multiple states in the next turn. Therefore, a dynamic programming formulation of this problem requires nondeterministic transition. We show that the problem becomes equivalent to minimizing the max-add criterion under nondeterministic transition. The optimal solutions then provide the shortest surefire strategies.

Number of accesses :  

Other information