紀要論文 Sure Ways to Win a Game ? Nondeterministic Dynamic Programming Approach ?

Fujita, Toshiharu

62pp.1 - 14 , 2015-03-31
ISSN:1343-8670
内容記述
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.
本文を読む

http://ds.lib.kyutech.ac.jp/dspace/bitstream/10228/5340/1/math62_p1_14.pdf

このアイテムのアクセス数:  回

その他の情報