Game theory for coding
minimax algo
The minimax algorithm is a decision-making algorithm used in two-player turn-based games like tic-tac-toe, chess, and checkers. It’s designed to find the optimal move for a player, assuming that the opponent also plays optimally.
This algorithm assumes that there are two players. One player is acting as MAX and second is acting as MIN. MAX will maximize (point or reward i.e. choose best move) own chances of winning (or getting the highest score). MIN will minimize (point or reward i.e. choose worst move) the opponent’s chances of winning (or minimize their score).
Note: Here MIN is not making worst move for themselves. It is making move so that opponent’s score can be minimize.
Game Tree: The algorithm explores all possible moves and counter-moves, constructing a game tree where each node represents a game state. Following is one example.
Following is pseudo code for minimax algo.
def minimax(state, depth, is_maximizer):
# Base case: terminal state or depth limit reached
if is_terminal(state) or depth == 0:
return evaluate(state)
# Maximizer's turn
if is_maximizer:
best_score = -infinity # Goal is to maximize it's score
for move in possible_moves(state):
new_state = make_move(state, move)
score = minimax(new_state, depth - 1, False)# Recursive call
best_score = max(best_score, score) # Post order traversal
return best_score
# Minimizer's turn
else:
best_score = +infinity # Goal is to minimize opponent's score
for move in possible_moves(state):
new_state = make_move(state, move)
score = minimax(new_state, depth - 1, True)
best_score = min(best_score, score)
return best_scoreNote: Sometime both player perform the same steps, therefore above code gets optimize with same block.
486. Predict the Winner
https://leetcode.com/problems/predict-the-winner/
You are given an integer array nums. Two players are playing a game with this array: player 1 and player 2.
Player 1 and player 2 take turns, with player 1 starting first. Both players start the game with a score of 0. At each turn, the player takes one of the numbers from either end of the array (i.e., nums[0] or nums[nums.length - 1]) which reduces the size of the array by 1. The player adds the chosen number to their score. The game ends when there are no more elements in the array.
Return true if Player 1 can win the game. If the scores of both players are equal, then player 1 is still the winner, and you should also return true. You may assume that both players are playing optimally.
Example 1:
Input: nums = [1,5,2]
Output: false
Explanation: Initially, player 1 can choose between 1 and 2.
If he chooses 2 (or 1), then player 2 can choose from 1 (or 2) and 5. If player 2 chooses 5, then player 1 will be left with 1 (or 2).
So, final score of player 1 is 1 + 2 = 3, and player 2 is 5.
Hence, player 1 will never be the winner and you need to return false.Approach# Use minimax algorithm
Player#1 can try to maximize the score by taking the positive value. Player#2 will minimize the opponent score by taking the negative value and minimizing the score. Following is code for reference.
class Solution {
private:
int miniMax(vector<int>& nums, int left, int right, bool isPlayer1) {
// Base case: Terminal node
if(left > right) {
return 0;
}
// Player#1 will try to maximimize the score
if(isPlayer1) {
// Get max score form all the possible moves
int move1 = nums[left]+ miniMax(nums, left+1, right, false);
int move2 = nums[right] + miniMax(nums, left, right-1, false);
return max(move1, move2);
}
// Player#2 will try to minimize the score for player#1 by returning negative score
int move1 = -nums[left]+ miniMax(nums, left+1, right, true);
int move2 = -nums[right] + miniMax(nums, left, right-1, true);
return min(move1, move2);
}
public:
bool predictTheWinner(vector<int>& nums) {
int n = nums.size();
int score = miniMax(nums, 0, n-1, true);
return score >=0;
}
};877. Stone Game
https://leetcode.com/problems/stone-game/description/
Alice and Bob play a game with piles of stones. There are an even number of piles arranged in a row, and each pile has a positive integer number of stones piles[i].
The objective of the game is to end with the most stones. The total number of stones across all the piles is odd, so there are no ties.
Alice and Bob take turns, with Alice starting first. Each turn, a player takes the entire pile of stones either from the beginning or from the end of the row. This continues until there are no more piles left, at which point the person with the most stones wins.
Assuming Alice and Bob play optimally, return true if Alice wins the game, or false if Bob wins.
Example 1:
Input: piles = [5,3,4,5]
Output: true
Explanation:
Alice starts first, and can only take the first 5 or the last 5.
Say she takes the first 5, so that the row becomes [3, 4, 5].
If Bob takes 3, then the board is [4, 5], and Alice takes 5 to win with 10 points.
If Bob takes the last 5, then the board is [3, 4], and Alice takes 4 to win with 9 points.
This demonstrated that taking the first 5 was a winning move for Alice, so we return true.Approach# Apply minimax with memoization
Similar to above problem, we can apply minimax algorithm here. Following is code for reference.
class Solution {
private:
int miniMax(vector<int>& piles, int left, int right, bool isAlice,
unordered_map<string, int>& dp) {
if (left > right) {
return 0;
}
string key =
to_string(left) + "-" + to_string(right) + "-" + to_string(isAlice);
if (dp.count(key) > 0) {
return dp[key];
}
if (isAlice) {
int move1 =
piles[left] + miniMax(piles, left + 1, right, false, dp);
int move2 =
piles[right] + miniMax(piles, left, right - 1, false, dp);
int score = max(move1, move2);
dp[key] = score;
return score;
}
int move1 = -piles[left] + miniMax(piles, left + 1, right, true, dp);
int move2 = -piles[right] + miniMax(piles, left, right - 1, true, dp);
int score = min(move1, move2);
dp[key] = score;
return score;
}
public:
bool stoneGame(vector<int>& piles) {
int n = piles.size();
unordered_map<string, int> dp;
int score = miniMax(piles, 0, n - 1, true, dp);
return score > 0;
}
};1025. Divisor Game
https://leetcode.com/problems/divisor-game/description/
Alice and Bob take turns playing a game, with Alice starting first.
Initially, there is a number n on the chalkboard. On each player's turn, that player makes a move consisting of:
- Choosing any
xwith0 < x < nandn % x == 0. - Replacing the number
non the chalkboard withn - x.
Also, if a player cannot make a move, they lose the game.
Return true if and only if Alice wins the game, assuming both players play optimally.
Example 1:
Input: n = 2
Output: true
Explanation: Alice chooses 1, and Bob has no more moves.Approach# using minimax algorithm
class Solution {
private:
int minimax(int n, bool isAlice, unordered_map<string, int>& dp) {
// Base case
if (n <= 1) {
return 0;
}
string key = to_string(n) + "-" + to_string(isAlice);
if (dp.count(key) > 0) {
return dp[key];
}
if (isAlice) {
// Alice will try to maximize her score
int score = INT_MIN;
for (int x = 1; x < n; x++) {
if (n % x == 0) {
score = max(score, x + minimax(n - x, false, dp));
}
}
dp[key] = score;
return score;
}
// Bob will try to minimize Alice's score
int score = INT_MAX;
for (int x = 1; x < n; x++) {
if (n % x == 0) {
score = min(score, -x + minimax(n - x, true, dp));
}
}
dp[key] = score;
return score;
}
public:
bool divisorGame(int n) {
unordered_map<string, int> dp;
int score = minimax(n, true, dp);
return score > 0;
}
};292. Nim Game
https://leetcode.com/problems/nim-game/description/
You are playing the following Nim Game with your friend:
- Initially, there is a heap of stones on the table.
- You and your friend will alternate taking turns, and you go first.
- On each turn, the person whose turn it is will remove 1 to 3 stones from the heap.
- The one who removes the last stone is the winner.
Given n, the number of stones in the heap, return true if you can win the game assuming both you and your friend play optimally, otherwise return false.
Example 1:
Input: n = 4
Output: false
Explanation: These are the possible outcomes:
1. You remove 1 stone. Your friend removes 3 stones, including the last stone. Your friend wins.
2. You remove 2 stones. Your friend removes 2 stones, including the last stone. Your friend wins.
3. You remove 3 stones. Your friend removes the last stone. Your friend wins.
In all outcomes, your friend wins.Approach#1: minimax using recursion (stack overflow)
class Solution {
private:
bool minimax(int n, bool isPlayer1, unordered_map<string, bool>& dp) {
// Base case: looser
if (n < 1) {
return false;
}
string key = to_string(n) + "-" + to_string(isPlayer1);
if (dp.count(key) > 0) {
return dp[key];
}
if (isPlayer1) {
// Will try to maximize score
for (int stones = 1; stones <= 3; stones++) {
if (n - stones >= 0) {
if (!minimax(n - stones, false, dp)) {
dp[key] = true;
return true;
}
}
}
return false;
}
// Player2 will try to minimize score
for (int stones = 1; stones <= 3; stones++) {
if (n - stones >= 0) {
if (!minimax(n - stones, true, dp)) {
dp[key] = true;
return true;
}
}
}
return false;
}
public:
bool canWinNim(int n) {
unordered_map<string, bool> dp;
return minimax(n, true, dp);
}
};Above code is same for both player, therefore we can refactor it as below.
class Solution {
private:
bool minimax(int n, unordered_map<int, bool>& dp) {
// Base case: looser
if (n < 1) {
return false;
}
if (dp.count(n) > 0) {
return dp[n];
}
// Will try to maximize score
for (int stones = 1; stones <= 3; stones++) {
if (n - stones >= 0) {
if (!minimax(n - stones, dp)) {
dp[n] = true;
return true;
}
}
}
return false;
}
public:
bool canWinNim(int n) {
unordered_map<int, bool> dp;
return minimax(n, dp);
}
};Approach#1: minimax using iterative (TLE)
class Solution {
public:
bool canWinNim(int n) {
if (n == 0) {
return false;
}
if (n <= 3) {
return true;
}
vector<bool> dp(n + 1);
// base case
dp[0] = false;
dp[1] = true;
dp[2] = true;
dp[3] = true;
for (int stones = 4; stones <= n; stones++) {
// If any of the previous 3 states is a losing state, current state
// is a winning state
if (!dp[stones - 1] || !dp[stones - 2] || !dp[stones - 3]) {
dp[stones] = true;
} else {
dp[stones] = false;
}
}
return dp[n];
}
};Approach#3: Using math
class Solution {
public:
bool canWinNim(int n) {
return n % 4 != 0;
}
};464. Can I Win
https://leetcode.com/problems/can-i-win/description/
In the “100 game” two players take turns adding, to a running total, any integer from 1 to 10. The player who first causes the running total to reach or exceed 100 wins.
What if we change the game so that players cannot re-use integers?
For example, two players might take turns drawing from a common pool of numbers from 1 to 15 without replacement until they reach a total >= 100.
Given two integers maxChoosableInteger and desiredTotal, return true if the first player to move can force a win, otherwise, return false. Assume both players play optimally.
Example 1:
Input: maxChoosableInteger = 10, desiredTotal = 11
Output: false
Explanation:
No matter which integer the first player choose, the first player will lose.
The first player can choose an integer from 1 up to 10.
If the first player choose 1, the second player can only choose integers from 2 up to 10.
The second player will win by choosing 10 and get a total = 11, which is >= desiredTotal.
Same with other integers chosen by the first player, the second player will always win.Approach# Use minimax with memoization using bitmasking
Since operation for both player is same therefore we don’t need to deal first and second players move separately. Instead we can simply code similar to previous problem. Following is implementation for reference.
class Solution {
private:
bool minimax(int maxChoosableInteger, int desiredTotal, int bitmask,
unordered_map<int, bool>& dp) {
if (desiredTotal <= 0) {
return true;
}
if (dp.count(bitmask) > 0) {
return dp[bitmask];
}
// player will try to win
for (int i = 1; i <= maxChoosableInteger; i++) {
int mask = 1 << (i - 1); // Bitmask for the current number
// If the number is not used yet
if ((bitmask & mask) == 0) {
if (desiredTotal - i <= 0) {
dp[bitmask] = true;
return true;
}
// choose i number so that opponent loose the game
if (!minimax(maxChoosableInteger, desiredTotal - i,
bitmask | mask, dp)) {
dp[bitmask] = true;
return true;
}
}
}
dp[bitmask] = false;
return false;
}
public:
bool canIWin(int maxChoosableInteger, int desiredTotal) {
int sum = (maxChoosableInteger * (maxChoosableInteger + 1)) / 2;
if (sum < desiredTotal) {
return false;
}
unordered_map<int, bool> dp;
return minimax(maxChoosableInteger, desiredTotal, 0, dp);
}
};Note: bitmasking helps to generate easy dp key as well as no need to erase it while backtracking.
293. Flip Game
https://leetcode.com/problems/flip-game/description/
You are playing a Flip Game with your friend.
You are given a string currentState that contains only '+' and '-'. You and your friend take turns to flip two consecutive "++" into "--". The game ends when a person can no longer make a move, and therefore the other person will be the winner.
Return all possible states of the string currentState after one valid move. You may return the answer in any order. If there is no valid move, return an empty list [].
Example 1:
Input: currentState = "++++"
Output: ["--++","+--+","++--"]Approach# Apply fixed sliding window
class Solution {
public:
vector<string> generatePossibleNextMoves(string currentState) {
vector<string> ans;
int n = currentState.size();
// State after one move using two size fixed sliding window
for(int left=0; left <n-1; left++) {
// flip if both left and left+1 is +
if(currentState[left]=='+' && currentState[left+1]=='+') {
string state = currentState.substr(0,left)+"--"+currentState.substr(left+2);
ans.push_back(state);
}
}
return ans;
}
};294. Flip Game II
https://leetcode.com/problems/flip-game-ii/description/
You are playing a Flip Game with your friend.
You are given a string currentState that contains only '+' and '-'. You and your friend take turns to flip two consecutive "++" into "--". The game ends when a person can no longer make a move, and therefore the other person will be the winner.
Return true if the starting player can guarantee a win, and false otherwise.
Example 1:
Input: currentState = "++++"
Output: true
Explanation: The starting player can guarantee a win by flipping the middle "++" to become "+--+".Approach# Apply minimax algo
class Solution {
private:
bool minimax(string currentState, unordered_map<string,bool> & dp) {
if(dp.count(currentState) > 0) {
return dp[currentState];
}
int n = currentState.size();
for(int left=0; left < n-1; left++) {
if(currentState[left]=='+' && currentState[left+1]=='+') {
// make sure opponent loose the game
string state = currentState.substr(0,left) +"--"+currentState.substr(left+2);
if(!minimax(state, dp)) {
dp[currentState] = true;
return true;
}
}
}
// if either move is not possible or opponent won the game
dp[currentState] = false;
return false;
}
public:
bool canWin(string currentState) {
unordered_map<string,bool> dp;
return minimax(currentState, dp);
}
};374. Guess Number Higher or Lower
https://leetcode.com/problems/guess-number-higher-or-lower/description/
We are playing the Guess Game. The game is as follows:
I pick a number from 1 to n. You have to guess which number I picked.
Every time you guess wrong, I will tell you whether the number I picked is higher or lower than your guess.
You call a pre-defined API int guess(int num), which returns three possible results:
-1: Your guess is higher than the number I picked (i.e.num > pick).1: Your guess is lower than the number I picked (i.e.num < pick).0: your guess is equal to the number I picked (i.e.num == pick).
Return the number that I picked.
Example 1:
Input: n = 10, pick = 6
Output: 6Approach# Apply binary search
/**
* Forward declaration of guess API.
* @param num your guess
* @return -1 if num is higher than the picked number
* 1 if num is lower than the picked number
* otherwise return 0
* int guess(int num);
*/
class Solution {
public:
int guessNumber(int n) {
int left = 1, right = n;
while (left <= right) {
int mid = left + (right - left) / 2;
int score = guess(mid);
if (score == 0) { // match
return mid;
}
if (score == -1) { // higher than the number, need to move left
right = mid - 1;
} else {
// lower than the number, move to right
left = mid + 1;
}
}
return -1;
}
};375. Guess Number Higher or Lower II
https://leetcode.com/problems/guess-number-higher-or-lower-ii/
We are playing the Guessing Game. The game will work as follows:
- I pick a number between
1andn. - You guess a number.
- If you guess the right number, you win the game.
- If you guess the wrong number, then I will tell you whether the number I picked is higher or lower, and you will continue guessing.
- Every time you guess a wrong number
x, you will payxdollars. If you run out of money, you lose the game.
Given a particular n, return the minimum amount of money you need to guarantee a win regardless of what number I pick.
Example 1:
Input: n = 10
Output: 16
Explanation: The winning strategy is as follows:
- The range is [1,10]. Guess 7.
- If this is my number, your total is $0. Otherwise, you pay $7.
- If my number is higher, the range is [8,10]. Guess 9.
- If this is my number, your total is $7. Otherwise, you pay $9.
- If my number is higher, it must be 10. Guess 10. Your total is $7 + $9 = $16.
- If my number is lower, it must be 8. Guess 8. Your total is $7 + $9 = $16.
- If my number is lower, the range is [1,6]. Guess 3.
- If this is my number, your total is $7. Otherwise, you pay $3.
- If my number is higher, the range is [4,6]. Guess 5.
- If this is my number, your total is $7 + $3 = $10. Otherwise, you pay $5.
- If my number is higher, it must be 6. Guess 6. Your total is $7 + $3 + $5 = $15.
- If my number is lower, it must be 4. Guess 4. Your total is $7 + $3 + $5 = $15.
- If my number is lower, the range is [1,2]. Guess 1.
- If this is my number, your total is $7 + $3 = $10. Otherwise, you pay $1.
- If my number is higher, it must be 2. Guess 2. Your total is $7 + $3 + $1 = $11.
The worst case in all these scenarios is that you pay $16. Hence, you only need $16 to guarantee a win.Approach# Apply minimax algorithm
class Solution {
private:
int minimax(int start, int end, vector<vector<int>>& dp) {
if (start >= end) {
return 0;
}
if(dp[start][end] != -1) {
return dp[start][end];
}
// Player will try to minimize the panelty on wrong guess
int penalty = INT_MAX;
for (int x = start; x <= end; x++) {
// let's assume x is the actual number need to guess.
// player has three option, in both high and low it has to pay
// penalty
int low = minimax(start, x - 1, dp);
int high = minimax(x + 1, end, dp);
int total = x + max(low, high); // max fund needed
penalty = min(penalty, total); // minimize the penalty
}
dp[start][end] = penalty;
return penalty;
}
public:
int getMoneyAmount(int n) {
vector<vector<int>> dp(n+1, vector<int>(n+1,-1));
return minimax(1, n, dp);
}
};3222. Find the Winning Player in Coin Game
https://leetcode.com/problems/find-the-winning-player-in-coin-game/description/
You are given two positive integers x and y, denoting the number of coins with values 75 and 10 respectively.
Alice and Bob are playing a game. Each turn, starting with Alice, the player must pick up coins with a total value 115. If the player is unable to do so, they lose the game.
Return the name of the player who wins the game if both players play optimally.
Example 1:
Input: x = 2, y = 7
Output: “Alice”
Explanation:
The game ends in a single turn:
- Alice picks 1 coin with a value of 75 and 4 coins with a value of 10.
Approach# use minimax
class Solution {
private:
bool minimax(int x, int y, vector<vector<int>>& dp) {
if(dp[x][y] != -1) {
return dp[x][y];
}
// Apply all the options for player
for(int i=0; i <=x; i++) {
for (int j=0; j <=y; j++) {
// choose i 75 coin and j 10 coins with valid move
if(75*i + 10*j == 115) {
// if opponent loose then current player will win
if(!minimax(x-i, y-j, dp)) {
dp[x][y] = true;
return true;
}
}
}
}
dp[x][y]= false;
return false;
}
public:
string winningPlayer(int x, int y) {
vector<vector<int>> dp(x+1, vector<int>(y+1,-1));
if(minimax(x,y, dp)) {
return "Alice";
}
return "Bob";
}
};CoinGame
Consider a 2 player game , each player takes alternate turn. There is a coin at start position and has to be moved to end position. The player who move to end will win. Find out who will win A or B or draw. Both players plays most optimally so if any of game state is repeated verdict is draw.
The only movement allowed to move coin is to choose subarray of length K and rotate it.
Condition:
- subarray being rotated must contain coin.
- subarray must be of length K i.e. cant choose partial subarray
Implement following code.
class Solution{
String findWinner(char[] arr, int start, int end,int K)
}
char arr[N] : char array containing a coin 'C'
start , end : start and end position
K : rotation length
@return : "A" or "B" or "draw"Example#1
arr= [x,C,x,x,x,x,x]
st = 1 ,end = 5, K = 3Possiblity 1 :
A — possible subarray for rotation = [0–2] or [1–3] ([0–1] not a valid subarray)
[0–2] wont result in any move (but its a valid move).Lets say A chose [1–3]
[x,C,x,x,x,x,x] → [x,x,x,C,x,x,x]
B — chose [3,5]
[x,x,x,C,x,x,x] → [x,x,x,x,x,C,x]
Verdict : B won as Coin is placed at the given end positin#5
Possiblity 2 :
A : chose [0–2]
[x,C,x,x,x,x,x] → [x,C,x,x,x,x,x]
B: knows if he chooses [1–3] A will win in next step so he also chooses [0–2], as same game state is repeated so its a draw
Verdict : draw
Approach# Use minimax
/******************************************************************************
Online C++ Compiler.
Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.
*******************************************************************************/
#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
void swap(vector<char>& state, int i, int j) {
char tmp = state[j];
state[j] = state[i];
state[i] = tmp;
}
string serialzieState(vector<char>& state) {
// This can overflow for larger input. We can optimize it further using long or convert to string based key
stringstream ss;
for(char chr : state) {
ss<<chr;
}
return ss.str();
}
int minimax(vector<char>& state, int coinCurrent, int coinTarget, int k, unordered_set<string>& visited) {
if(coinCurrent == coinTarget) {
return 1;
}
string key = serialzieState(state);
if(visited.count(key) > 0){
return 0; // in case of state repetation, it would be a draw
}
visited.insert(key); // track current state
// Plyaer A will try al possible option and make sure opponent loose or draw
// Apply k size fixed sliding window to find all options
int left = 0;
int n = state.size();
for(int right=coinCurrent; right < min(coinCurrent+k, n); right++) {
// target position after rotating window of len k
int target = right - coinCurrent;
swap(state, coinCurrent, target);
// If oponent loose or draw then return early
int oponent = minimax(state, target, coinTarget, k, visited);
if(oponent ==0 ) {
return 0;
}
if(oponent == -1){
return 1;
}
swap(state, coinCurrent, target); // undo for backtracking
}
// At this place, current player will loose
return -1;
}
public:
string findWinner(vector<char> arr, int start, int end, int k) {
unordered_set<string> visited;
// 0: draw, 1: player A win, -1: B win. Start with A
int winner = minimax(arr, start, end, k, visited);
if(winner == 0) {
return "draw";
}
return winner == 1? "A" : "B";
}
};
int main()
{
vector<char> state = {'x','c','x','x','x','x','x'};
int start = 1, end = 5, k=3;
Solution* soln = new Solution();
string ans = soln->findWinner(state, start, end, k);
cout<<"ans " << ans <<endl;
return 0;
}Happy coding :-)
