FOUNDATIONS OF POSITIONAL GAMES

This is the third piece of a series of papers about a new, quasiprobab ilistic theory of positional games (i.e., ''combinatorial games''). Th e strange thing is that we wrote these papers in reverse order. Chrono logically the first paper, ''Deterministic Graph Games and a Probabili stic Intuition,'' was a highly technical one, and can be considered as part III of the series. The next paper, ''Achievement Games and the P robabilistic Method,'' was a survey that attempted to explain the role of the subject in discrete mathematics. We felt, however, that we did not quite succeed, and somehow the foundations were not very solid. T his is why we had to write this paper, which should be considered as p art I of the series. Our main object here is to explain what the basic questions of positional game theory are. The well-known algebraic the ory of Nim-like games (called ''combinatorial game theory'') and the q uasiprobabilistic theory represent two entirely different viewpoints, and they in some sense complement each other. Indeed, combinatorial ga me theory (i.e., Nim-like games) is an exact local theory in the sense how seemingly complicated games start out as composites, or quickly d evelop into composites of several simple local games. On the other han d, the quasi-probabilistic theory attempts to solve ''hopelessly compl icated'' Tic-Tac-Toe-like games which usually remain as single coheren t entities throughout play. It is an efficient global approach which, roughly speaking, evaluates via loss probabilities. Because of the int ractable complexity of the exhausting search through the game-tree, an efficient evaluation method has to approximate. So one cannot really expect from the quasiprobabilistic theory to solve evenly balanced ''h ead-to-head games,'' where a single mistake could be fatal, but it can effectively recognize and solve large classes of difficult ''one-side d games.'' Positional games are finite 2-player games of skill (i.e., no chance moves) with perfect information, and the payoff function has three values 1, 0, -1 only (''win,'' ''draw,'' ''loss''). These games , therefore, are deterministic, and because of the perfect information , the optimal strategies are deterministic. How can randomness then en ter the story? To answer this, we very briefly summarize the simplest case of the quasi-probabilistic theory: the majority principle. The ma jority principle is in two parts. The first part is a probabilistic in tuition that says in a nutshell that, in many complicated games, the o utcome between two perfect players is the same as the ''majority outco me'' between two ''random players'' (random game). The point is that e ven relatively simple games are too hopelessly complicated to analyze in full depth. but to describe the ''typical'' behavior is usually a t ractable problem to solve by using probability theory. However, the ma jority principle is more than merely predicting tile outcomes of compl icated games. The second part is to convert the probabilistic intuitio n, via potential techniques, into effective deterministic strategies, in fact, greedy algorithms. (C) 1996 John Wiley & Sons, Inc.