高能玩家博弈游戏--《最后一个》《31点》必胜策略

《高能玩家》里面的某些玩家智商。。。

不过10s确实比较难反应过来

尝试着用自己学过的知识来解决这个问题。

规则

有6个领域,每个领域有若干个棋子。

每个玩家每轮每次选择一个颜色,并且至少移除一个棋子。

最后一个移完棋盘上的棋子的玩家失败。

31点的必胜策略

update: 2019年4月2日22:21:33

先手拥有必胜的策略。

用平时的分析的方法会有局限性。

我们一开始出3的话,最后会消耗完的。

我们得转换思路,思路就是消耗完对手的1,然后我们凑30点。

我们先出2,对手一般的思路会出1.

这个时候我们就出6,局势如下:

2 1

6 1

6 1

6 1

6 ?

进行到这一步的时候,对手就下不下去了。我们就胜利了。

若对手一开始出的不是1,那我们按照常规的思路就能赢了。

代码

一个还算比较简单的零和博弈,因为没有表不知道自己写的对不对。。。

准备和其他的人玩一玩来验证自己的程序是不是对的23333

代码写的比较的丑就不改了。。。

本来以为自己写的是对的。。。

结果和朋友讨论的时候发现了很大的问题

于是乖乖手动打表

打表的时间复杂度为$O(n^nn^n) = O(6^66^6)$, 所以要减小范围才能打出来。

发现(1, 1, 0, 0, 0, 0)和(0, 0, 0, 0, 0, 1)是特殊情况

这也是这个博弈的一个很奇特的特点。

