Game complexity | EPFL Graph Search

Are you an EPFL student looking for a semester project?

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Combinatorial game theory measures game complexity in several ways: State-space complexity (the number of legal game positions from the initial position), Game tree size (total number of possible games), Decision complexity (number of leaf nodes in the smallest decision tree for initial position), Game-tree complexity (number of leaf nodes in the smallest full-width decision tree for initial position), Computational complexity (asymptotic difficulty of a game as it grows arbitrarily large). These measures involve understanding game positions, possible outcomes, and computation required for various game scenarios. The state-space complexity of a game is the number of legal game positions reachable from the initial position of the game. When this is too hard to calculate, an upper bound can often be computed by also counting (some) illegal positions, meaning positions that can never arise in the course of a game. The game tree size is the total number of possible games that can be played: the number of leaf nodes in the game tree rooted at the game's initial position. The game tree is typically vastly larger than the state space because the same positions can occur in many games by making moves in a different order (for example, in a tic-tac-toe game with two X and one O on the board, this position could have been reached in two different ways depending on where the first X was placed). An upper bound for the size of the game tree can sometimes be computed by simplifying the game in a way that only increases the size of the game tree (for example, by allowing illegal moves) until it becomes tractable. For games where the number of moves is not limited (for example by the size of the board, or by a rule about repetition of position) the game tree is generally infinite. The next two measures use the idea of a decision tree, which is a subtree of the game tree, with each position labelled with "player A wins", "player B wins" or "drawn", if that position can be proved to have that value (assuming best play by both sides) by examining only other positions in the graph.

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (2)

In this paper we view the possibilities to lance a multiple (iterative) birthday attack on NTRU. Recently Wagner's algorithm for the generalized birthday problem [9] allowed to speed-up several combin

Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa2009

A multiple birthday attack on NTRU

In this paper we view the possibilities to lance a multiple (iterative) birthday attack on NTRU. Recently Wagner's algorithm for the generalized birthday problem (Wagner, 2002) allowed to speed-up sev

Insticc-Inst Syst Technologies Information Control & Communication, Avenida D Manuel L, 27A 2 Esquerdo, Setubal, 2910-595, Portugal2008

Related concepts (18)

Related courses (2)

CS-430: Intelligent agents

Software agents are widely used to control physical, economic and financial processes. The course presents practical methods for implementing software agents and multi-agent systems, supported by prog

PHYS-435: Statistical physics III

This course introduces statistical field theory, and uses concepts related to phase transitions to discuss a variety of complex systems (random walks and polymers, disordered systems, combinatorial o

Related lectures (11)

Gomoku

Gomoku, also called Five in a Row, is an abstract strategy board game. It is traditionally played with Go pieces (black and white stones) on a Go board. It is played using a 15×15 board while in the past a 19×19 board was standard. Because pieces are typically not moved or removed from the board, gomoku may also be played as a paper-and-pencil game. The game is known in several countries under different names. Players alternate turns placing a stone of their color on an empty intersection. Black plays first.

Go (game)

Go is an abstract strategy board game for two players in which the aim is to surround more territory than the opponent. The game was invented in China more than 2,500 years ago and is believed to be the oldest board game continuously played to the present day. A 2016 survey by the International Go Federation's 75 member nations found that there are over 46 million people worldwide who know how to play Go, and over 20 million current players, the majority of whom live in East Asia. The playing pieces are called stones.

Abstract strategy game

Abstract strategy games in contrast to strategy games in general usually have no or minimal narrative theme, outcomes determined only by player choice (with no randomness), and all players have perfect information about the game. For example, Go is a pure abstract strategy game since it fulfills all three criteria; chess and related games are nearly so but feature a recognizable theme of ancient warfare; and Stratego is borderline since it is deterministic, loosely based on 19th-century Napoleonic warfare, and features concealed information.

Deliberative Agents: Planning and Strategies

Covers planning with adversaries, heuristic search algorithms, and strategies for games with chance, emphasizing the significance of deliberative agents.

Introduction to Game Theory

Covers game theory fundamentals, Nash equilibrium, and strategic interactions in multi-agent systems.

Connect Four: Alpha-Beta Pruning and Monte-Carlo Tree Search

Explores solving Connect Four using game theory and algorithms for optimal strategy in minimum time.