如何编写一个五子棋AI（附AI源码）

注:此文章的代码推荐在$\boxed{小熊猫c++}$上运行（使用了EGE图形库）

AI的原理

1.三子棋AI的编写

三子棋的总局面数约为$549,946$，因此我们先以它为基础开始编写。

Test1:构建决策树

注意:节点上方的$[a/b]$表示某个决策下一步还有$b$种可能，还剩下$a$种未显示

这里，我们先来讨论某个局面下一步的决策。

源码见文末 $Test1$ 源码
关注左上红下$(1,3)$的节点，可以发现下一步蓝色可以获胜，那么红方必然不能下$(1,3)$。
同理，红下$(3,2)\&(1,2)$同样不行，只能下$(3,1)$。

继续看蓝方，可以发现蓝方也只能下$(1,3)$

于是，我们就得到了三子棋的AI的博弈树，现在来分析具体方法。

Test2:Min-Max算法

我们将平局定为$5$分，红胜为$10$，红负为$0$分，这样，我们就可以得到每个局面对红方的好处。
设前一步的节点为$u$,下一步的节点为$v$
对于每一个蓝点（到蓝色下棋），下一步是红方控制的，当然会选择对自己优的，所以取 V u = max ⁡ { V v } V_u=\max\{V_v\} Vu​=max{Vv​}，比如下图中粉框节点，下一步红方可以取胜，那当然要选取胜了

对于每一个红点（到红色下棋），下一步是对方控制的，当然会选择对红方劣的，所以取 V u = min ⁡ { V v } V_u=\min\{V_v\} Vu​=min{Vv​}，比如如果有一个节点，下一步蓝方可以取胜，那当然要选取胜（红败）了
这样，我们就得到了所有局面的胜率。
源码见文末 $Test2-1$ 源码，AI下3子棋见 $Test2-2$ 源码

当然，经过对所有局面的考察，可以发现没有必胜的可能，但是还是有可能在前几步利用对手失误获得必胜（读者可以自行查看程序），如上图。

1.五子棋AI的编写

五子棋的总局面数约为$10^{50}$，因此不可能构造完整的决策树。

Test3:对局面进行估分

还是以三子棋为例，把$[X][X][]$记为$50$分，$[][X][]$和$[][][X]$记为$10$分，$[X][X][X]$记为$100$分，就可以在决策树层数较少的情况估算价值。

有了估值，AI就智慧多了，如果我们把比较有可能的点（这里是选前2个）单独挑出来，其余的点不进行展开，可以发现它已经把较优的点选好了（如上图），就会大大减少节点数。
以下是一次对局：（AI:蓝）

评价：目光较短浅，但是速度非常快(约0.3s)
源码见$Test3$

Test4:α-β剪枝

AI不行，就加深度，时间太长，就加剪枝

发现 V u = m a x { m i n { a , b } , c } V_u=max\{min\{a,b\},c\} Vu​=max{min{a,b},c}时，如果$a\&b$有一个$<c$，那就不用算了，$V_u$就是$c$，
同理 V u = m i n { m a x { a , b } , c } V_u=min\{max\{a,b\},c\} Vu​=min{max{a,b},c}，如果$a\&b$有一个$>c$，$V_u$就是$c$



即：$min(7,max(10,?))=7$

(实测大约剪掉了$3/4$的节点，效率不太高，所以笔者并没有用)

本文中所有源代码

$Test1$

