博弈算法实现三子棋

81 阅读 0 评论 54 点赞

我是靠谱客的博主沉默板栗，最近开发中收集的这篇文章主要介绍博弈算法实现三子棋，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

用博弈树算法实现井字棋游戏。井字棋游戏是一种简单的棋类游戏，在3*3的棋盘上，两人轮流下子，谁的棋子先连成3颗一条直线，谁就赢了，可以横着、竖着、斜着。博弈树算法是用搜索来解决这类问题的算法，井字棋游戏步数较少，很容易用博弈树算法实现

#include<iostream>
#include<stdlib.h>
#include<stdio.h>
using namespace std;
int num = 0;
int p, q;
int tmpQP[3][3]; //表示棋盘数据的临时数组，其中的元素0表示该格为空，
int cur[3][3];
const int depth = 3;
//搜索树的最大深度
void Init()
{
for (int i = 0; i<3; i++)
for (int j = 0; j<3; j++)
{
cur[i][j] = 0;
}
}
void PrintQP()
//打印当棋盘格局的函数
{
for (int i = 0; i<3; i++)
{
for (int j = 0; j<3; j++)
cout << cur[i][j] << 't';
cout << endl;//换行
}
}
int CheckWin() //有人赢了吗？返回0表示没有人赢，返回-1表示人赢了，返回1表示计算机赢了
{
for (int i = 0; i<3; i++)
{
if (cur[i][0] == 1 && cur[i][1] == 1 && cur[i][2] == 1)
return 1;
if (cur[i][0] == -1 && cur[i][1] == -1 && cur[i][2] == -1)
return -1;
}
for (int i = 0; i<3; i++)
{
if (cur[0][i] == 1 && cur[1][i] == 1 && cur[2][i] == 1)
return 1;
if (cur[0][i] == -1 && cur[1][i] == -1 && cur[2][i] == -1)
return -1;
}
if ((cur[0][0] == 1 && cur[1][1] == 1 && cur[2][2] == 1) || (cur[2][0] == 1 && cur[1][1] == 1 && cur[0][2] == 1))
return 1;
if ((cur[0][0] == -1 && cur[1][1] == -1 && cur[2][2] == -1) || (cur[2][0] == -1 && cur[1][1] == -1 && cur[0][2] == -1))
return -1;
return 0;
}
int value()//评估函数
{
p = 0;
q = 0;
//将棋盘中的空格填满自己的棋子，既将棋盘数组中的0变为1
for (int i = 0; i<3; i++)
for (int j = 0; j<3; j++)
if (cur[i][j] == 0)
tmpQP[i][j] = 1;
else
tmpQP[i][j] = cur[i][j];
//电脑一方
//计算每一行中有多少行的棋子连成3个的
for (int i = 0; i<3; i++)
p += (tmpQP[i][0] + tmpQP[i][1] + tmpQP[i][2]) / 3;
//计算每一列中有多少列的棋子连成3个的
for (int i = 0; i<3; i++)
p += (tmpQP[0][i] + tmpQP[1][i] + tmpQP[2][i]) / 3;
//斜行有没有连成3个的？
p += (tmpQP[0][0] + tmpQP[1][1] + tmpQP[2][2]) / 3;
p += (tmpQP[2][0] + tmpQP[1][1] + tmpQP[0][2]) / 3;
//将棋盘中的空格填满对方的棋子，既将棋盘数组中的0变为-1
for (int i = 0; i<3; i++)
for (int j = 0; j<3; j++)
if (cur[i][j] == 0)tmpQP[i][j] = -1;
else tmpQP[i][j] = cur[i][j];
//对方
//计算每一行中有多少行的棋子连成3个的
for (int i = 0; i<3; i++)
q += (tmpQP[i][0] + tmpQP[i][1] + tmpQP[i][2]) / 3;
//计算每一列中有多少列的棋子连成3个的
for (int i = 0; i<3; i++)
q += (tmpQP[0][i] + tmpQP[1][i] + tmpQP[2][i]) / 3;
//斜行有没有连成3个的？
q += (tmpQP[0][0] + tmpQP[1][1] + tmpQP[2][2]) / 3;
q += (tmpQP[2][0] + tmpQP[1][1] + tmpQP[0][2]) / 3;
return p + q;
}
//极大结点下界为A,极小结点上界为B
int cut(int &val, int dep, bool max)
//主算法部分，实现A－B剪枝的算法，val为上一层的评价值，dep为搜索深度，max记录上一层是否为极大层
{
if (dep == depth || dep + num == 9)
//如果搜索深度达到最大深度，或者深度加上当前棋子数已经达到9，就直接调用评价函数
{
return value();
}
int i, j, flag, temp;
bool out = false;
//out记录是否剪枝，初始为false
if (CheckWin() == 1)
//如果用户玩家输了，就置上一层的评价值为无穷（用很大的值代表无穷）
{
val = 10000;
return 0;
}
if (max)
//如果上一层是极大层，本层则需要是极小层，记录flag为无穷大；反之，则为记录为负无穷大
flag = 10000;
//flag记录本层节点的极值
else
flag = -10000;
for (i = 0; i<3 && !out; i++)
//两重循环，遍历棋盘所有位置
{
for (j = 0; j<3 && !out; j++)
{
if (cur[i][j] == 0)
//如果该位置上没有棋子
{
if (max)
//并且为上一层为极大层，即本层为极小层,轮到用户玩家走了。
{
cur[i][j] = -1;
//该位置填上用户玩家棋子
if (CheckWin() == -1)
//如果用户玩家赢了
temp = -10000;
//置棋盘评价值为负无穷
else
temp = cut(flag, dep + 1, !max);
//否则继续调用ab剪枝函数
if (temp<flag)
//如果下一步棋盘的评价值小于本层节点的极值，则置本层极值为更小者，即后辈结点极小值<=祖先节点极大值
flag = temp;
if (flag <= val)
//如果本层的极值已经小于上一层的评价值，则不需要搜索下去，剪枝
A剪枝
out = true;
}
else
//如果上一层为极小层，算法与上面刚好相反
{
cur[i][j] = 1;//该位置填上电脑玩家棋子
if (CheckWin() == 1)//如果电脑玩家赢了，置棋盘评价值为正无穷
temp = 10000;
else
temp = cut(flag, dep + 1, !max); // 否则继续调用ab剪枝函数
if (temp>flag)
//如果下一步棋盘的评价值大于本层节点的极值，则置本层极值为更小者，即后辈结点极大值>=祖先节点极小值
flag = temp;
if (flag >= val)
//如果本层的极值已经大于上一层的评价值，则不需要搜索下去，剪枝 B剪枝
out = true;
}
cur[i][j] = 0;
//把模拟下的一步棋还原，回溯
}
}
}
if (max)
//根据上一层是否为极大层，用本层的极值修改上一层的评价值
{
if (flag>val)
val = flag;
}
else
{
if (flag<val)
val = flag;
}
return flag;
//函数返回的是本层的极值
}
//用户通过此函数来输入落子的位置，
//比如，用户输入31，则表示用户在第3行第1列落子。
void UserInput()
{
int pos, x, y;
L1: cout << "Please input your qizi (xy):n ";
cin >> pos;
x = pos / 10, y = pos % 10;
if (x>0 && x<4 && y>0 && y<4 && cur[x - 1][y - 1] == 0)
{
cur[x - 1][y - 1] = -1;
}
else
{
cout << "Input Error!n";
goto L1;
}
}
//主程序
int main()
{
int m = -10000, val = -10000, dep = 1;
//m 用来存放最大的val
int x_pos, y_pos;
//记录最佳走步的坐标
Init();
cout << "Qipan: " << endl;
PrintQP();
char IsFirst;
cout << "Do you want do first?(y/n)";
cin >> IsFirst;
while (IsFirst != 'y'&&IsFirst != 'n')
{
cout << "ERROR!" << "Do you want do first?(y/n)";
cin >> IsFirst;
}
if (IsFirst == 'y')
{
L4:
// 人先走
UserInput();
PrintQP();
cout << endl;
num++;
value();
if (q == 0)
{
cout << "DOWN GAME!" << endl;
system("pause");
return 0;
}
if (CheckWin() == -1)
{
cout << "You Win! GAME OVER." << endl;
system("pause");
return 0;
}
for (int x = 0; x<3; x++)
for (int y = 0; y<3; y++){
if (cur[x][y] == 0){
cur[x][y] = 1;
cut(val, dep, 1);
if (CheckWin() == 1)
{
cout << "The computer put the qizi at:" << x + 1 << y + 1 << endl;
PrintQP();
cout << "The computer WIN! GAME OVER." << endl;
system("pause");
return 0;
}
if (val>m) {
m = val;
x_pos = x; y_pos = y;
}
val = -10000;
cur[x][y] = 0;
}
}
cur[x_pos][y_pos] = 1;
val = -10000; m = -10000; dep = 1;
cout << "The computer put the qizi at:" << x_pos + 1 << y_pos + 1 << endl;
PrintQP();
cout << endl;
num++;
value();
if (q == 0)
{
cout << "DOWN GAME!" << endl;
system("pause");
return 0;
}
goto L4;
}
else
{
// 计算机先走
L5:
for (int x = 0; x<3; x++)
for (int y = 0; y<3; y++){
if (cur[x][y] == 0){
cur[x][y] = 1;
cut(val, dep, 1);
if (CheckWin() == 1)
{
cout << "The computer put the qizi at:" << x + 1 << y + 1 << endl;
PrintQP();
cout << "The computer WIN! GAME OVER." << endl;
system("pause");
return 0;
}
if (val>m) {
m = val;
x_pos = x; y_pos = y;
}
val = -10000;
cur[x][y] = 0;
}
}
cur[x_pos][y_pos] = 1;
val = -10000; m = -10000; dep = 1;
cout << "The computer put the qizi at:" << x_pos + 1 << y_pos + 1 << endl;
PrintQP();
cout << endl;
num++;
value();
if (p == 0)
{
cout << "DOWN GAME!" << endl;
system("pause");
return 0;
}
UserInput();
PrintQP();
cout << endl;
num++;
value();
if (p == 0)
{
cout << "DOWN GAME!" << endl;
system("pause");
return 0;
}
if (CheckWin() == -1)
{
cout << "Conguatulations! You Win! GAME OVER." << endl;
system("pause");
return 0;
}
goto L5;
}
system("pause");
return 0;
}