五子棋——AI篇

内容介绍

上一篇我们讲到五子棋的UI篇的实现,现在这一篇我们来讲五子棋的AI篇的实现。
我们在这里把这个实现的过程分成几部分:

  • 赢法数组
    用一个三维的数组记录五子棋的所有赢法。
  • 每种赢法的统计数组
    我们用一维数组来记录每种赢法
  • 如何判断输赢
    判断输赢的方法
  • 实现计算机落子
    这部分是重点,算法设计精准,计算机的棋艺就高

所有代码在上一篇的UI的基础上实现,建议首先阅读UI篇。在UI篇的JS文件下打代码。

赢法数组

首先定义一个三维的数组,用于存放所有赢的情况。

1
2
3
4
5
6
7
8
9
//赢法数组
var wins = [] ;
//三维数组
for(var i=0; i<15; i++){
wins[i] = [] ;
for(var j=0;j<15; j++){
wins[i][j] = [] ;
}
}

定义count用于记录赢的方法种类数量,然后再遍历所有赢的情况,包括横向、纵向、斜向、反斜向,下面以横向为例讲解。

1
2
3
4
5
6
7
8
9
10
11
12
//赢法统计
var count = 0 ;
//横线
for(var i=0; i<15; i++){
for(var j=0; j<11; j++){
for(var k=0; k<5; k++){
//此循环结束,就是横向的第一种赢法
wins[i][j+k][count] = true;
}
count++ ;
}
}

这是五个棋子呈横的形式赢的情况。
这里有三个循环,第一个循环是指每一条横线。第二个循环指的是摆成五个子,第一个子的纵坐标。第三个循环是摆满五个棋子,里重点说说为什么j<11。如果你想更好地理解,可以代些数进去看一下是什么情况。
如果j=10时,赢的情况是如下图:
blob.png
如果j还比10大的话就会超出棋盘。
以此类推,纵向、斜向、反斜向也是同理:

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
//纵线
for(var i=0; i<15; i++){
for(var j=0; j<11; j++){
for(var k=0; k<5; k++){
wins[j+k][i][count] = true;
}
count++ ;
}
}
//正斜线
for(var i=0; i<11; i++){
for(var j=0; j<11; j++){
for(var k=0; k<5; k++){
wins[i+k][j+k][count] = true;
}
count++ ;
}
}
//反斜线
for(var i=0; i<11; i++){
for(var j=14; j>3; j--){
for(var k=0; k<5; k++){
wins[i+k][j-k][count] = true;
}
count++ ;
}
}
console.log(count);//572

最后在后台输出总共有多少种赢法。我们由此知道,15*15的棋盘总共有572种赢法,所有赢法计算机都知道了,所以,如果代码打得好,你根本无法赢机器。

赢法的统计数组

这是一个一维的数组,用来计算某种赢法是否达成。上面列举了所有的赢法,那在某赢法中成功落下一个棋子,那我们就为该种赢法的值加1,直到加5就实现了此种赢法,实现结束游戏。那如果该赢法中有另一方的棋子,此种赢法报废。大概就是这么一个思路。计算机落子的目的就是去破坏你某种赢法的可行性,所以计算机落子的风格跟人有很大的区别。
定义并实例化两个数组,一个用来存放玩家赢法的数组,另一个用来存放电脑赢法的数组。
还定义了一个over变量,标志游戏是否结束。

1
2
3
4
5
6
7
8
9
10
//游戏结束
var over = false ;
//统计记法数组
var myWin = [] ;
var computerWin = [] ;
//统计数组的实例化
for(var i=0; i<count; i++){
myWin[i] = 0 ;
computerWin[i] = 0 ;
}

在单击事件,成功落子后进行一个循环。
这个循环遍历所有的赢法,如果某种赢法里有棋子,就myWin[k]++,如果myWin[k] == 5成立了,改变over的标志,就代表你赢了。

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
chess.onclick = function (e){
if(over){//判断游戏是否结束
return ;
}
var x = e.offsetX ;
var y = e.offsetY ;
var i = Math.floor(x/30) ;
var j = Math.floor(y/30) ;
if(chessBoard[i][j] == 0){
oneStep(i,j,me);
if(me){
chessBoard[i][j] = 1 ;
}else{
chessBoard[i][j] = 2 ;
}
me = !me ;
//落下子后需要进行统计
for(var k=0; k<count; k++){
if(wins[i][j][k]){//某种赢的某子true
myWin[k]++;//离胜利又进一步
computerWin[k] = 6 ;//该种赢法计算机没有机会了
if(myWin[k] == 5){//如果达到5就赢了
window.alert("厉害,你赢了!!");
over = true ;
}
}
}
}
}

