Convergence Characteristics of Fictitious Play in a Search Game

摘要

In this thesis the convergence characteristics of an iterative method for solving area search games were investigated. This method, Fictitious Play, was first introduced by G. W. Brown and solves two-person zero-sum games by having each player sequentially select a pure strategy based on the combined past actions of his opponent. The Fictitious Play method was successfully implemented for an area search game in which two players, a searcher and a target, move independently through an area. In this game, the payoff is the number of detections of the target by the searcher. For each iteration of the game, an upper and lower bound on the value of the game were determined and as the number of iterations of the game increased, these bounds converged to the actual solution. In the games examined, the convergence of the bounds was closely approximated by a power function, with large games converging more slowly. Because of the observed symmetrical convergence of the bounds, an accurate approximation of the value of the game was obtainable from the average of the upper and lower bounds.(kr)