Problem Sets on Game Theory
Contents
This post contains a couple of well-defined problems on game theory.
Game theory 01
Coins in a Line (394):
Show solution
C++
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
public:
/**
* @param n: An integer
* @return: A boolean which equals to true if the first player will win
*/
bool isWinning(int playerId, int coinsLeft){
if(occurMapArr[playerId].find(coinsLeft) != occurMapArr[playerId].end()){
return occurMapArr[playerId][coinsLeft];
} else if(coinsLeft<=0){
return false;
} else if(coinsLeft<=2){
return true;
} else if(playerId==0){
occurMapArr[playerId][coinsLeft] = !isWinning(1, coinsLeft-1) || !isWinning(1, coinsLeft-2);
return occurMapArr[playerId][coinsLeft];
} else {
occurMapArr[playerId][coinsLeft] = !isWinning(0, coinsLeft-1) || !isWinning(0,coinsLeft-2);
return occurMapArr[playerId][coinsLeft];
}
}
bool firstWillWin(int n) {
// write your code here
return isWinning(0,n);
}
private:
vector< map<int, bool>> occurMapArr = vector<map<int, bool>>(2);
Coins in a Line II (395):
Show solution
Text
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
public:
/**
* @param values: a vector of integers
* @return: a boolean which equals to true if the first player will win
*/
bool isWinning(int playerId, vector<int> &values, int index, int value){
if (occurMapArray[playerId].find(index) != occurMapArray[playerId].end()){
return occurMapArray[playerId][index];
}else if(index >= values.size()) {
if(playerId==0 && value>=0){
return true;
} else if(playerId==1 && value<=0){
return true;
} else{
return false;
}
} else {
if(playerId==0){
if(index+1 < values.size()){
occurMapArray[playerId][index] = !isWinning(1, values, index+1, value+values[index]) ||
!isWinning(1, values, index+2, value+values[index]+values[index+1]);
} else {
occurMapArray[playerId][index] = !isWinning(1, values, index+1, value+values[index]);
}
return occurMapArray[playerId][index];
} else {
if(index+1 < values.size()){
occurMapArray[playerId][index] = !isWinning(0, values, index+1, value-values[index]) ||
!isWinning(0, values, index+2, value-values[index]-values[index+1]);
} else {
occurMapArray[playerId][index] = !isWinning(0, values, index+1, value-values[index]);
}
return occurMapArray[playerId][index];
}
}
}
bool firstWillWin(vector<int> &values) {
// write your code here
return isWinning(0, values, 0, 0);
}
private:
vector<map<int,bool>> occurMapArray = vector<map<int,bool>>(2);
Bash Game II (3735):
Show solution
C++
1
2
3
4
5
6
7
8
bool canWinBash(vector<int> &rocks) {
// --- write your code here ---
int nimSum = 0;
for(int &val : rocks){
nimSum ^= val;
}
return nimSum!=0;
}