博弈问题 tic-tac-toe（井字棋） 人机对战 C++
难得今天校园活动日，学校放假一天，可以好好做近期计划做但一直没有时间做的事了~比如写博客 【斜眼笑
最近好忙，好多ddl，下周还有三门考试，下下周还有英语pre。。。但是窝真的很想记录一下近期的学习成果，要不然以后可能就忘了。
P.S.这学期的数据结构课真是深得朕心，肥肠喜欢这种用上课学的知识成功解决实际问题的感觉٩(๑❛ᴗ❛๑)۶
C++ 极小极大算法 实现井字棋人机对战
概述：
因为本题的核心是博弈的实现，所以在这里对如何下棋，如何判断游戏是否结束之类的问题不做赘述。
本题中博弈的实现思路如下：
- 设置一个评价机制，为当前局势赋值
设置两个相反的比较机制，比较两个局势的评价值，决定哪个当前方最有利 - 遍历——试放，评价
- 比较，返回最有利位置
解释一下：
- 因为就客观而言，博弈双方面临同一盘棋，所以设置一个评价机制为当前局势赋值。
但对于任一方而言，对对手最有利的情况就是对自己最不利的。所以设置两个相反的比较机制。 - 使用递归，在每一层，遍历所有可以放棋的位置，评估对当前放棋方而言这个位置放棋之后的局势。
- 在同层进行比较，返回对当前放棋方最有利的位置。
具体代码&讲解：
- 头文件 =_=
#include<iostream>
#include<stdio.h>
#include"windows.h"
#define Stack_entry Move
#define maxstack 100
#define success true
#define underflow false
#define overflow false
using namespace std;
- Move类的定义（每一步都是一个Move）
class Move{
public:
Move();
Move(int r,int c);
int row;
int col;
};
Move::Move()
{
row=3;
col=3;
}
Move::Move(int r,int c)
{
row=r;
col=c;
}
- 栈的定义（用来存储所有可行的步（Move））
class Stack{
public:
Stack();
bool empty()const;
bool pop();
bool top(Stack_entry &item);
bool push(const Stack_entry &item);
private:
int count;
Stack_entry entry[maxstack];
};
Stack::Stack()
{
count=0;
}
bool Stack::push(const Stack_entry &item)
{
bool outcome=success;
if(count>=maxstack)
return overflow;
else
entry[count++]=item;
return outcome;
}
bool Stack::pop()
{
bool outcome=success;
if(count==0)
outcome=underflow;
else --count;
return outcome;
}
bool Stack::top(Stack_entry &item)
{
bool outcome=success;
if(count==0)
return underflow;
else
item=entry[count-1];
return outcome;
}
bool Stack::empty()const
{
bool outcome=true;
if(count>0)
outcome=false;
return outcome;
}
- Board类的定义（定义棋盘和对棋盘的操作）
重点是better函数，worst_case函数 和 evaluate函数。
class Board{
public:
Board();
bool done()const;
bool is_ok(Move try_it);
void print()const;
bool better(int value,int old_value)const;
void play(Move try_it);
int worst_case()const;
int evaluate()const;
int legal_moves(Stack &moves)const;
void show_the_board();
private:
int square[3][3];
int moves_done;
int the_winner()const;
};
Board::Board()
/**初始化棋盘，没有棋的地方存的数是0**/
{
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
square[i][j]=0;
moves_done=0;
}
void Board::print()const
/**打印棋盘**/
{
cout<<endl<<" 0 1 2"<<endl;
for(int i=0; i<3; i++)
{
cout<<endl<<i;
for(int j=0; j<3; j++)
{
if(square[i][j]==1)
cout<<" O";
else if(square[i][j]==2)
cout<<" X";
else cout<<" -";
if(j==2) cout<<endl;
}
}
cout<<endl;
}
void Board::play(Move try_it)
/**把“步”放到棋盘上**/
{
square[try_it.row][try_it.col]=moves_done%2+1;
moves_done++;
}
int Board::the_winner()const
/**返回代表赢家的数字（1或2），若胜负未定则返回0**/
{
int i;
for(i=0 ; i<3 ; i++)
if(square[i][0]&&square[i][0]==square[i][1]
&&square[i][0]==square[i][2])
return square[i][0];
for(i=0 ; i<3 ; i++)
if(square[0][i]&&square[0][i]==square[1][i]
&&square[0][i]==square[2][i])
return square[0][i];
if(square[0][0]&&square[0][0]==square[1][1]
&&square[0][0]==square[2][2])
return square[0][0];
if(square[0][2]&&square[0][2]==square[1][1]
&&square[0][2]==square[2][0])
return square[0][2];
return 0;
}
bool Board::done()const
/**判断游戏是否结束**/
{
return (moves_done==9||the_winner()>0);
}
int Board::legal_moves(Stack &moves)const
/**把 所有可行的步 存到 传入的栈 里**/
{
int count=0;
while(!moves.empty())
moves.pop();
for(int i=0; i<3; i++)
for(int j=0; j<3; j++)
if(square[i][j]==0)
{
Move can_play(i,j);
moves.push(can_play);
count++;
}
return count;
}
bool Board::is_ok(Move try_it)
/**判断这一步是否可行**/
{
if(try_it.row>=0&&try_it.row<3&&try_it.col>=0&&try_it.col<3
&&square[try_it.row][try_it.col]==0)
return true;
else return false;
}
int Board::evaluate()const
/**返回一个数，这个数反映了 胜负 和 一共走了多少步，
用于在下面的递归函数里 计算每个可行的步最后结果**/
{
int winner=the_winner();
if(winner==1)
return 10-moves_done;//赢家是1，则返回值为正，数越大对玩家1越有利
else if(winner==2)
return moves_done-10;//赢家是2，则返回值为负，数越小对玩家2越有利
else
return 0;//平局
}
int Board::worst_case()const
/**返回最坏的情况，方便在递归中的比较**/
{
if(moves_done%2) //对玩家2而言
return 10;
else return -10; //对玩家1而言
}
bool Board::better(int value,int old_value)const
/**比较两个值哪个最好**/
{
if(moves_done%2) //对玩家2而言
return value<old_value;
else //对玩家1而言
return value>old_value;
}
放上草图一张以便理解：
5. 非常重要的函数。
负责找出对当前放棋方最有利的一步。
int look_ahead(const Board &game, int depth, Move &recommended)
{
if(game.done()||depth==0)
return game.evaluate();
else
{
Stack moves;
game.legal_moves(moves);
int value;
int best_value=game.worst_case();
while(!moves.empty())
{
Move try_it,reply;
moves.top(try_it);
Board new_game=game;
new_game.play(try_it);
value=look_ahead(new_game,depth-1,reply);
if(game.better(value,best_value))
{
best_value=value;
recommended=try_it;
}
moves.pop();
}
return best_value;
}
}
- 打印相关信息
void instructions()
{
cout<<"欢迎来到井字棋游戏！您将开始与这台电脑博弈。"<<endl
<<"游戏规则很简单，只需输入放置棋子的坐标。"<<endl
<<"温馨提示：O代表您，X代表您的对手。"<<endl<<endl;
}
void print_the_result(int result)
{
if(result>0)
cout<<"\n恭喜您获胜了！\n"<<endl;
else if(result<0)
cout<<"\noops！您输了！\n"<<endl;
else cout<<"\n本局和局。\n"<<endl;
}
- 玩一局棋
int play_game(int intel)
{
Board game;
Move player1_choice;
Move player2_choice;
cout<<"请输入电脑的智商："<<endl;
while(intel<1||intel>9)
{
cout<<"智商应大于等于1，小于等于9。"<<endl;
cin>>intel;
}
system("cls");
game.print();
while(!game.done())
{
cout<<"请输入位置坐标：\n"; //玩家下棋
cin>>player1_choice.row>>player1_choice.col;
while(!game.is_ok(player1_choice))
{
cout<<"这个地方不可以放棋喔。"<<endl;
cin>>player1_choice.row>>player1_choice.col;
}
game.play(player1_choice);
if(game.done())
{
system("cls");
game.print();
break;
}
look_ahead(game , intel , player2_choice); //电脑下棋
game.play(player2_choice);
system("cls");
game.print();
}
print_the_result(game.evaluate());
return game.evaluate();
}
- 主函数。可以下多局棋，并统计胜负情况。
int main(){
int win0=0,win1=0,win2=0;
int winner;
char command;
int intel=0;
instructions();
cout<<"是否开始游戏？输入任意非N字符以开始游戏。"<<endl;
cin>>command;
if(command!='N'&&command!='n')
{
cout<<"请输入电脑的智商："<<endl;
while(intel<1||intel>9)
{
cout<<"智商应大于等于1，小于等于9。"<<endl;
cin>>intel;
}
system("cls");
}
while(command!='N'&&command!='n')
{
winner=play_game(intel);
if(winner==0) win0++;
else if(winner>0) win1++;
else win2++;
cout<<"是否继续游戏？输入任意非N字符以继续。"<<endl;
cin>>command;
system("cls");
}
if((win0+win1+win2)!=0)
cout<<"在与智商为"<<intel<<"的电脑的博弈中："<<endl
<<" 您赢了 "<<win1<<" 次"<<endl
<<"电脑赢了 "<<win2<<" 次"<<endl
<<"双方平局 "<<win0<<" 次"<<endl;
getchar();
return 0;
}
最后想说：
不写不知道，一写吓一跳。
一个看似简单的小程序，竟然要写这么多。
所以，，路漫漫其修远兮，吾将上下而求索。
好了，这就算写完了8，时间过得好快，竟然在不知不觉中错过了饭点，电脑也即将没电orz
但不得不说这感觉真好【逃
——2019.4.18 14:32 于图书馆