Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Lecture

Connect Four: α-β Pruning vs Monte-Carlo Tree Search

Description

This lecture presents the application of game theory to solve Connect Four using the minimax algorithm, optimized with α-β pruning, and compared with the Monte-Carlo tree search algorithm. The lecture covers the motivation, principles, and performance analysis of these strategies, concluding with acknowledgments.

Official source

Related concepts (8)

Alpha–beta pruning

Alpha–beta pruning is a search algorithm that seeks to decrease the number of nodes that are evaluated by the minimax algorithm in its search tree. It is an adversarial search algorithm used commonly for machine playing of two-player combinatorial games (Tic-tac-toe, Chess, Connect 4, etc.). It stops evaluating a move when at least one possibility has been found that proves the move to be worse than a previously examined move. Such moves need not be evaluated further.

Minimax

Minmax (sometimes Minimax, MM or saddle point) is a decision rule used in artificial intelligence, decision theory, game theory, statistics, and philosophy for minimizing the possible loss for a worst case (maximum loss) scenario. When dealing with gains, it is referred to as "maximin" – to maximize the minimum gain. Originally formulated for several-player zero-sum game theory, covering both the cases where players take alternate moves and those where they make simultaneous moves, it has also been extended to more complex games and to general decision-making in the presence of uncertainty.

Game theory

Game theory is the study of mathematical models of strategic interactions among rational agents. It has applications in all fields of social science, as well as in logic, systems science and computer science. The concepts of game theory are used extensively in economics as well. The traditional methods of game theory addressed two-person zero-sum games, in which each participant's gains or losses are exactly balanced by the losses and gains of other participants.

Combinatorial game theory

Combinatorial game theory is a branch of mathematics and theoretical computer science that typically studies sequential games with perfect information. Study has been largely confined to two-player games that have a position that the players take turns changing in defined ways or moves to achieve a defined winning condition. Combinatorial game theory has not traditionally studied games of chance or those that use imperfect or incomplete information, favoring games that offer perfect information in which the state of the game and the set of available moves is always known by both players.

Cooperative game theory

In game theory, a cooperative game (or coalitional game) is a game with competition between groups of players ("coalitions") due to the possibility of external enforcement of cooperative behavior (e.g. through contract law). Those are opposed to non-cooperative games in which there is either no possibility to forge alliances or all agreements need to be self-enforcing (e.g. through credible threats). Cooperative games are often analysed through the framework of cooperative game theory, which focuses on predicting which coalitions will form, the joint actions that groups take and the resulting collective payoffs.

Related lectures (27)

Safe Learning for Autonomous Systems

Explores challenges in control, safety, and coordination for autonomous systems like autonomous cars, focusing on safe learning and Nash equilibria.

Solving Connect Four: A-B Pruning and Monte-Carlo Tree Search Log in to Mediaspace to watch this video

Explores applying game theory to optimize strategies in Connect Four using advanced algorithms.

Solving Connect Four: A-B Pruning and Monte-Carlo Tree Search Log in to Mediaspace to watch this video

Explores solving Connect Four using game theory algorithms and compares their efficiency.

Solving Connect Four: Game Theory Strategies Log in to Mediaspace to watch this video

Explores game theory strategies to solve Connect Four efficiently using minimax, alpha-beta pruning, and Monte Carlo methods.

Connect Four: Game Theory Approach Log in to Mediaspace to watch this video