Deterministic Games

Deterministic games are those that contain no elements of chance.

This is understood in the context of game mechanics, and distinct from uncertainty of outcome in non-trivial games.

Chance is introduced into games in two main forms: random number generation (such as dice or card shuffling) and hidden information (such as hidden cards or unknown positions.) These two methods may be utilized exclusively, as with Backgammon (random number generation but perfect information), Battleship (no randomness but hidden board positions), Stratego (perfect information but hidden token values), or together, as in Poker (random card sequence and hidden information.)

Nature is often used in random number generators such as dice in the sense that, although the roll of a die is ultimately deterministic, it involves "factors beyond calculation". This is to say that, although the technique itself is be deterministic, the intractability of the technique requires its utilization to know the outcome, which may only be determined by observing the result.  Physicists refer to this as a "chaotic system".

Hidden information presents a distinct type of indeterminacy, which may be said to be deterministic in that the state is defined, and merely unknown. (Undetermined outcome per hidden information is decision based, which is to say voluntary, where randomness in the sense of "luck" is involuntary.)  Hidden information may further be broken into two distinct categories: imperfect information and incomplete information.

The key distinction is that probability arising in the context of hidden information only does not necessarily make a game non-deterministic.  The case of Battleship demonstrates how the opponent's positions may be unknown (imperfect information) but the positions are fixed, which is to say pre-determined.  

Where hidden information in relation to determinism becomes stickier is in the case of simultaneous games such as non-iterated Prisoner's Dilemma, which contain incomplete information (per the inability to know the opponent's choice prior to interaction) but deterministic mechanics in the form of a pre-defined payoff matrix.

A game like Rock, Paper, Scissors functions as a random number generator because the probability of a win loss or draw on any given round is 1/3 (not accounting for meta-strategies, which, in any case, are unstable.)

True randomness, which requires an outcome independent of causation, only exists at the quantum level, and in special cases.  Even at the quantum level, indeterminacy is largely a function of observation and the limiting factor of the speed of light.

Richard Garfield makes the point that luck can never be entirely removed from an unsolved game—from a strategic perspective, given enough iterations, a strategy based on purely random choices will result in a win.  (This is a factor of the game being unsolved.  Specifically, a player making strategic choices in the context of an unsolved game can only know if the choices are more or less optimal than an opponent's choices, but not whether they are objectively optimal, as in the case of a solved game.  The idea that a random strategy will eventually result in a win is analogous the the "Infinite monkey theorem";)

All games, at the fundamental level, are algorithms, and algorithms that always produce the same result for a given set of inputs are deterministic, regardless of whether the inputs are random. 

命运

Determinism, in the classical sense, is inherently temporal, and when we think about deterministic games, we tend to think of those that are sequential.

Of the fundamental, sequential forms of deterministic playgames, which are among the oldest games known, there is a special class of "non-chance, perfect information" games. 

This special class, which are games of pure skill, includes Tic-tac-toe, Checkers, Chess, and Go.  These games are combinatorial, and are further termed partisan in that each player has a unique set of choices.  The most common expression of partisanism in games is the restriction of a given player to a subset of a set of tokens (x's and o's, black vs. white, etc.)

All of these games contain perfect information which means that all current and previous positions (game states) are known to all competitors.

Impartial forms of deterministic games include Mancala, which some claim to be the oldest board game (although there is compelling evidence for Tic-Tac-Toe;) Nim, another famous impartial game, provided the foundational for Combinatorial Game Theory in the Sprague-Grundy theorem.

The distinction between partisan and impartial games is whether the same moves are available to all competitors. In impartial games the only difference between players may be turn.

In the strictest definition, games are said to require multiple competitors.  Puzzles, which are commonly regarded as games, are distinct.  (Multiple participants may collaborate to solve puzzles, but this is distinct from competition.  Competitive puzzle solving, however, does constitute a proper game.)  Determinism may be said to be a requirement of classical puzzles in that the outcome is pre-determined.

Combinatorial puzzles such as Sudoku are of great interest mathematically, and also constitute a popular form of mental stimulation.  Latin squares were an obsession of Euler's, and The Seven Bridges of Königsberg, an extremely famous combinatorial puzzle, laid the foundations for graph theory and prefigured the field of topology.  (For those who don't know of him, Euler was a badass--two mathematical constants bear his name.)

There is another, special class of game that are said to involve no players, known as cellular automata.  In the strictest sense, this definition means no human players—automata may be said to be players, and commonly are.

Conway's Game of Life may, might be regarded as non-classical puzzle, a single player endeavor where outcomes are arrived at deterministically, but knowable only by playing out the sequence. (Each ply on the Game of Life tree has only one node, and expressing the game tree is indistinguishable from playing the game.)  Non-trivial starting configuration in Life produce a chaotic system.

Typically, deterministic games are between two players, but there is no restriction, demonstrated by "Chinese Checkers" and [M]. Thus, the most reduced categorization of games in regard to participants may be single player and multiplayer.

Traditionally, the conception of combinatorial games has been restricted to those which are non-chance and perfect information, but as mathematics has advanced, analysis of games involving chance, notably poker, has widened the definition. (Blackjack was certainly a precursor, and card counting is a popular form of mathematical analysis of games.)

Combinatorial games and puzzles which are deterministic are commonly believed to be intelligence building, with special prestige afforded to those with perfect information. In the case of non-trivial variants such as Chess and Go, high level play is associated with genius. 

Partisan, sequential, deterministic games of perfect information are important in the development of Artificial Intelligence. Nimatron may be the first game AI, which is to say the first algorithmic intelligence, but it was Deep Blue's Chess play that captured the imagination of the world. More recently, AlphaGo served as a proof-of-concept for Machine Learning as a method of managing computational intractability, which is to say indeterminacy, a function of its ability to beat the top humans in a context with complexity akin to nature. (Legend holds that if all of the atoms in the known universe were converted into bits, and the engine were given the entire duration of this universe to process, the complete Go gametree could not be expressed.) Not to be forgotten is Giraffe Chess, an algorithmic intelligence that taught itself to play Chess at an International Master level in 72 hours.

Thus deterministic games may be said to be the most useful type of game.

Where disequilibrium may be the primary requirement of games (without imbalance, there is no action,) and balanced asymmetry may be said to be the "hook" (the incentive to play is the possibility of a win,) complexity is the equalizer.

Complexity is the element that adds indeterminacy to purely deterministic games. The inability of the participants to grasp to complete gametree is what allows the possibility for any given player to engineer a victory. (This, of course, so long as the asymmetry is effectively balanced--too much balance and the game results in stalemate—too little balance and the game always results in win for the advantaged player.)

The mathematics are unforgiving, but complexity is more powerful.

Complexity is what makes a game difficult to solve, which is to say a riddle. Complexity provides depth, which generates nuance. This emergent complexity has, in some cases, captivated human minds for millennia.

Complexity is a tool of unbounded potential, and equally unwieldy, as evidenced by the scarcity of compelling sets of purely deterministic mechanics. The balance is delicate—too much complexity and the game is bewildering—too little and the game is easily solved.

A game is only interesting when it is enigmatic.  This is to say the game is unsolved, or that the solution is unknown to the participants, or the solution is too complex to be processed. Such games are said to be non-trivial, although the categorization is subjective. (To the average five year old, Tic-tac-toe is distinctly non-trivial!)

For the most part, non-trivial games are said to be those that are intractable to the strongest human players. Intractability may be understood as "effective infinity" in the sense of functional indeterminacy.  This is the power of the game to defy determinism and reflects the interaction of the mind with the infinite.

No data is collected by this page

www.deterministicgames.com