| Abstract: |  Game theory is science not only for modeling games such as Chess, Poker or Backgammon compute its solutions but it can also provide useful tools for modeling and solving real life problems that we are not aware of at the first sight. For example, one problem from this category is borders patrolling. These problems are linked because each of them includes huge state space which has to be searched in order to find an optimum solution that maximizes possible payoff under the assumption that opponent acts rationally.
The aim of this work is to design and experimentally evaluate the performance of a parallel version of the algorithm from framework developed by ATG group from FEE, CTU. This algorithm uses double-oracle framework, which narrows searched state space by allowing only some strategies to be played by players. The algorithm solves two-player zero-sum games with imperfect information. Before proposing a parallel design an analysis of the algorithm and a survey of known parallel search techniques on two-players game trees are investigated. Parallel version should contribute by shorter computation time allowing faster computation of exploitability of heuristic strategies in imperfect-information games. Simplified, exploitability expresses distance of a strategy from optimum. When comparing two strategies, the one with lower exploitability is better.
Experiments show that parallel design proposed in this work achieved speed up of 2.2.
|
|---|