共有回帖数 0 个
-
按照之前发帖的格式，应该先解释一下。不过……这个游戏不用再多解释了吧，就是三子连成一线就获胜。
算法是 Minimax，假设双方都会选择最优方案，那么轮到计算机下棋时，对当前所有空的方格进行估值，选择最大的。进行估值时，要站在对方一方进行考虑。对方如果选择最优方案的话，会选择一个使计算机优势最小的方格。下面给出的程序使用的算法实际上是原始的 Minimax 的一种改进。
#include algorithm
#include cstdio
using namespace std;
const int EMPTY = 0, PLAYER = 1;
const int DRAW = 0, WIN = 1;
int a[3][3], cnt;
bool Check(int side, int x, int y)
{ //判断是否有一方获胜
return a[y][0] == side && a[y][1] == side && a[y][2] == side
|| a[0][x] == side && a[1][x] == side && a[2][x] == side
|| a[0][0] == side && a[1][1] == side && a[2][2] == side
|| a[0][2] == side && a[1][1] == side && a[2][0] == side;
}
int SearchMove(int side, int alpha, int beta, int &pos, int prev_pos)
{ //搜索最佳着法
if (prev_pos != -1 && Check(3-side, prev_pos%3, prev_pos/3)) return -WIN;
if (cnt == 9) return DRAW;
int b[9], res, tmp;
for (int i = 0; i 9; ++i)
b = i;
random_shuffle(b, b+9);
for (int i = 0; i 9 && alpha beta; ++i)
{
if (a[b/3][b%3]) continue;
a[b/3][b%3] = side; ++cnt;
res = -SearchMove(3-side, -beta, -alpha, tmp, b);
if (res alpha)
{
alpha = res;
pos = b;
}
a[b/3][b%3] = EMPTY; --cnt;
}
return alpha;
}
void Show()
{ //显示棋盘
for (int i = 0; i 3; ++i, putchar('n'))
for (int j = 0; j 3; ++j)
printf(a[j] == EMPTY ? "┼" : a[j] == PLAYER ? "●" : "×");
putchar('n');
}
bool PlayerTurn()
{ //选手的回合
int x, y;
Show();
do scanf("%d%d", &x, &y);
while (x 0 || x = 3 || y 0 || y = 3 || a[y][x]);
a[y][x] = 1; ++cnt;
putchar('n');
Show();
if (Check(1, x, y))
{
puts("You win!n");
return true;
}
return false;
}
bool ComputerTurn()
{ //计算机的回合
int pos;
SearchMove(2, -WIN, WIN, pos, -1);
a[pos/3][pos%3] = 2; ++cnt;
Show();
if (Check(2, pos%3, pos/3))
{
puts("You lose!n");
return true;
}
return false;
}
int main()
{
int option;
for(;;)
{
//显示菜单
puts("0 You firstn1 Computer firstn2 Exitn");
do scanf("%d", &option);
while (option 0 || option = 3);
if (option == 2) break;
putchar('n');
//清空棋盘
for (int i = 0; i 3; ++i)
for (int j = 0; j 3; ++j)
a[j] = EMPTY;
cnt = 0;
//游戏过程
if (!option)
{
for(;;)
{
if (PlayerTurn()) break;
if (cnt == 9)
{
puts("Draw!n");
break;
}
if (ComputerTurn()) break;
}
}
else for(;;)
{
if (ComputerTurn()) break;
if (cnt == 9)
{
puts("Draw!n");
break;
}
if (PlayerTurn()) break;
}
}
return 0;
}
楼主 2016-06-09 09:19 回复
Copyright © 2010~2015 直线网 版权所有,All Rights Reserved.沪ICP备10039589号
意见反馈 |
关于直线 |
版权声明 |
会员须知