其他的必败点是亦或和为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
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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
//#include <bits/stdc++.h>
//using namespace std;
//
//const int maxn = 7;
//int val[maxn][maxn][maxn][maxn][maxn][maxn];
//int num[maxn];
//
//int get_mex(int a, int b, int c, int d, int e, int f, int pos){
// //0表示的是必败
// //1表示的是必胜
// //pos = 0表示我自己
// //pos = 1表示对手
// num[1] = a, num[2] = b, num[3] = c, num[4] = d, num[5] = e, num[6] = f;
// sort(num+1, num+7);
// if(a+b+c+d+e+f == 1) {
// if(pos == 0){
// val[a][b][c][d][e][f] = 0;
// val[num[1]][num[2]][num[3]][num[4]][num[5]][num[6]] = val[a][b][c][d][e][f];
// return 0;
// }
// else{
// return 1;
// }
// }
// if(val[num[1]][num[2]][num[3]][num[4]][num[5]][num[6]] != -1&&pos == 0) {
// return val[a][b][c][d][e][f];
// }
//
// if(val[num[1]][num[2]][num[3]][num[4]][num[5]][num[6]]!=-1){
// val[num[1]][num[2]][num[3]][num[4]][num[5]][num[6]] = val[a][b][c][d][e][f];
// if(pos == 0)return val[a][b][c][d][e][f];
// else return (val[a][b][c][d][e][f]^1);
// }
//
// queue<int> sta;
// while(!sta.empty()) sta.pop();
// for(int a1=1;a1<=a; a1++) sta.push(get_mex(a-a1, b, c, d, e, f, pos^1));
// for(int b1=1;b1<=b; b1++) sta.push(get_mex(a, b-b1, c, d, e, f, pos^1));
// for(int c1=1;c1<=c; c1++) sta.push(get_mex(a, b, c-c1, d, e, f, pos^1));
// for(int d1=1;d1<=d; d1++) sta.push(get_mex(a, b, c, d-d1, e, f, pos^1));
// for(int e1=1;e1<=e; e1++) sta.push(get_mex(a, b, c, d, e-e1, f, pos^1));
// for(int f1=1;f1<=f; f1++) sta.push(get_mex(a, b, c, d, e, f-f1, pos^1));
// bool flag = false;
// while(!sta.empty()){
// int temp = sta.front();
// sta.pop();
// if(temp == 1){
// flag = true;
// break;
// }
// }
// if(flag == false){
// if(pos == 0){
// val[num[1]][num[2]][num[3]][num[4]][num[5]][num[6]] =
// val[a][b][c][d][e][f] = 0;
// return 0;
// }
// else {
// return 1;
// }
// }
// else{
// if(pos == 0){
// val[num[1]][num[2]][num[3]][num[4]][num[5]][num[6]] =
// val[a][b][c][d][e][f] = 1;
// return 1;
// }
// else{
// return 0;
// }
// }
//}
//
//int main(){
//
// ios::sync_with_stdio(false);
// int n = 3;
// memset(val, -1, sizeof(val));
// val[0][0][0][0][0][0] = 1;
// get_mex(0, 0, 0, n, n, n, 0);
// //cout<<val[0][0][0][6][6][0]<<endl;
// int lose = 0;
// int win = 0;
// for(int a=0; a<=6; a++){
// for(int b=0; b<=6; b++){
// for(int c=0; c<=6; c++){
// for(int d=0; d<=6; d++){
// for(int e=0; e<=6; e++){
// for(int f=0; f<=6; f++){
// if(val[a][b][c][d][e][f] == 0){
// cout<<a<<" "<<b<<" "<<c<<" "<<d<<" "<<e<<" "<<f<<endl;
// win++;
// }
// else lose++;
// }
// }
// }
// }
// }
// }
// //cout<<val[0][0][0][0][2][2]<<endl;
// while(~scanf("%d%d%d%d%d%d", &num[1], &num[2], &num[3], &num[4], &num[5], &num[6])){
// if(val[num[1]][num[2]][num[3]][num[4]][num[5]][num[6]] == 0){
// cout<<"you lose"<<endl;
// }
// bool flag = false;
// for(int i=1; i<=num[1]; i++){
// if(val[num[1]-i][num[2]][num[3]][num[4]][num[5]][num[6]]){
// cout<<num[1]-i<<" "<<num[2]<<" "<<num[3]<<" "<<num[4]<<" "<<num[5]<<" "<<num[6]<<endl;
// flag = true;
// break;
// }
// }
// if(flag) continue;
// for(int i=1; i<=num[2]; i++){
// if(val[num[1]][num[2]-i][num[3]][num[4]][num[5]][num[6]]){
// cout<<num[1]<<" "<<num[2]-i<<" "<<num[3]<<" "<<num[4]<<" "<<num[5]<<" "<<num[6]<<endl;
// flag = true;
// break;
// }
// }
// if(flag) continue;
// for(int i=1; i<=num[3]; i++){
// if(val[num[1]][num[2]][num[3]-i][num[4]][num[5]][num[6]]){
// cout<<num[1]<<" "<<num[2]<<" "<<num[3]-i<<" "<<num[4]<<" "<<num[5]<<" "<<num[6]<<endl;
// flag = true;
// break;
// }
// }
// if(flag) continue;
// for(int i=1; i<=num[4]; i++){
// if(val[num[1]][num[2]][num[3]][num[4]-i][num[5]][num[6]]){
// cout<<num[1]<<" "<<num[2]<<" "<<num[3]<<" "<<num[4]-i<<" "<<num[5]<<" "<<num[6]<<endl;
// flag = true;
// break;
// }
// }
// if(flag) continue;
// for(int i=1; i<=num[5]; i++){
// if(val[num[1]][num[2]][num[3]][num[4]][num[5]-i][num[6]]){
// cout<<num[1]<<" "<<num[2]<<" "<<num[3]<<" "<<num[4]<<" "<<num[5]-i<<" "<<num[6]<<endl;
// flag = true;
// break;
// }
// }
// if(flag) continue;
// for(int i=1; i<=num[6]; i++){
// if(val[num[1]][num[2]][num[3]][num[4]][num[5]][num[6]-i]){
// cout<<num[1]<<" "<<num[2]<<" "<<num[3]<<" "<<num[4]<<" "<<num[5]<<" "<<num[6]-i<<endl;
// flag = true;
// break;
// }
// }
// if(flag) continue;
// }
// return 0;
//}
#include <bits/stdc++.h>
using namespace std;
int num[10];
int main(){
int a, b, c, d, e, f;
int round = 0;
printf("please input 6 numbers ranging from 4-6 and begin the game:\n");
while(~scanf("%d%d%d%d%d%d", &a, &b, &c, &d, &e, &f)){
if((a^b^c^d^e^f) == 0) printf("GG\n");
int zero = 0;
int one = 0;
int above = 0;
bool flag = false;
num[1] = a, num[2] = b, num[3] = c, num[4] = d, num[5] = e, num[6] =f;
for(int i=1; i<=6; i++){
if(num[i] == 0) zero++;
if(num[i] == 1) one++;
else above++;
}
if(zero== 4){
if(one == 1){
for(int i=1; i<=6; i++){
if(num[i]>1){
printf("%d ", 0);
}
else printf("%d ", num[i]);
}
printf("\n");
flag = true;
}
if(flag == true){
printf("game over!You lose!\n");
break;
}
}
else if(zero== 5){
{
for(int i=1; i<=6; i++){
if(num[i]>1){
printf("%d ", 1);
}
else printf("%d ", 0);
}
printf("\n");
flag = true;
}
if(flag == true){
printf("game over!You lose!\n");
break;
}
}
for(int a1=1; a1<=a; a1++){
if((((a-a1)^b^c^d^e^f) == 0)){
printf("%d %d %d %d %d %d\n", a-a1, b, c, d, e, f);
flag = true;
printf("--------------------\n");
printf("Now it's your turn\n");
break;
}
}
if(flag == true) continue;
for(int b1=1; b1<=b; b1++){
if((((a)^(b-b1)^c^d^e^f) == 0)){
printf("%d %d %d %d %d %d\n", a, b-b1, c, d, e, f);
flag = true;
printf("--------------------\n");
printf("Now it's your turn\n");
break;
}
}
if(flag == true) continue;
for(int c1=1; c1<=c; c1++){
if((((a)^b^(c-c1)^d^e^f) == 0)){
printf("%d %d %d %d %d %d\n", a, b, c-c1, d, e, f);
flag = true;
printf("--------------------\n");
printf("Now it's your turn\n");
break;
}
}
if(flag == true) continue;
for(int d1=1; d1<=d; d1++){
if((((a)^b^c^(d-d1)^e^f) == 0)){
printf("%d %d %d %d %d %d\n", a, b, c, d-d1, e, f);
flag = true;
printf("--------------------\n");
printf("Now it's your turn\n");
break;
}
}
if(flag == true) continue;
for(int e1=1; e1<=e; e1++){
if((((a)^b^c^d^(e-e1)^f) == 0)){
printf("%d %d %d %d %d %d\n", a, b, c, d, e-e1, f);
flag = true;
printf("--------------------\n");
printf("Now it's your turn\n");
break;
}
}
if(flag == true) continue;
for(int f1=1; f1<=f; f1++){
if(((a)^b^c^d^e^(f-f1)) == 0){
printf("%d %d %d %d %d %d\n", a, b, c, d, e, f-f1);
flag = true;
printf("--------------------\n");
printf("Now it's your turn\n");
break;
}
}
if(flag == true) continue;
}
}

