• 98

Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.



Difficulty: Medium
Topic: Minimax algorithm, Alpha–beta pruning, Zero-sum games, Negamax

We are given a 2-player, zero-sum game, where players alternate turns. The game always lasts D turns, and during its move, every player has to choose from B choices. Thus, D is the game tree depth, B its branching factor, and depending on players' choices, the game has B^D possible outcomes.

Assuming the game tree is small enough, we can check all outcomes and solve the game (i.e. compute the best strategy for every player) using the Minimax algorithm ( ).

To make our algorithm more efficient, we can skip some computations using the alpha-beta prunning technique ( ).

Your task is to compute the minimum gain for the first player using Minimax with alpha-beta cutoffs. Moves should be examined in left-to-right order, as provided in the input.
Line 1: 2 space-separated integers:
D - depth of the game tree (assuming root is depth 0)
B - the branching factor

Line 2: B^D space-separated integers - the leafs of the game tree containing scores of the first (max) player.
Two space-separated numbers:
- the best score that the root player is guaranteed to obtain
- the number of visited tree nodes
0 < D < 15
0 < B < 15
-1000 < game score < 1000
number of leafs < 3500
1 4
2 -1 3 0
3 5

A higher resolution is required to access the IDE

codingame x discord
Join the CodinGame community on Discord to chat about puzzle contributions, challenges, streams, blog articles - all that good stuff!
Online Participants