#include<iostream>
#include<vector>
#include<graphics.h>
using namespace std;
struct BOARD{int a[3][3];int number,win;};
struct SHOW{int x,y;int SON;}node[4020889];
int NODE=1;bool show[4028089];
BOARD tree[4028809];
vector<int>son[4002889];
int mx,my,Dl,LINE[400288][5],LN,Dr,LOCK,Rc=1;
int check(BOARD now)
{
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
			if(now.a[i][j])
			for(int fx=-1;fx<=1;fx++)
				for(int fy=-1;fy<=1;fy++)
					if(fx!=0||fy!=0)
				{
					int bo=now.a[i][j];
					for(int f=1;f<=2;f++)
						if(i+fx*f>=3||j+fy*f>=3||i+fx*f<0||j+fy*f<0||now.a[i][j]!=now.a[i+fx*f][j+fy*f])bo=0;
					if(bo)return bo;
				}
	return 0;
}
int getstep(BOARD now)
{
	int step=0;
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)step+=now.a[i][j];
	if(step==0)step=1;else step=-1;
	return step;
}
void dfs(BOARD now)
{
	tree[now.number]=now;
	if(now.win)
	{
		return;
	}
	int step=getstep(now);
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
		if(!now.a[i][j])
		{
			NODE++;BOARD next=now;next.number=NODE;
			son[now.number].push_back(NODE);
			next.a[i][j]=step;
			next.win=check(next);
			dfs(next);
		}
}
BOARD empty_board()
{
	BOARD empty;
	for(int i=0;i<3;i++)for(int j=0;j<3;j++)empty.a[i][j]=0;empty.number=1;empty.win=0;
	return empty;
}
void print_board(int x,int y,BOARD z)
{
	setcolor(getstep(z)==1?RED:BLUE);
	setfillcolor(WHITE);
	fillrect(x,y,x+100,y+100);
	x+=10;y+=10;
	setcolor(BLACK);
	int t=80/3;
	for(int i=x;i<=x+80;i+=t)line(i,y,i,y+80);
	for(int j=y;j<=y+80;j+=t)line(x,j,x+80,j);
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
			if(z.a[i][j]==1)
			{
				setcolor(BLUE);setlinewidth(2);
				circle(x+i*t+t/2,y+j*t+t/2,t/2-1);setlinewidth(1);
			}
			else if(z.a[i][j]==-1)
			{
				setcolor(RED);
				setlinewidth(3);
				line(x+t*i+2,y+t*j+2,x+t*i+t-2,y+t*j+t-2);
				line(x+t*i+2,y+t*j+t-2,x+t*i+t-2,y+t*j+2);
				setlinewidth(1);
			}
}
void change_board(int x,int y,BOARD &z)
{
	x+=10;y+=10;
	int t=80/3;
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
			if(mx>x+t*i&&mx<x+t*i+t&&my>y+t*j&&my<y+t*j+t)
			{
				if(Dr)z.a[i][j]=getstep(z);
			}
}
void print_line()
{
	setcolor(BLACK);
	for(int i=1;i<=LN;i++)line(node[LINE[i][0]].x+50,node[LINE[i][0]].y+50,node[LINE[i][1]].x+50,node[LINE[i][1]].y+50);
}
void mousedata()
{
	if(Dr==0)LOCK=0;
	Dl=0;Rc=0;
	while(mousemsg())
	{
		mouse_msg m=getmouse();
		if(m.is_move())mx=m.x,my=m.y;
		if(m.is_down()&&m.is_mid())Dl=1;
		if(m.is_down()&&m.is_left())Dr=1;
		if(m.is_up()&&m.is_left())Dr=0;
		if(m.is_down()&&m.is_right())Rc=1;
	}	
}
int main()
{
	initgraph(1000,600);setbkcolor(WHITE);setcolor(BLACK);
	BOARD empty=empty_board();
	while(1)
	{
		dfs(empty);
		setcaption("显示模式（点击右键编辑初始棋盘，中键展开，左键移动）");
		cout<<"TOTAL:"<<NODE<<endl;
		int t=0;
		node[1].y=250;node[1].x=5;show[1]=1;Rc=0;tree[1]=empty;
		while(Rc==0)
		{
			cleardevice();
			print_line();
			for(int i=1;i<=NODE;i++)
				if(show[i])
				{
					print_board(node[i].x,node[i].y,tree[i]);
					outtextxy(node[i].x,node[i].y-20,("["+to_string(son[i].size())+"/"+to_string(node[i].SON+son[i].size())+"]").c_str());
					if(tree[i].win==-1)outtextxy(node[i].x,node[i].y-20,"WIN:RED");
					if(tree[i].win==1)outtextxy(node[i].x,node[i].y-20,"WIN:BLUE");
					if(Dl&&!son[i].empty()&&mx>node[i].x&&mx<node[i].x+100&&my>node[i].y&&my<node[i].y+100)
					{
						show[son[i].back()]=1;node[son[i].back()].x=node[i].x+120;
						node[son[i].back()].y=node[i].y;LINE[++LN][0]=i;LINE[LN][1]=son[i].back();
						son[i].pop_back();node[i].SON++;
					}
					if(Dr&&mx>node[i].x&&mx<node[i].x+100&&my>node[i].y&&my<node[i].y+100)
					{
						if(LOCK==i||LOCK==0)
						{
							node[i].x=mx-50;node[i].y=my-50;
							LOCK=i;
						}
						
					}
				}
			mousedata();
			delay_ms(100);
		}
		setcaption("编辑模式（点击右键开始计算，左键编辑棋盘）");
		Rc=0;
		cleardevice();
		while(Rc==0)
		{
			print_board(5,250,empty);
			change_board(5,250,empty);
			mousedata();
			if(Dl)empty=empty_board();
			delay_ms(100);
		}
		for(int i=1;i<=NODE;i++)
		{
			show[i]=0;tree[i].number=0;tree[i].win=0;
			son[i].clear();node[i].SON=0;
		}
		NODE=1;LN=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

$Test2-1$

#include<iostream>
#include<vector>
#include<graphics.h>
using namespace std;
struct BOARD{int a[3][3];int number,win,score;};
struct SHOW{int x,y;int SON;}node[4020889];
int NODE=1;bool show[4028089];
BOARD tree[4028809];
vector<int>son[4002889];
int mx,my,Dl,LINE[400288][5],LN,Dr,LOCK,Rc=1;
int check(BOARD now)
{
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
			if(now.a[i][j])
				for(int fx=-1;fx<=1;fx++)
					for(int fy=-1;fy<=1;fy++)
						if(fx!=0||fy!=0)
						{
							int bo=now.a[i][j];
							for(int f=1;f<=2;f++)
								if(i+fx*f>=3||j+fy*f>=3||i+fx*f<0||j+fy*f<0||now.a[i][j]!=now.a[i+fx*f][j+fy*f])bo=0;
							if(bo)return bo;
						}
	return 0;
}
int getstep(BOARD now)
{
	int step=0;
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)step+=now.a[i][j];
	if(step==0)step=1;else step=-1;
	return step;
}
int dfs(BOARD now)
{
	tree[now.number]=now;
	if(now.win)
	{
		tree[now.number].score=now.win==-1?10:0;
		return now.win==-1?10:0;
	}
	int step=getstep(now),ping=1,Min=1e9,Max=-1e9;
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
			if(!now.a[i][j])
			{ping=0;
				NODE++;BOARD next=now;next.number=NODE;
				son[now.number].push_back(NODE);
				next.a[i][j]=step;
				next.win=check(next);
				if(step==1)Min=min(Min,dfs(next));
				else Max=max(Max,dfs(next));
				
			}
	if(ping==1)
	{
		tree[now.number].score=5;
		return 5;
	}
	tree[now.number].score=(step==1?Min:Max);
	return tree[now.number].score;
}
BOARD empty_board()
{
	BOARD empty;
	for(int i=0;i<3;i++)for(int j=0;j<3;j++)empty.a[i][j]=0;empty.number=1;empty.win=0;
	return empty;
}
void print_board(int x,int y,BOARD z)
{
	setcolor(getstep(z)==1?RED:BLUE);
	setfillcolor(WHITE);
	fillrect(x,y,x+100,y+100);
	x+=10;y+=10;
	setcolor(BLACK);
	int t=80/3;
	for(int i=x;i<=x+80;i+=t)line(i,y,i,y+80);
	for(int j=y;j<=y+80;j+=t)line(x,j,x+80,j);
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
			if(z.a[i][j]==1)
			{
				setcolor(BLUE);setlinewidth(2);
				circle(x+i*t+t/2,y+j*t+t/2,t/2-1);setlinewidth(1);
			}
	else if(z.a[i][j]==-1)
	{
		setcolor(RED);
		setlinewidth(3);
		line(x+t*i+2,y+t*j+2,x+t*i+t-2,y+t*j+t-2);
		line(x+t*i+2,y+t*j+t-2,x+t*i+t-2,y+t*j+2);
		setlinewidth(1);
	}
}
void change_board(int x,int y,BOARD &z)
{
	x+=10;y+=10;
	int t=80/3;
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
			if(mx>x+t*i&&mx<x+t*i+t&&my>y+t*j&&my<y+t*j+t)
			{
				if(Dr)z.a[i][j]=getstep(z);
			}
}
void print_line()
{
	setcolor(BLACK);
	for(int i=1;i<=LN;i++)line(node[LINE[i][0]].x+50,node[LINE[i][0]].y+50,node[LINE[i][1]].x+50,node[LINE[i][1]].y+50);
}
void mousedata()
{
	if(Dr==0)LOCK=0;
	Dl=0;Rc=0;
	while(mousemsg())
	{
		mouse_msg m=getmouse();
		if(m.is_move())mx=m.x,my=m.y;
		if(m.is_down()&&m.is_mid())Dl=1;
		if(m.is_down()&&m.is_left())Dr=1;
		if(m.is_up()&&m.is_left())Dr=0;
		if(m.is_down()&&m.is_right())Rc=1;
	}	
}
int main()
{
	initgraph(1000,600);setbkcolor(WHITE);setcolor(BLACK);
	BOARD empty=empty_board();
	while(1)
	{
		dfs(empty);
		setcaption("显示模式（点击右键编辑初始棋盘，中键展开，左键移动）");
		cout<<"TOTAL:"<<NODE<<endl;
		int t=0;
		node[1].y=250;node[1].x=5;show[1]=1;Rc=0;
		while(Rc==0)
		{
			cleardevice();
			print_line();
			for(int i=1;i<=NODE;i++)
				if(show[i])
				{
					print_board(node[i].x,node[i].y,tree[i]);
					outtextxy(node[i].x,node[i].y-20,("["+to_string(son[i].size())+"]"+"Score:"+to_string(tree[i].score)).c_str());
					if(Dl&&!son[i].empty()&&mx>node[i].x&&mx<node[i].x+100&&my>node[i].y&&my<node[i].y+100)
					{
						show[son[i].back()]=1;node[son[i].back()].x=node[i].x+120;
						node[son[i].back()].y=node[i].y;LINE[++LN][0]=i;LINE[LN][1]=son[i].back();
						son[i].pop_back();node[i].SON++;
					}
					if(Dr&&mx>node[i].x&&mx<node[i].x+100&&my>node[i].y&&my<node[i].y+100)
					{
						if(LOCK==i||LOCK==0)
						{
							node[i].x=mx-50;node[i].y=my-50;
							LOCK=i;
						}
						
					}
				}
			mousedata();
			delay_ms(100);
		}
		setcaption("编辑模式（点击右键开始计算，左键编辑棋盘）");
		Rc=0;
		cleardevice();
		while(Rc==0)
		{
			print_board(5,250,empty);
			change_board(5,250,empty);
			mousedata();
			if(Dl)empty=empty_board();
			delay_ms(100);
		}
		for(int i=1;i<=NODE;i++)
		{
			show[i]=0;tree[i].number=0;tree[i].win=0;
			son[i].clear();node[i].SON=0;
		}
		NODE=1;LN=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

$Test2-2$

#include<iostream>
#include<vector>
#include<graphics.h>
using namespace std;
struct BOARD{int a[3][3];int number,win,score;};
struct SHOW{int x,y;int SON;}node[4020889];
int NODE=1;bool show[4028089];
BOARD tree[4028809];
vector<int>son[4002889];
int mx,my,Dl,LINE[400288][5],LN,Dr,LOCK,Rc=1,PC=0;
int check(BOARD now)
{
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
			if(now.a[i][j])
				for(int fx=-1;fx<=1;fx++)
					for(int fy=-1;fy<=1;fy++)
						if(fx!=0||fy!=0)
						{
							int bo=now.a[i][j];
							for(int f=1;f<=2;f++)
								if(i+fx*f>=3||j+fy*f>=3||i+fx*f<0||j+fy*f<0||now.a[i][j]!=now.a[i+fx*f][j+fy*f])bo=0;
							if(bo)return bo;
						}
	return 0;
}
int getstep(BOARD now)
{
	int step=0;
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)step+=now.a[i][j];
	if(step==0)step=1;else step=-1;
	return step;
}
int dfs(BOARD now)
{
	tree[now.number]=now;
	if(now.win)
	{
		tree[now.number].score=now.win==-1?10:0;
		return now.win==-1?10:0;
	}
	int step=getstep(now),ping=1,Min=1e9,Max=-1e9;
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
			if(!now.a[i][j])
			{ping=0;
				NODE++;BOARD next=now;next.number=NODE;
				son[now.number].push_back(NODE);
				next.a[i][j]=step;
				next.win=check(next);
				if(step==1)Min=min(Min,dfs(next));
				else Max=max(Max,dfs(next));
				
			}
	if(ping==1)
	{
		tree[now.number].score=5;
		return 5;
	}
	tree[now.number].score=(step==1?Min:Max);
	return tree[now.number].score;
}
BOARD empty_board()
{
	BOARD empty;
	for(int i=0;i<3;i++)for(int j=0;j<3;j++)empty.a[i][j]=0;empty.number=1;empty.win=0;
	return empty;
}
void print_board(int x,int y,BOARD z)
{
	setcolor(getstep(z)==1?RED:BLUE);
	setfillcolor(WHITE);
	fillrect(x,y,x+100,y+100);
	x+=10;y+=10;
	setcolor(BLACK);
	int t=80/3;
	for(int i=x;i<=x+80;i+=t)line(i,y,i,y+80);
	for(int j=y;j<=y+80;j+=t)line(x,j,x+80,j);
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
			if(z.a[i][j]==1)
			{
				setcolor(BLUE);setlinewidth(2);
				circle(x+i*t+t/2,y+j*t+t/2,t/2-1);setlinewidth(1);
			}
	else if(z.a[i][j]==-1)
	{
		setcolor(RED);
		setlinewidth(3);
		line(x+t*i+2,y+t*j+2,x+t*i+t-2,y+t*j+t-2);
		line(x+t*i+2,y+t*j+t-2,x+t*i+t-2,y+t*j+2);
		setlinewidth(1);
	}
}
void change_board(int x,int y,BOARD &z)
{
	x+=10;y+=10;
	int t=80/3;
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
			if(mx>x+t*i&&mx<x+t*i+t&&my>y+t*j&&my<y+t*j+t)
			{
				if(Dr)z.a[i][j]=1;PC=1;
			}
}
void print_line()
{
	setcolor(BLACK);
	for(int i=1;i<=LN;i++)line(node[LINE[i][0]].x+50,node[LINE[i][0]].y+50,node[LINE[i][1]].x+50,node[LINE[i][1]].y+50);
}
void mousedata()
{
	if(Dr==0)LOCK=0;
	Dl=0;Rc=0;
	while(mousemsg())
	{
		mouse_msg m=getmouse();
		if(m.is_move())mx=m.x,my=m.y;
		if(m.is_down()&&m.is_mid())Dl=1;
		if(m.is_down()&&m.is_left())Dr=1;
		if(m.is_up()&&m.is_left())Dr=0;
		if(m.is_down()&&m.is_right())Rc=1;
	}	
}
int main()
{srand(time(0));
	initgraph(1000,600);setbkcolor(WHITE);setcolor(BLACK);
	BOARD empty=empty_board();
	while(1)
	{
		setcaption("下棋模式（左键下棋，右键确认）");Rc=0;
		while(Rc==0)
		{
			cleardevice();
			print_board(5,250,empty);
			change_board(5,250,empty);
			mousedata();
			delay_ms(50);
		}print_board(5,250,empty);
		for(int i=1;i<=NODE;i++)
		{
			show[i]=0;tree[i].number=0;tree[i].win=0;
			son[i].clear();node[i].SON=0;
		}
		NODE=1;LN=0;empty.number=1;
		dfs(empty);
		setcaption("显示模式（点击右键AI决策，中键展开，左键移动）");
		cout<<"TOTAL:"<<NODE<<endl;
		int t=0;
		node[1].y=250;node[1].x=5;show[1]=1;Rc=0;
		int Min=1e9,Max=-1e9;
		vector<BOARD>CAN;CAN.clear();
		if(son[1].size()==0)exit(0);
		//for(int i=1;i<=10;i++)cout<<son[i].size();
		for(auto i:son[1])
		{//cout<<i<<endl;
			Max=max(Max,tree[i].score);
		}
		Min=Max;
		for(auto i:son[1])if(tree[i].score==Min)CAN.push_back(tree[i]);
		empty=CAN[rand()%CAN.size()];cout<<"[COMPLETE]\n";
		while(Rc==0)
		{
			cleardevice();
			print_line();
			
			for(int i=1;i<=NODE;i++)
				if(show[i])
				{
					print_board(node[i].x,node[i].y,tree[i]);
					outtextxy(node[i].x,node[i].y-20,("["+to_string(son[i].size())+"]"+"Score:"+to_string(tree[i].score)).c_str());
					if(Dl&&!son[i].empty()&&mx>node[i].x&&mx<node[i].x+100&&my>node[i].y&&my<node[i].y+100)
					{
						show[son[i].back()]=1;node[son[i].back()].x=node[i].x+120;
						node[son[i].back()].y=node[i].y;LINE[++LN][0]=i;LINE[LN][1]=son[i].back();
						son[i].pop_back();node[i].SON++;
					}
					if(Dr&&mx>node[i].x&&mx<node[i].x+100&&my>node[i].y&&my<node[i].y+100)
					{
						if(LOCK==i||LOCK==0)
						{
							node[i].x=mx-50;node[i].y=my-50;
							LOCK=i;
						}
						
					}
				}
			mousedata();
			delay_ms(100);
		}
	}
}
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

$Test3$

#include<bits/stdc++.h>
#include<graphics.h>
using namespace std;
struct BOARD{int a[10][10];int number,win,score,stepx,stepy;};
struct SHOW{int x,y;int SON;}node[402088];
int NODE=1;bool show[402808];
BOARD tree[402880];
vector<int>son[400288];
int mx,my,Dl,LINE[400288][5],LN,Dr,LOCK,Rc=1;
int cmp(int a,int b)
{
	return tree[a].score<tree[b].score;
}
int check(BOARD now,int x,int y)
{
	for(int i=x;i<=x;i++)
		for(int j=y;j<=y;j++)
			if(now.a[i][j])
				for(int fx=-1;fx<=1;fx++)
					for(int fy=-1;fy<=1;fy++)
						if(fx!=0||fy!=0)
						{
							int bo=now.a[i][j];
							for(int f=1;f<=4;f++)
								if(i+fx*f>=10||j+fy*f>=10||i+fx*f<0||j+fy*f<0||now.a[i][j]!=now.a[i+fx*f][j+fy*f])bo=0;
							if(bo)return bo;
						}
	return 0;
}
int evaluateDirection(const BOARD board, int row, int col, int player) 
{
	int directions[4][2] = {{1, 0}, {0, 1}, {1, 1}, {1, -1}};
	int score = 0;
	for (int i = 0; i < 4; i++) 
	{
		int count = 0,dc=1;
		for (int j = 1; j <= 5; j++) 
		{
			int newRow = row + j * directions[i][0];
			int newCol = col + j * directions[i][1];
			if (newRow < 0 || newRow >= 10 || newCol < 0 || newCol >= 10 ||
				board.a[newRow][newCol] != player)
			{
				if(board.a[newRow][newCol] != 0)dc=2;
				break;
			}
			count++;
		}
		if(board.a[row  -1 * directions[i][0]][col - 1 * directions[i][1]]==-player)dc*=2;
		if (count == 1) {
			score += 1/dc;
		} else if (count == 2) {
			score += 10/dc;
		} else if (count == 3) {
			score += 100/dc;
		} else if (count == 4) {
			score += 900/dc;
		} else if (count == 5) {
			score += 1000/dc;
		}
	}
	
	return score;
}
int evaluateBoard(const BOARD board) 
{
	int score = 0;
	for (int i = 0; i < 10; i++) 
	{
		for (int j = 0; j < 10; j++) 
		{
			if (board.a[i][j] == 1) 
				score += evaluateDirection(board, i, j, 1);
			else if (board.a[i][j] == -1) 
				score -= evaluateDirection(board, i, j, -1);
		}
	}
	return score;
}
int getstep(BOARD now)
{
	int step=0;
	for(int i=0;i<10;i++)
		for(int j=0;j<10;j++)step+=now.a[i][j];
	if(step==0)step=1;else step=-1;
	return step;
}
int dfs(BOARD now,int k,int Nk)
{//if(rand()%10000==0)cout<<now.number;
	son[now.number].clear();
	int nd=NODE;
	tree[now.number]=now;
	if(now.win)
	{
		tree[now.number].score=now.win==-1?1000:0;
		return now.win==-1?1000:0;
	}
	int step=getstep(now),Min=1e9,Max=-1e9;
	if(k>min(Nk,4))
	{
		tree[now.number].score=-evaluateBoard(now);
		return tree[now.number].score;
	}
	map<int,int>ndx,ndy;
	for(int i=0;i<10;i++)
		for(int j=0;j<10;j++)
			if(!now.a[i][j])
			{
				NODE++;BOARD next=now;next.number=NODE;
				son[now.number].push_back(NODE);
				next.a[i][j]=step;ndx[NODE]=i;ndy[NODE]=j;
				next.win=check(next,i,j);next.stepx=i;next.stepy=j;
				if(step==1)Min=min(Min,dfs(next,k+1,Nk));
				else Max=max(Max,dfs(next,k+1,Nk));
			}
	sort(son[now.number].begin(),son[now.number].end(),cmp);
	if(getstep(tree[now.number])==1)reverse(son[now.number].begin(),son[now.number].end());
	if(k>2)
	{
		Min=1e9,Max=-1e9;NODE=nd;
		vector<int>SON;
		for(int i=0;i<5;i++)
		{
			NODE++;BOARD next=now;next.number=NODE;
			SON.push_back(NODE);
			next.stepx=ndx[son[now.number][i]];next.stepy=ndy[son[now.number][i]];
			next.a[next.stepx][next.stepy]=step;next.win=check(next,next.stepx,next.stepy);
			if(step==1)Min=min(Min,dfs(next,k+1,k+3));
			else Max=max(Max,dfs(next,k+1,k+3));
		}
		son[now.number]=SON;
	}
	
	tree[now.number].score=(step==1?Min:Max);
	return tree[now.number].score;
}
BOARD empty_board()
{
	BOARD empty;
	for(int i=0;i<10;i++)for(int j=0;j<10;j++)empty.a[i][j]=0;empty.number=1;empty.win=0;
	return empty;
}
void print_board_all(int x,int y,BOARD z)
{
	setcolor(getstep(z)==1?RED:BLUE);
	setfillcolor(WHITE);
	fillrect(x,y,x+300,y+300);
	x+=10;y+=10;
	setcolor(BLACK);
	int t=270/10;
	for(int i=x;i<=x+280;i+=t)line(i,y,i,y+280);
	for(int j=y;j<=y+280;j+=t)line(x,j,x+280,j);
	for(int i=0;i<10;i++)
		for(int j=0;j<10;j++)
			if(z.a[i][j]==1)
			{
				setcolor(BLUE);setlinewidth(2);
				circle(x+i*t+t/2,y+j*t+t/2,t/2-1);setlinewidth(1);
			}
	else if(z.a[i][j]==-1)
	{
		setcolor(RED);
		setlinewidth(3);
		line(x+t*i+2,y+t*j+2,x+t*i+t-2,y+t*j+t-2);
		line(x+t*i+2,y+t*j+t-2,x+t*i+t-2,y+t*j+2);
		setlinewidth(1);
	}
}
void print_board_step(int x,int y,BOARD z)
{
	setcolor(getstep(z)==1?RED:BLUE);
	setfillcolor(WHITE);
	fillrect(x,y,x+100,y+40);
	x+=20;y+=10;
	setcolor(BLACK);
	if(z.stepx==0&&z.stepy==0);else
		outtextxy(x,y,("("+to_string(z.stepx+1)+","+to_string(z.stepy+1)+")").c_str());
}
void change_board(int x,int y,BOARD &z)
{
	x+=10;y+=10;
	int t=270/10;
	for(int i=0;i<10;i++)
		for(int j=0;j<10;j++)
			if(mx>x+t*i&&mx<x+t*i+t&&my>y+t*j&&my<y+t*j+t)
			{
				if(Dr)z.a[i][j]=getstep(z);
			}
}
void print_line()
{
	setcolor(BLACK);
	for(int i=1;i<=LN;i++)line(node[LINE[i][0]].x+50,node[LINE[i][0]].y+20,node[LINE[i][1]].x+50,node[LINE[i][1]].y+20);
}
void mousedata()
{
	if(Dr==0)LOCK=0;
	Dl=0;Rc=0;
	while(mousemsg())
	{
		mouse_msg m=getmouse();
		if(m.is_move())mx=m.x,my=m.y;
		if(m.is_down()&&m.is_mid())Dl=1;
		if(m.is_down()&&m.is_left())Dr=1;
		if(m.is_up()&&m.is_left())Dr=0;
		if(m.is_down()&&m.is_right())Rc=1;
	}	
}

int main()
{
	initgraph(1000,600);setbkcolor(WHITE);setcolor(BLACK);
	BOARD empty=empty_board();
	while(1)
	{
		setcaption("游玩模式（点击右键AI开始计算，左键下棋）");
		Rc=0;
		cleardevice();
		while(Rc==0)
		{
			print_board_all(5,250,empty);
			change_board(5,250,empty);
			mousedata();
			if(Dl)empty=empty_board();
			delay_ms(100);
		}
		for(int i=1;i<=NODE;i++)
		{
			show[i]=0;tree[i].number=0;tree[i].win=0;
			son[i].clear();node[i].SON=0;
		}
		NODE=1;LN=0;
		dfs(empty,1,2);
		setcaption("显示模式（点击右键编辑初始棋盘，中键展开，左键移动）");
		cout<<"TOTAL:"<<NODE<<endl;
		int t=0;
		node[1].y=250;node[1].x=5;show[1]=1;Rc=0;int lc=1;
		empty=tree[son[1].back()];empty.number=1;empty.score=0;
		while(Rc==0)
		{
			cleardevice();
			print_line();print_board_all(0,0,tree[lc==0?1:lc]);
			for(int i=NODE;i>=1;i--)
				if(show[i])
				{
					
					print_board_step(node[i].x,node[i].y,tree[i]);
					outtextxy(node[i].x,node[i].y-20,("["+to_string(son[i].size())+"]"+"Score:"+to_string(tree[i].score)).c_str());
					if(Dl&&!son[i].empty()&&mx>node[i].x&&mx<node[i].x+100&&my>node[i].y&&my<node[i].y+100)
					{
						show[son[i].back()]=1;node[son[i].back()].x=node[i].x+120;
						node[son[i].back()].y=node[i].y;LINE[++LN][0]=i;LINE[LN][1]=son[i].back();
						son[i].pop_back();node[i].SON++;
					}
					if(Dr&&mx>node[i].x&&mx<node[i].x+100&&my>node[i].y&&my<node[i].y+40)
					{
						if(LOCK==i||LOCK==0)
						{
							node[i].x=mx-50;node[i].y=my-20;
							LOCK=i;lc=i;
						}
						
					}
				}
			mousedata();
			delay_ms(100);
		}
		
	}
}
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

$五子棋最终AI(我无法评价)$

#include<bits/stdc++.h>
#include<graphics.h>
using namespace std;
struct BOARD{int a[10][10];int number,win,score,stepx,stepy;};
struct SHOW{int x,y;int SON;}node[402088];
int NODE=1;bool show[402808];
BOARD tree[402880];
vector<int>son[400288];
int mx,my,Dl,LINE[400288][5],LN,Dr,LOCK,Rc=1;
int cmp(int a,int b)
{
	return tree[a].score<tree[b].score;
}
int check(BOARD now,int x,int y)
{
	for(int i=x;i<=x;i++)
		for(int j=y;j<=y;j++)
			if(now.a[i][j])
				for(int fx=-1;fx<=1;fx++)
					for(int fy=-1;fy<=1;fy++)
						if(fx!=0||fy!=0)
						{
							int bo=now.a[i][j];
							for(int f=1;f<=4;f++)
								if(i+fx*f>=10||j+fy*f>=10||i+fx*f<0||j+fy*f<0||now.a[i][j]!=now.a[i+fx*f][j+fy*f])bo=0;
							if(bo)return bo;
						}
	return 0;
}
int evaluateDirection(const BOARD board, int row, int col, int player) 
{
	int directions[4][2] = {{1, 0}, {0, 1}, {1, 1}, {1, -1}};
	int score = 0;
	for (int i = 0; i < 4; i++) 
	{
		int count = 0,dc=1;
		for (int j = 1; j <= 5; j++) 
		{
			int newRow = row + j * directions[i][0];
			int newCol = col + j * directions[i][1];
			if (newRow < 0 || newRow >= 10 || newCol < 0 || newCol >= 10 ||
				board.a[newRow][newCol] != player)
			{
				if(board.a[newRow][newCol] != 0)dc=2;
				break;
			}
			count++;
		}
		if(board.a[row  -1 * directions[i][0]][col - 1 * directions[i][1]]==-player)dc*=2;
		if (count == 1) {
			score += 1/dc;
		} else if (count == 2) {
			score += 10/dc;
		} else if (count == 3) {
			score += 100/dc;
		} else if (count == 4) {
			score += 900/dc;
		} else if (count == 5) {
			score += 1000/dc;
		}
	}
	
	return score;
}
int evaluateBoard(const BOARD board) 
{
	int score = 0;
	for (int i = 0; i < 10; i++) 
	{
		for (int j = 0; j < 10; j++) 
		{
			if (board.a[i][j] == 1) 
				score += evaluateDirection(board, i, j, 1);
			else if (board.a[i][j] == -1) 
				score -= evaluateDirection(board, i, j, -1);
		}
	}
	return score;
}
int getstep(BOARD now)
{
	int step=0;
	for(int i=0;i<10;i++)
		for(int j=0;j<10;j++)step+=now.a[i][j];
	if(step==0)step=1;else step=-1;
	return step;
}
int dfs(BOARD now,int k,int Nk,int alpha,int beta)
{//if(rand()%10000==0)cout<<now.number;
	son[now.number].clear();
	int nd=NODE;
	tree[now.number]=now;
	if(now.win)
	{
		tree[now.number].score=now.win==-1?1000:0;
		return now.win==-1?1000:0;
	}
	int step=getstep(now),Min=1e9,Max=-1e9;
	if(k>min(Nk,6))
	{
		tree[now.number].score=-evaluateBoard(now);
		return tree[now.number].score;
	}
	map<int,int>ndx,ndy;
	for(int i=0;i<10;i++)
		for(int j=0;j<10;j++)
			if(!now.a[i][j])
			{
				NODE++;BOARD next=now;next.number=NODE;
				son[now.number].push_back(NODE);
				next.a[i][j]=step;ndx[NODE]=i;ndy[NODE]=j;
				next.win=check(next,i,j);next.stepx=i;next.stepy=j;
				int t=step==1?dfs(next,k+1,Nk,alpha,Min):dfs(next,k+1,Nk,Max,beta);
				//if(t>beta||t<alpha)return t;
				if(step==1)Min=min(Min,t);
				else Max=max(Max,t);
			}
	sort(son[now.number].begin(),son[now.number].end(),cmp);
	if(getstep(tree[now.number])==1)reverse(son[now.number].begin(),son[now.number].end());
	if(k>2)
	{
		Min=1e9,Max=-1e9;NODE=nd;
		vector<int>SON;
		for(int i=0;i<5;i++)
		{
			NODE++;BOARD next=now;next.number=NODE;
			SON.push_back(NODE);
			next.stepx=ndx[son[now.number][i]];next.stepy=ndy[son[now.number][i]];
			next.a[next.stepx][next.stepy]=step;next.win=check(next,next.stepx,next.stepy);
			int t=step==1?dfs(next,k+1,Nk,alpha,Min):dfs(next,k+1,Nk,Max,beta);
			if(step==1)Min=min(Min,t);
			else Max=max(Max,t);
		}
		son[now.number]=SON;
	}
	
	tree[now.number].score=(step==1?Min:Max);
	return tree[now.number].score;
}
BOARD empty_board()
{
	BOARD empty;
	for(int i=0;i<10;i++)for(int j=0;j<10;j++)empty.a[i][j]=0;empty.number=1;empty.win=0;
	return empty;
}
void print_board_all(int x,int y,BOARD z)
{
	setcolor(getstep(z)==1?RED:BLUE);
	setfillcolor(WHITE);
	fillrect(x,y,x+300,y+300);
	x+=10;y+=10;
	setcolor(BLACK);
	int t=270/10;
	for(int i=x;i<=x+280;i+=t)line(i,y,i,y+280);
	for(int j=y;j<=y+280;j+=t)line(x,j,x+280,j);
	for(int i=0;i<10;i++)
		for(int j=0;j<10;j++)
			if(z.a[i][j]==1)
			{
				setcolor(BLUE);setlinewidth(2);
				circle(x+i*t+t/2,y+j*t+t/2,t/2-1);setlinewidth(1);
			}
	else if(z.a[i][j]==-1)
	{
		setcolor(RED);
		setlinewidth(3);
		line(x+t*i+2,y+t*j+2,x+t*i+t-2,y+t*j+t-2);
		line(x+t*i+2,y+t*j+t-2,x+t*i+t-2,y+t*j+2);
		setlinewidth(1);
	}
}
void print_board_step(int x,int y,BOARD z)
{
	setcolor(getstep(z)==1?RED:BLUE);
	setfillcolor(WHITE);
	fillrect(x,y,x+100,y+40);
	x+=20;y+=10;
	setcolor(BLACK);
	if(z.stepx==0&&z.stepy==0);else
		outtextxy(x,y,("("+to_string(z.stepx+1)+","+to_string(z.stepy+1)+")").c_str());
}
void change_board(int x,int y,BOARD &z)
{
	x+=10;y+=10;
	int t=270/10;
	for(int i=0;i<10;i++)
		for(int j=0;j<10;j++)
			if(mx>x+t*i&&mx<x+t*i+t&&my>y+t*j&&my<y+t*j+t)
			{
				if(Dr)z.a[i][j]=getstep(z);
			}
}
void print_line()
{
	setcolor(BLACK);
	for(int i=1;i<=LN;i++)line(node[LINE[i][0]].x+50,node[LINE[i][0]].y+20,node[LINE[i][1]].x+50,node[LINE[i][1]].y+20);
}
void mousedata()
{
	if(Dr==0)LOCK=0;
	Dl=0;Rc=0;
	while(mousemsg())
	{
		mouse_msg m=getmouse();
		if(m.is_move())mx=m.x,my=m.y;
		if(m.is_down()&&m.is_mid())Dl=1;
		if(m.is_down()&&m.is_left())Dr=1;
		if(m.is_up()&&m.is_left())Dr=0;
		if(m.is_down()&&m.is_right())Rc=1;
	}	
}

int main()
{
	initgraph(1000,600);setbkcolor(WHITE);setcolor(BLACK);
	BOARD empty=empty_board();
	while(1)
	{
		setcaption("游玩模式（点击右键AI开始计算，左键下棋）");
		Rc=0;
		cleardevice();
		while(Rc==0)
		{
			print_board_all(0,0,empty);
			change_board(0,0,empty);
			mousedata();
			if(Dl)empty=empty_board();
			delay_ms(100);
		}
		for(int i=1;i<=NODE;i++)
		{
			show[i]=0;tree[i].number=0;tree[i].win=0;
			son[i].clear();node[i].SON=0;
		}
		NODE=1;LN=0;
		dfs(empty,1,3,-10000,10000);
		setcaption("显示模式（点击右键编辑初始棋盘，中键展开，左键移动）");
		cout<<"TOTAL:"<<NODE<<endl;
		int t=0;
		node[1].y=250;node[1].x=5;show[1]=1;Rc=0;int lc=1;
		empty=tree[son[1].back()];empty.number=1;empty.score=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