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: Alpha-Beta Pruning and Monte-Carlo Tree Search

Description

This lecture presents the application of game theory to solve Connect Four using the minimax algorithm, optimizing it with alpha-beta pruning, and comparing it with the Monte-Carlo tree search algorithm. The lecture also covers the principles and differences between Monte-Carlo and Alpha-Beta approaches, along with performance comparisons. Special thanks are given to Anna Maddux, Giulio Salizzoni, and Professor Maryam Kamgarpour for their support.

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 (32)

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.

Search algorithm

In computer science, a search algorithm is an algorithm designed to solve a search problem. Search algorithms work to retrieve information stored within particular data structure, or calculated in the search space of a problem domain, with either discrete or continuous values. Although search engines use search algorithms, they belong to the study of information retrieval, not algorithmics. The appropriate search algorithm to use often depends on the data structure being searched, and may also include prior knowledge about the data.

Backpropagation

As a machine-learning algorithm, backpropagation performs a backward pass to adjust the model's parameters, aiming to minimize the mean squared error (MSE). In a single-layered network, backpropagation uses the following steps: Traverse through the network from the input to the output by computing the hidden layers' output and the output layer. (the feedforward step) In the output layer, calculate the derivative of the cost function with respect to the input and the hidden layers.

Simulation

A simulation is the imitation of the operation of a real-world process or system over time. Simulations require the use of models; the model represents the key characteristics or behaviors of the selected system or process, whereas the simulation represents the evolution of the model over time. Often, computers are used to execute the simulation. Simulation is used in many contexts, such as simulation of technology for performance tuning or optimizing, safety engineering, testing, training, education, and video games.

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.

Related lectures (43)

Modeling Prisoner's Dilemma: Naive vs. Optimal

Explores the modeling of the '100 prisoners' problem and compares naive and optimal approaches.

Simulation & Optimization: Poisson Process & Random Numbers

Explores simulation pitfalls, random numbers, discrete & continuous distributions, and Monte-Carlo integration.

Suspension Optimisation: Performance Analysis and Optimization

Explores the design and optimization of car suspensions for improved performance.

Optimization and Simulation: Introduction to Simulation

Introduces state-of-the-art methods in optimization and simulation, covering topics like statistical analysis, variance reduction, and simulation projects.

Optimization and Simulation