测试,如下图所示,如果你下够五个子,就弹窗提示你赢了,这里有点不好,就是你要点击确认,第五个棋子才出来。
blob.png

计算机判断有效落棋点

在完成落子统计后判断是否结束游戏,如果没结束,就轮到计算机下棋,计算棋下棋调用computerAi()方法。

1
2
3
4
if(!over){
me = !me ; //如果游戏没结束,下棋权利交给计算机
computerAi();//计算机AI
}

在点击鼠标的时候需要判断是否轮到人落棋:

1
2
3
if(!me){//不到你下棋点击无效
return ;
}

更改落棋的判断,如果鼠标点击,只下黑棋,并且只改变黑棋的频数统计。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
if(chessBoard[i][j] == 0){
oneStep(i,j,me);//需要要更改处
chessBoard[i][j] = 1 ;
//落下子后需要进行统计
for(var k=0; k<count; k++){
if(wins[i][j][k]){//某种赢的某子true
myWin[k]++;//离胜利又进一步
computerWin[k] = 6 ;//该种赢法计算机没有机会了
if(myWin[k] == 5){//如果达到5就赢了
window.alert("厉害,你赢了!!");
over = true ;
}
}
}
if(!over){
me = !me ; //如果游戏没结束,下棋权利交给计算机
computerAI();//计算机AI
}
}

接下来实现computerAi()方法的棋步权值。

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
var computerAI = function(){
var myScore = [] ;//定义两个数组,用于存放每个点的分值
var computerScore = [] ;
for(var i=0; i<15; i++){
myScore[i] = [] ;
computerScore[i] = [] ;
for(var j=0; j<15; j++){
myScore[i][j] = 0 ;
computerScore[i][j] = 0;
}
}
//为所有赢法打分
for(var i=0; i<15; i++){
for(var j=0; j<15; j++){
if(chessBoard[i][j] == 0){//该点可下棋
for(var k=0; k<count; k++){//遍历所有赢法
if(wins[i][j][k]){//这种赢法已经有子
if(myWin[k] == 1){//黑方,有1个子
myScore[i][j] += 200 ;
}else if(myWin[k] == 2){
myScore[i][j] += 400 ;
}else if(myWin[k] == 3){
myScore[i][j] += 2000 ;
}else if(myWin[k] == 4){
myScore[i][j] += 10000 ;
}
if(computerWin[k] == 1){//白方,有1个子
computerScore[i][j] += 220 ;
}else if(computerWin[k] == 2){
computerScore[i][j] += 420 ;
}else if(computerWin[k] == 3){
computerScore[i][j] += 2200 ;
}else if(computerWin[k] == 4){
computerScore[i][j] += 20000 ;
}
}
}
}
}
}
}

如上代码,首先定义并实例化myScore[]computerScore[]两个数组,用于存放各个棋点的落子价值,再分别遍历人和计算机的所有赢法,如果有1、2、3、4子,分别为棋点附权值。

实现计算机落子

