Game
Math
1
2
3
4
5
6
7
8
9
10
11
12
public boolean xorGame(int[] nums) {
int xor = 0;
for (int num : nums) {
xor ^= num;
}
// when the number of elements are even
// not all elements are same, otherwise xor == 0
// if nums[i] and nums[j] are distinct
// Alice can erase either and not close at current turn
return xor == 0 || nums.length % 2 == 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public boolean sumGame(String num) {
// left - right
int diff = 0, qDiff = 0;
for (int i = 0; i < num.length(); i++) {
int c = i < num.length() / 2 ? 1 : -1;
if (num.charAt(i) == '?') {
qDiff += c;
} else {
diff += c * (num.charAt(i) - '0');
}
}
// if qDiff is odd, Alice can always win
// checks parity by qDiff & 1 to cover negative cases
// 1. '?' on the opposite sides cancel each out
// 2. For two '?' on the same side, Bob can always make ? + ? == 9, regardless of how Alice plays.
// so if we have n '?'s, Bob can only win if:
// smaller + n * 9 / 2 == larger
return (qDiff & 1) == 1 || diff + qDiff * 9 / 2 != 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public boolean stoneGameIX(int[] stones) {
int[] remainders = new int[3];
for (int s : stones) {
remainders[s % 3]++;
}
// Alice will always win if remainders[0] == 0 by picking the mod with less frequency
// if remainders[0] is even, Alice can always pick a 3 when Bob picks a 3
// so that's equivalent
if (remainders[0] % 2 == 0) {
return remainders[1] > 0 && remainders[2] > 0;
}
// because of the extra 3, Alice needs to pick mod with more frequency instead
// after popping the more frequency mod twice,
// Alice should keep the invariant that the less frequency mod is still the less frequency mod
return Math.abs(remainders[1] - remainders[2]) > 2;
}
Dynamic Programming
Bottom-up
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public boolean stoneGame(int[] piles) {
int n = piles.length;
// the largest number of stones one can get more than opponent
int[][] dp = new int[n][n];
for (int i = 0; i < n; i++) {
dp[i][i] = piles[i];
}
for (int d = 1; d < n; d++) {
for (int i = 0; i + d < n; i++) {
dp[i][i + d] = Math.max(piles[i] - dp[i + 1][i + d], piles[i + d] - dp[i][i + d - 1]);
}
}
return dp[0][n - 1] > 0;
}
1D:
1
2
3
4
5
6
7
8
9
10
public boolean stoneGame(int[] piles) {
int n = piles.length;
int[] dp = Arrays.copyOf(piles, n);
for (int d = 1; d < n; d++) {
for (int i = 0; i + d < n; i++) {
dp[i] = Math.max(piles[i] - dp[i + 1], piles[i + d] - dp[i]);
}
}
return dp[0] > 0;
}
Alex can always take either all odd piles or all even piles, and one of the colors must have a sum number of stones larger than the other color.
1
2
3
4
5
6
7
8
9
10
11
12
public boolean winnerSquareGame(int n) {
boolean[] dp = new boolean[n + 1];
for (int i = 1; i <= n; i++) {
for (int k = 1; k * k <= i; k++) {
if (!dp[i - k * k]) {
dp[i] = true;
break;
}
}
}
return dp[n];
}
Top-down
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
private int maxChoosableInteger;
private Map<Integer, Boolean> map = new HashMap<>();
public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
this.maxChoosableInteger = maxChoosableInteger;
if (desiredTotal == 0) {
return true;
}
if (maxChoosableInteger * (maxChoosableInteger + 1) / 2 < desiredTotal) {
return false;
}
return dfs(desiredTotal, 0);
}
private boolean dfs(int total, int state) {
if (map.containsKey(state)) {
return map.get(state);
}
boolean canWin = false;
for (int i = maxChoosableInteger; i > 0; i--) {
if ((state & (1 << (i - 1))) == 0) {
// "can't force a win" == "lose"
// because both players play optimally
if (i >= total || !dfs(total - i, state | (1 << (i - 1)))) {
canWin = true;
break;
}
}
}
map.put(state, canWin);
return canWin;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
private int[] p;
private int[][] memo;
public int stoneGameII(int[] piles) {
p = new int[piles.length + 1];
memo = new int[piles.length][piles.length + 1];
for (int i = 0; i < piles.length; i++) {
p[i + 1] = p[i] + piles[i];
}
return helper(piles, 0, 1);
}
private int helper(int[] piles, int start, int m) {
if (start == piles.length) {
return 0;
}
if (memo[start][m] > 0) {
return memo[start][m];
}
int max = 0;
for (int x = 1; x <= Math.min(2 * m, piles.length - start); x++) {
max = Math.max(max, p[p.length - 1] - p[start] - helper(piles, start + x, Math.max(m, x)));
}
return memo[start][m] = max;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
public static final int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
private int n, m, available, catJump, mouseJump;
private String[] grid;
// {cell position, cat r, cat c, mouse r, mouse c}
private Boolean[][][][][] memo;
public boolean canMouseWin(String[] grid, int catJump, int mouseJump) {
this.grid = grid;
this.n = grid.length;
this.m = grid[0].length();
this.catJump = catJump;
this.mouseJump = mouseJump;
// positions of Cat and Mouse
int[] cat = {-1, -1}, mouse = {-1, -1};
// count of cells that Cat or Mouse can move to, i.e. non-wall cells
available = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i].charAt(j) != '#') {
available++;
}
if (grid[i].charAt(j) == 'C') {
cat = new int[]{i, j};
} else if (grid[i].charAt(j) == 'M') {
mouse = new int[]{i, j};
}
}
}
memo = new Boolean[available * 2 + 1][n][m][n][m];
return dfs(0, cat, mouse);
}
private boolean dfs(int turn, int[] cat, int[] mouse) {
if (memo[turn][cat[0]][cat[1]][mouse[0]][mouse[1]] != null) {
return memo[turn][cat[0]][cat[1]][mouse[0]][mouse[1]];
}
// 2 * available is the max turns
// it's a rough estimate
if (turn == available * 2) {
return false;
}
// Mouse's turn
if (turn % 2 == 0) {
for (int[] d : DIRECTIONS) {
for (int i = 0; i <= mouseJump; i++) {
int r = mouse[0] + i * d[0], c = mouse[1] + i * d[1];
if (r < 0 || r == n || c < 0 || c == m || grid[r].charAt(c) == '#') {
break;
}
if (grid[r].charAt(c) == 'F' || dfs(turn + 1, cat, new int[]{r, c})) {
return memo[turn][cat[0]][cat[1]][mouse[0]][mouse[1]] = true;
}
}
}
return memo[turn][cat[0]][cat[1]][mouse[0]][mouse[1]] = false;
}
// Cat's turn
for (int[] d : DIRECTIONS) {
for (int i = 0; i <= catJump; i++) {
int r = cat[0] + i * d[0], c = cat[1] + i * d[1];
if (r < 0 || r == n || c < 0 || c == m || grid[r].charAt(c) == '#') {
break;
}
if ((r == mouse[0] && c == mouse[1]) || grid[r].charAt(c) == 'F' || !dfs(turn + 1, new int[]{r, c}, mouse)) {
return memo[turn][cat[0]][cat[1]][mouse[0]][mouse[1]] = false;
}
}
}
return memo[turn][cat[0]][cat[1]][mouse[0]][mouse[1]] = true;
}
Bottom-up Percolation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
private enum Color {
DRAW,
MOUSE,
CAT
}
// minimax
// P-complete
public int catMouseGame(int[][] graph) {
int n = graph.length;
// state: (cat location, mouse location, move)
// mouse move = 0, cat move = 1
// these states form a directed graph
Color[][][] color = new Color[n][n][2];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
Arrays.fill(color[i][j], Color.DRAW);
}
}
int[][][] outdegree = new int[n][n][2];
for (int i = 0; i < n; i++) { // cat
for (int j = 0; j < n; j++) { // mouse
outdegree[i][j][0] = graph[j].length;
outdegree[i][j][1] = graph[i].length;
for (int next : graph[i]) {
// excludes the hole from outdegree[i][j][1] (cat move)
if (next == 0) {
outdegree[i][j][1]--;
break;
}
}
}
}
// bottom-up percolation
// enqueues ending nodes with definite results
// {cat location, mouse location, move, color}
Queue<int[]> q = new LinkedList<>();
for (int i = 1; i < n; i++) {
for (int k = 0; k < 2; k++) {
// Mouse reaches the hole
color[i][0][k] = Color.MOUSE;
q.offer(new int[]{i, 0, k, Color.MOUSE.ordinal()});
// Cat occupies the same node as Mouse
color[i][i][k] = Color.CAT;
q.offer(new int[]{i, i, k, Color.CAT.ordinal()});
}
}
while (!q.isEmpty()) {
int[] node = q.poll();
int cat = node[0], mouse = node[1], move = node[2], c = node[3];
// starting node
if (cat == 2 && mouse == 1 && move == 0) {
return c;
}
int prevMove = 1 - move;
for (int prev : graph[prevMove == 0 ? mouse : cat]) {
// if previous move is mouse, then cat remains
// otherwise cat is prev
int prevCat = prevMove == 0 ? cat : prev;
// if previous move is mouse, then mouse is prev
// otherwise mouse remains
int prevMouse = prevMove == 0 ? prev : mouse;
// Cat can't be in the hole
if (prevCat == 0) {
continue;
}
// if previous state is not DRAW, then it's already visited
if (color[prevCat][prevMouse][prevMove] != Color.DRAW) {
continue;
}
// for each DRAW node, there are two types of coloring
// (suppose the move is mouse move)
// - immediate coloring: if there's a child that's colored MOUSE,
// then this node will also be colored MOUSE
// - eventual coloring: if all children are colored CAT,
// then this node will also be colored CAT
if ((prevMove == 0 && c == Color.MOUSE.ordinal()) || // immediate coloring
(prevMove == 1 && c == Color.CAT.ordinal()) || // immediate coloring
--outdegree[prevCat][prevMouse][prevMove] == 0) { // eventual coloring
color[prevCat][prevMouse][prevMove] = Color.values()[c];
q.offer(new int[]{prevCat, prevMouse, prevMove, c});
}
}
}
return color[2][1][0].ordinal();
}
Sprague–Grundy Theorem
Combinatorial game theory (CGT) has been largely confined to two-player games that have a position in which the players take turns changing in defined ways or moves to achieve a defined winning condition.
In combinatorial game theory, an impartial game is a game in which the allowable moves depend only on the position and not on which of the two players is currently moving, and where the payoffs are symmetric. In other words, the only difference between player 1 and player 2 is that player 1 goes first.
In combinatorial game theory, the normal play convention of an impartial game is that the last player able to move is the winner.
Nim is a mathematical game of strategy in which two players take turns removing (or “nimming”) objects from distinct heaps or piles. On each turn, a player must remove at least one object, and may remove any number of objects provided they all come from the same heap or pile. The game is to take the last object.
Nim-sum is the bitwise xor of the heap sizes.
Theorem: In a normal Nim game, the player making the first move has a winning strategy if and only if the nim-sum of the sizes of the heaps is not zero. Otherwise, the second player has a winning strategy.
Strategy: the winning strategy is to finish every move with a nim-sum of 0. This is always possible if the nim-sum is not zero before the move. To find out which move to make, let X be the nim-sum of all the heap sizes. Find a heap where X \xor heap-size < heap-size; the winning strategy is to play in such a heap, reducing that heap to X \xor heap-size.
In mathematics, the nimbers, also called Grundy numbers, are the values of heaps in the game Nim.
The Grundy Number/ nimber is equal to 0 for a game that is lost immediately by the first player and is equal to Mex of the nimbers of all possible next positions for any other game.
In mathematics, the mex of a subset of a well-ordered set is the smallest value from the whole set that does not belong to the subset. That is, it is the minimum value of the complement set. The name “mex” is shorthand for “minimum excluded” value.
In combinatorial game theory, the Sprague–Grundy theorem states that every impartial game under the normal play convention is equivalent to a one-heap game of nim, or to an infinite generalization of nim.
Then Sprague-Grundy Theorem says that if both A and B play optimally, then the player starting first is guaranteed to win if the XOR of the grundy numbers of position in each sub-games at the beginning of the game is non-zero. Otherwise, if the XOR evaluates to zero, then player A will lose definitely, no matter what.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// O(n ^ 2)
public boolean canWin(String s) {
int sg = 0;
List<Integer> nimbers = new ArrayList<>();
// DP to get nimbers
for (String t : s.split("-+")) {
int n = t.length();
// t is consecutive '+'s
if (n != 0) {
while (nimbers.size() <= n) {
char[] chars = t.toCharArray();
int i = 0, j = nimbers.size() - 2;
// g(t) = mex(g(0, n - 2), g(1, n - 3), ...)
// = mex(g(0) ^ g(n - 2), g(1) ^ g(n - 3), ...)
//
// chars marks the presence of nimbers of all sub-game states
// chars[i] == '-': sub-game nimber i exists
while (i <= j) {
chars[nimbers.get(i++) ^ nimbers.get(j--)] = '-';
}
// mex
nimbers.add(new String(chars).indexOf('+'));
}
sg ^= nimbers.get(n);
}
}
return sg != 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// O(n)
public boolean canWin(String s) {
// https://oeis.org/A002187
// Has period 34 with the only exceptions at n=0, 14, 16, 17, 31, 34 and 51.
// our definition is shifted by 1, so the last exception is nimbers[52]
int p = 34, n = 51 + 1 + p;
int[] nimbers = new int[n + 1];
for (int k = 2; k <= n; k++) {
char[] chars = "+".repeat(k).toCharArray();
int i = 0, j = k - 2;
while (i <= j) {
chars[nimbers[i++] ^ nimbers[j--]] = '-';
}
nimbers[k] = new String(chars).indexOf('+');
}
int sg = 0;
for (String t : s.split("-+")) {
// t is consecutive '+'s
int len = t.length();
while (len > n) {
len -= p;
}
sg ^= nimbers[len];
}
return sg != 0;
}
Subtree Removal Game with Fibonacci Tree
Colon principle: when branches come together at a vertex, one may replace the branches by a non-branching stalk of length equal to their nim sum.
1
2
3
4
5
6
7
8
public boolean findGameWinner(int n) {
// The Grundy value of a node is the nim sum of the Grundy values of its children.
// SG(1) = 0
// SG(2) = 1
// SG(n) = (SG(n - 1) + 1) xor (SG(n - 2) + 1)
// SG: [null, 0, 1, 3, 6, 3, 3, 0, 5, 7, 14, 7, 7, 0, 9, 11, 6, 11, 11, 0, 13, ...]
return n % 6 != 1;
}