修改的第二版

修改了边界

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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <bits/stdc++.h>
using namespace std;
int num[10];
int main(){
int a, b, c, d, e, f;
int round = 0;
printf("please input 6 numbers ranging from 4-6 and begin the game:\n");
while(~scanf("%d%d%d%d%d%d", &a, &b, &c, &d, &e, &f)){
int zero = 0;
int one = 0;
int above = 0;
bool flag = false;
num[1] = a, num[2] = b, num[3] = c, num[4] = d, num[5] = e, num[6] =f;
for(int i=1; i<=6; i++){
if(num[i] == 0) zero++;
if(num[i] == 1) one++;
else above++;
}
if(zero== 4){
if(one == 1){
for(int i=1; i<=6; i++){
if(num[i]>1){
printf("%d ", 0);
}
else printf("%d ", num[i]);
}
printf("\n");
flag = true;
}
if(one == 2){
printf("Congratulations!YOU WIN!!\n");
break;
}
if(flag == true){
printf("game over!You lose!\n");
break;
}
}
else if(zero== 5){
{
for(int i=1; i<=6; i++){
if(num[i]>1){
printf("%d ", 1);
}
else printf("%d ", 0);
}
printf("\n");
flag = true;
}
if(one == 1){
printf("Congratulations!YOU WIN!!\n");
break;
}
if(flag == true){
printf("game over!You lose!\n");
break;
}
}
if((a^b^c^d^e^f) == 0) printf("GG\n");
for(int a1=1; a1<=a; a1++){
if((((a-a1)^b^c^d^e^f) == 0)){
printf("%d %d %d %d %d %d\n", a-a1, b, c, d, e, f);
flag = true;
printf("--------------------\n");
printf("Now it's your turn\n");
break;
}
}
if(flag == true) continue;
for(int b1=1; b1<=b; b1++){
if((((a)^(b-b1)^c^d^e^f) == 0)){
printf("%d %d %d %d %d %d\n", a, b-b1, c, d, e, f);
flag = true;
printf("--------------------\n");
printf("Now it's your turn\n");
break;
}
}
if(flag == true) continue;
for(int c1=1; c1<=c; c1++){
if((((a)^b^(c-c1)^d^e^f) == 0)){
printf("%d %d %d %d %d %d\n", a, b, c-c1, d, e, f);
flag = true;
printf("--------------------\n");
printf("Now it's your turn\n");
break;
}
}
if(flag == true) continue;
for(int d1=1; d1<=d; d1++){
if((((a)^b^c^(d-d1)^e^f) == 0)){
printf("%d %d %d %d %d %d\n", a, b, c, d-d1, e, f);
flag = true;
printf("--------------------\n");
printf("Now it's your turn\n");
break;
}
}
if(flag == true) continue;
for(int e1=1; e1<=e; e1++){
if((((a)^b^c^d^(e-e1)^f) == 0)){
printf("%d %d %d %d %d %d\n", a, b, c, d, e-e1, f);
flag = true;
printf("--------------------\n");
printf("Now it's your turn\n");
break;
}
}
if(flag == true) continue;
for(int f1=1; f1<=f; f1++){
if(((a)^b^c^d^e^(f-f1)) == 0){
printf("%d %d %d %d %d %d\n", a, b, c, d, e, f-f1);
flag = true;
printf("--------------------\n");
printf("Now it's your turn\n");
break;
}
}
if(flag == true) continue;
}
}

未解决的问题

文章目录
  1. 1. 规则
  • 31点的必胜策略
    1. 1. 代码
  • 修改的第二版
  • 未解决的问题
  • {{ live2d() }}