接下来我们找到计算机落子的最佳坐标,然后在这个坐标上落子,就实现了计算机落子的功能了,在这里把整个computerAI()函数贴出来再进行讲解:

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
var computerAI = function(){
var myScore = [] ;//定义两个数组,用于存放每个点的分值
var computerScore = [] ;
var max = 0 ;//落子的价值
var u = 0, v = 0 ;//落子的坐标
for(var i=0; i<15; i++){
myScore[i] = [] ;
computerScore[i] = [] ;
for(var j=0; j<15; j++){
myScore[i][j] = 0 ;
computerScore[i][j] = 0;
}
}
//为所有赢法打分
for(var i=0; i<15; i++){
for(var j=0; j<15; j++){
if(chessBoard[i][j] == 0){//该点可下棋
for(var k=0; k<count; k++){//遍历所有赢法
if(wins[i][j][k]){//这种赢法已经有子
if(myWin[k] == 1){//黑方,有1个子
myScore[i][j] += 200 ;
}else if(myWin[k] == 2){
myScore[i][j] += 400 ;
}else if(myWin[k] == 3){
myScore[i][j] += 2000 ;
}else if(myWin[k] == 4){
myScore[i][j] += 10000 ;
}
if(computerWin[k] == 1){//白方,有1个子
computerScore[i][j] += 220 ;
}else if(computerWin[k] == 2){
computerScore[i][j] += 420 ;
}else if(computerWin[k] == 3){
computerScore[i][j] += 2200 ;
}else if(computerWin[k] == 4){
computerScore[i][j] += 20000 ;
}
}
}
//下面判断计算机落子的最佳处
if(myScore[i][j] > max ){//人在某步的权值更高的时候
max = myScore[i][j] ;
u = i ;
v = j ;
}else if(myScore[i][j] = max){//如果权值是最大了
if(computerScore[i][j] > computerScore[u][v]){//而i,j点的权值比在u,v点的更大时
u = i ;
v = j ;
}
}
if(computerScore[i][j] > max ){//人在某步的权值更高的时候
max = computerScore[i][j] ;
u = i ;
v = j ;
}else if(computerScore[i][j] = max){//如果权值是最大了
if(myScore[i][j] > myScore[u][v]){//而计算机在此处落子更有用
u = i ;
v = j ;
}
}
}
}
}
oneStep(u, v, false) ;//上面得到最佳落子点,现在为其落白子
chessBoard[u][v] == 2 ;
//计算机落完子后需要进行统计
for(var k=0; k<count; k++){
if(wins[u][v][k]){//某种赢的某子true
computerWin[k]++;//离胜利又进一步
myWin[k] = 6 ;//该种赢法计算机没有机会了
if(computerWin[k] == 5){//如果达到5就赢了
window.alert("计算机赢了!!");
over = true ;
}
}
}
if(!over){
me = !me ; //如果游戏没结束,
}
}

上面函数的代码比较长,其实很多一部分都是与上面有重复的。
为了找到棋盘坐标最高权值和其坐标点,这里定义三个变量maxuv 。通过上遍历所有赢法的值后,这里只要判断比较在哪一方的赢法中落子价值大,主要是自己向着赢的方向前进和不让对方赢的方向进行阻挡。
如下面是比较的权值的代码,通过以下代码得到(u,v)这个权值最大的坐标:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//下面判断计算机落子的最佳处
if(myScore[i][j] > max ){//人在某步的权值更高的时候
max = myScore[i][j] ;
u = i ;
v = j ;
}else if(myScore[i][j] = max){//如果权值是最大了
if(computerScore[i][j] > computerScore[u][v]){//而i,j点的权值比在u,v点的更大时
u = i ;
v = j ;
}
}
if(computerScore[i][j] > max ){//人在某步的权值更高的时候
max = computerScore[i][j] ;
u = i ;
v = j ;
}else if(computerScore[i][j] = max){//如果权值是最大了
if(myScore[i][j] > myScore[u][v]){//而计算机在此处落子更有用
u = i ;
v = j ;
}
}

得到最大权值的坐标后,我们就要实现在该位置落子:
落完子后要对落子的位置进行统计,如果达到赢的情况就终止游戏,否则把落子权交给鼠标。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
oneStep(u, v, false) ;//上面得到最佳落子点,现在为其落白子
chessBoard[u][v] == 2 ;
//计算机落完子后需要进行统计
for(var k=0; k<count; k++){
if(wins[u][v][k]){//某种赢的某子true
computerWin[k]++;//离胜利又进一步
myWin[k] = 6 ;//该种赢法计算机没有机会了
if(computerWin[k] == 5){//如果达到5就赢了
window.alert("计算机赢了!!");
over = true ;
}
}
}
if(!over){
me = !me ; //如果游戏没结束,
}

游戏已经完成了,你们可以点击这里体验一下。明白这个算法的实现后,你们也可以不断思考,不断改进算法,提高计算机的棋艺。如果你们最终下来没有达到想要的效果,可以去下载我的源码,查看一下,自己的代码在哪一步出错了。下载源码的地址是点击这里

总结

整个游戏分为UI篇和AI篇都完成了,这里分以下三部分完成:

  • 赢法数组
    用一个三维的数组记录五子棋的所有赢法。每种赢法都有一个值,值达到5就结束游戏。
  • 确定计算机落子点
    这是难点,我们通过为某种赢法附一个权值,权值最大的就是落子价值最大的。
  • 实现计算机落子
    通过上一步计算机找到了权值最大的落子坐标后,我们就可以实现落子了。
Allen151 wechat
评论功能没弄好,如果有问题,欢迎在我公众号上提问!!
坚持原创,您的支持将鼓励我继续创作!