forked from luckymark/wuziqi2020
-
Notifications
You must be signed in to change notification settings - Fork 0
/
min_max.h
152 lines (146 loc) · 4.87 KB
/
min_max.h
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
//#pragma comment(lib,"User32.lib")
#ifndef MIN_MAX_H
#define MIN_MAX_H
#include "score_count.h"
#include <vector>
//#pragma comment(lib,"ws2_32.lib")
extern int chess_board[25][25];
int max_search(int depths, int alpa);
int min_search(int depths, int beta);
void AImax_search(int& xxx, int& yyy, int depths);
int evaluate_minmax();
int evaluate_minmax() { //这是评估函数
const int SIZES = 15;
int scoreAI = 0;
int scoreplayer = 0;
for (int i = 0; i < SIZES; i++) { //横排
std::vector <int> v;
for (int j = 0; j < SIZES; j++)
v.push_back(chess_board[i][j]);
scoreplayer += count_score(v, 1);
scoreAI += count_score(v, 2);
v.clear();
}
for (int j = 0; j < SIZES; j++) { //竖排
std::vector <int> v;
for (int i = 0; i < SIZES; i++)
v.push_back(chess_board[i][j]);
scoreplayer += count_score(v, 1);
scoreAI += count_score(v, 2);
v.clear();
}
for (int i = 0; i < SIZES; i++) { //上半正斜线
int ddx, ddy;
std::vector <int> v;
for (ddx = i, ddy = 0; ddx < SIZES && ddy < SIZES; ++ddx, ++ddy)
v.push_back(chess_board[ddy][ddx]);
scoreplayer += count_score(v, 1);
scoreAI += count_score(v, 2);
v.clear();
}
for (int j = 1; j < SIZES; j++) { //下半正斜线
int ddx, ddy;
std::vector <int> v;
for (ddx = 0, ddy = j; ddy < SIZES && ddx < SIZES; ddx++, ddy++)
v.push_back(chess_board[ddy][ddx]);
scoreplayer += count_score(v, 1);
scoreAI += count_score(v, 2);
v.clear();
}
for (int i = 0; i < SIZES; i++) { //上半反斜线
std::vector <int> v;
int ddx, ddy;
for (ddy = i, ddx = 0; ddy >= 0 && ddx < SIZES; ddy--, ddx++)
v.push_back(chess_board[ddy][ddx]);
scoreplayer += count_score(v, 1);
scoreAI += count_score(v, 2);
v.clear();
}
for (int j = 1; j < SIZES; j++) {
std::vector <int> v;
int ddx, ddy;
for (ddy = j, ddx = SIZES - 1; ddy < 16 && ddx >= 0; ddy++, ddx--)
v.push_back(chess_board[ddx][ddy]);
scoreplayer += count_score(v, 1);
scoreAI += count_score(v, 2);
v.clear();
}
return scoreAI - scoreplayer;
}
//, int beta 不加大概跑1min（54.96s)，加了大概40s左右(41.98s)
int min_search(int depths,int beta) {
if (depths <= 0) {
int res = evaluate_minmax();
return res;
}
std::vector < std::pair<std::pair<int, int>,int> > vv;
genarator_point(vv, 1);
int Length = vv.size();
int best = INT_MAX;
for (int i = 0; i < Length; i++) {
int t1 = vv[i].first.first;
int t2 = vv[i].first.second;
chess_board[t1][t2] = 1;
int temps = max_search(depths - 1, best < beta ? best : beta);
chess_board[t1][t2] = 0;
if (temps < best) best = temps;
if (temps < beta) break;
// int temps = max_search(depths - 1, best < alpha ? best : alpha);
// if (temps < best) best = temps;
// if (temps < beta) break; //剪枝
}
return best;
}
//, int alpha
int max_search(int depths,int alpa) {
if (depths <= 0) {
int res = evaluate_minmax();
return res;
}
std::vector < std::pair<std::pair<int, int>,int> > vv;
genarator_point(vv, 2);
int Length = vv.size();
int best = INT_MIN;
for (int i = 0; i < Length; i++) {
int t1 = vv[i].first.first;
int t2 = vv[i].first.second;
chess_board[t1][t2] = 1;
int temps = min_search(depths - 1, best > alpa ? best : alpa);
chess_board[t1][t2] = 0;
if (temps > best) best = temps;
if (temps > alpa) break;
// int temps = min_search(depths - 1, best > beta ? best : beta);
// if (temps > best) best = temps;
// if (temps > alpha) break;//剪枝
}
return best;
}
void AImax_search(int& xxx, int& yyy, int depths) {
std::vector <std::pair<std::pair <int, int>,int> > vv;
genarator_point(vv, 2);
int best = INT_MIN;
int Length = vv.size();
std::vector <std::pair<std::pair <int, int>,int> > vv2;
for (int i = 0; i < Length; i++) {
int t1 = vv[i].first.first;
int t2 = vv[i].first.second;
chess_board[t1][t2] = 2;
int temp = min_search(depths - 1, best);
if (temp > best) {
best = temp;
vv2.clear();
vv2.push_back(vv[i]);
}
else {
if (temp == best) {
vv2.push_back(vv[i]);
}
}
chess_board[t1][t2] = 0;
}
int Length2 = vv2.size();
int choose = (int)(rand() % Length2);
xxx = vv2[choose].first.first;
yyy = vv2[choose].first.second;
}
#endif