A Probabilistic Theory of Positional Games

点击翻译按钮获取中文摘要

9626151 Beck ABSTRACT In this proposal the investigator outlines a new, probabilistic approach to positional games (i.e. board-games, or combinatorial games). The straightforward way to analyze a position is to examine all of its options and all the options of these options and all the options of the options of these options and all the.... The obvious difficulty is that this exhausting search through the game-tree takes an enormous amount of time even for very simple games (exponential running time in terms of the board-size). Note that the game-matrix approach, the set-up of traditional game theory, is much worse: usually requiring double exponential time. A desperate attempt to make up for the lack of time is to study the random walk on the game-tree. Now the basic idea of the probabilistic theory of the investigator is that the probabilistic analysis of the random walk (i.e. the random game) is often a tractable problem, and also what one has learned from this analysis can often be converted, via potential arguments (like resource counting with loss-probabilities), into deterministic optimal strategies. The probabilistic theory is basically a game-theoretic adaptation of the so-called Probabilistic Method in Combinatorics applied to hopelessly complicated games where algebraic and other exact methods fail to work. The surprising thing is that this desperate attempt turns out to be very successful for large, interesting classes of positional games. The main chapters of the proposal are: the foundations of positional games (a surprisingly non-trivial task), game-theoretic Ramsey theory, game-theoretic random graph theory, game-theoretic Lovasz Local Lemma, and applications in algorithms and complexity. Traditional game theory, i.e. von Neumann's theory, is basically the theory of games of incomplete information. It provides good insights to Economics, and many areas of social science (Management, Military Strategy, etc.). Similarly, one can expect many new applications from a successfu l theory of games of complete information (i.e. positional games). This is exactly what the investigator's proposal is all about. An extremely exciting aspect of studying positional games is that it might give a better understanding of how human intelligence works. It might have some impact on fundamental questions like whether human understanding is a computational or a non-computational process. Note that in Japan there are several "perfect" players who, when playing first, can consistently win Go-Moku (5-in-a-row on the 19 by 19 Go board), but nobody can turn these heuristics into precise arguments. Similarly, 6-in-a-row on a sufficiently large board between two reasonably good players is always a boring draw-game, but again we cannot precisely explain why. Or what is the reason that Go-playing computer programs are nowhere close to the best human players? These are just three of many examples where the human mind "knows" something beyond rigorous mathematics. One more thing: in contrast to Go, the best Chess-playing computer programs have now reached the level of human Grandmasters. But there is a basic difference. Computer programs examine millions of positions before deciding what to do next. On the other hand, even the best Grandmasters do not search more than 100 positions per move. In human Chess, pattern recognition plays a more important role than search. How to supply this human knowledge to a computer is a puzzle that no one has solved yet. Beside its theoretical importance, the investigator's project could be a crucial step toward the solution of these questions, too.