Lecture

Solving Connect Four: Game Theory Strategies

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Description

This lecture presents the application of game theory to solve the two-player zero-sum game Connect Four. Starting with the minimax algorithm, the instructor optimizes it using alpha-beta pruning and compares it with the Monte-Carlo tree search algorithm. The lecture discusses the principles of alpha-beta pruning, the differences between minimax and alpha-beta pruning in terms of running time, and the principles of Monte Carlo methods. It also compares Monte Carlo with alpha-beta in terms of systematic computing, information processing, and computational efficiency. The lecture concludes with acknowledgments to individuals who supported the project.

This video is available exclusively on Mediaspace for a restricted audience. Please log in to MediaSpace to access it if you have the necessary permissions.

Watch on Mediaspace

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)

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

Explores solving Connect Four using game theory algorithms to find optimal strategies efficiently.

Introduction to Game Theory

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

Game Theory: Stackelberg and Backward Induction

Discusses Stackelberg games and backward induction, illustrating game theory concepts through examples and applications in real-world scenarios.

Markov Games: Concepts and Applications in Reinforcement Learning

Covers Markov games, their dynamics, equilibria, and applications in reinforcement learning.

Separating Hyperplanes: Theory and Applications