1200字范文 > 采用α-β算法实现井字棋游戏

采用α-β算法实现井字棋游戏

时间：2023-08-25 04:33:52

相关推荐

采用α-β算法实现井字棋游戏

题目描述

（1）图形化界面。

（2）随机选取先手后手。

（3）可以人-计算机或计算机-计算机

界面效果

算法

基本思想

Max-Min算法:

采用Max-Min算法进行对抗搜索，Max和Min双方均要对方失败，在井字棋中双方交替走子，根据评估函数的值更新Max和Min，在更新的过程中进行α-β剪枝，加快搜索速度。

评估函数e(s)代表Max状态的启发值，是对Max有利状态的估计。

（1） e(s)大于0时代表对Max有利，e(s)小于0为不利。（2）在五子棋中评估函数e(s) = e(棋盘剩余位置全为Max计算机下的子后连成一条线的个数)-e(全为Min下的其后连成一条线的个数)。（3）如果s 是Max必胜的棋局则返回+∞（4）如果s 是Min必胜的棋局则返回-∞

α-β剪枝算法:

α-β剪枝中，α是Max至今为止的路径上所有选择点的最大值，β是Min中的最小值。它的基本思想是：边生成博弈树边计算评估各节点的倒推值，并且根据评估出的倒推值范围，及时停止扩展那些已无必要再扩展的子节点，即相当于剪去了博弈树上的一些分枝，从而节约了机器开销，提高了搜索效率。具体算法如下：

（1）对于Min节点，如果倒推值的上确界β不大于Min的父节点倒推值的下确界α，即α>=β时，则就不必再扩展该Min 节点的其余子节点了，因为这些节点的估值对 Min 父节点的倒推值已经没有任何影响了。这一过程称为α剪枝。（2）对于Max节点，如果倒推值的下确界α不小于Max的父节点倒推值的上确界β，即α>=β时，则就不必再扩展该Max 节点的其余子节点了，因为这些节点的估值对 Max父节点的倒推值已经没有任何影响了。这一过程称为β剪枝。

需求分析

（1）使用Max-Min算法和α-β剪枝算法实现井字棋游戏。

（2）图形化界面，可以直观显示下棋过程。

（3）可以选取人先手或者计算机先手。

（4）可以人与计算机下棋或者计算机与计算机互博。

模块设计

（1）计算机与计算机模块：调用计算机下棋模块，判断赢家模块和判断平局模块完成功能。

（2）人与计算机模块：调用人类下棋，计算机下棋，赢家判断和平局判断模块完成功能。

（3）人类下棋模块：获取当前鼠标点击的按钮，在对应按钮上显示棋子图片，根据按钮位置修改存储的棋盘信息。

（4）计算机下棋模块：调用Max-Min的α-β剪枝算法，获取搜索到的最有利于计算机的下棋点在相应位置上显示棋子图片。

（5）评估值计算模块：根据上面基本思想介绍的算法计算评估值，即所有空余位置填满计算机棋子后连成一条线的个数减去填满人类棋子后连成一条线的个数。如果电脑赢则返回极大值，人类赢则返回极小值。

（6）Max-Min的α-β剪枝模块：根据计算的评估值进行极大极小算法，不停的交换当前下棋的人进行搜索，在搜索的过程中如果遇到α>=β的情况就进行剪枝。

（7）游戏结束模块：当有一方赢得棋局时，对图形化界面进行重置，存储的棋盘信息也清零。

（8）先手判断模块：当点击计算机先手按钮时，调用计算机下棋模块先进行下棋。

（8）平局判断模块：当有九个格子都被走过且没有赢家时，弹出平局的提示信息对话框。

（9）判断赢家模块：分别对于水平，垂直，对角线进行判断是否有一方连成了一条线。

模块间的调用关系:

人与计算机下棋算法设计

当用户点击棋盘区域进行下棋时，会触发按钮的消息响应函数，消息响应函数会调用人类与计算机下棋的模块，在人类下棋的部分，直接获取点击的按钮然后更改图片为棋子图片就行。而对于计算机下棋就需要调用Max-Min剪枝算法获取搜索到的下棋点进行下棋。下棋的过程中判断是否有输赢和平局的出现，如果出现则游戏结束重新开始。

计算机与计算机算法设计

当用户点击计算机-计算机下棋单选按钮时就会触发消息响应函数修改游戏类型为计算机-计算机类型代表的值，然后点击Next Step按钮界面会一步一步显示计算机之间下棋的过程。在下棋的过程中计算机的下棋点的计算都是基于Max-Min的α-β剪枝算法计算得到的点。

评估值的计算算法

根据上述基本思想的介绍可以得到下面计算的流程图：

Max-Min的α-β剪枝算法设计

文件结构

代码

mainwindow.h

#ifndef MAINWINDOW_H#define MAINWINDOW_H#include <QMainWindow>#include <QPushButton>#include <QMessageBox>#include <QLabel>#include <QRadioButton>#include <iostream>#include <QDebug>using namespace std;const int N = 1e3 + 5;namespace Ui {class MainWindow;}class MainWindow : public QMainWindow{Q_OBJECTpublic:explicit MainWindow(QWidget *parent = 0);~MainWindow();QList<QPushButton *> gridButton; //九个网格按钮QRadioButton *humanVScom, *comVScom, *human_first, *com_first;QRadioButton *level1, *level2, *level3;QLabel *first_player, *level, *boundup, *boundunder;QPushButton *next_step;private:Ui::MainWindow *ui;void HumanAndComputer(QPushButton *button);//人与计算机void ComputerAndComputer(); //计算机与计算机int HumanChess(QPushButton *button); //人类下子int ComputerChess(); //计算机下棋int GetWinPeople(); //获取当前赢的人void ComFirst(); //电脑是否先手bool Tie();//是否平局void Print(); //打印棋盘int MinMaxSolution(int depth, int alpha, int beta); //MinMax算法int CalEvalute();int chess[3][3]; //棋盘int select_type = 0; //选择游戏类型：人-计算机为0，计算机-计算机为1int select_level; // 选择难度等级pair<int, int> best_point; //最优点int cur_depth = 9; //当前搜索深度int cur_player = 1; //当前玩家public slots:void ButtonClick(); //下棋按钮信号void GameOver(); //游戏结束信号void RadioButtonClick();//选择游戏类型void NextbutClick(); //获得电脑下一步};#endif // MAINWINDOW_H

main.cpp

#include "mainwindow.h"#include <QApplication>int main(int argc, char *argv[]){QApplication a(argc, argv);MainWindow w;w.show();return a.exec();}

mainwindow.cpp

#include "mainwindow.h"#include "ui_mainwindow.h"MainWindow::MainWindow(QWidget *parent) :QMainWindow(parent),ui(new Ui::MainWindow){ui->setupUi(this);memset(chess, 0, sizeof(chess)); //棋盘初始化select_type = 0;setWindowTitle("井字棋"); //设置窗体名setFixedSize(1000, 610); //设置窗体大小setWindowIcon(QIcon(":/logo.png")); //设置窗体图标//设置窗体背景为白色QPalette palette(this->palette());palette.setColor(QPalette::Background, Qt::white);this->setPalette(palette);//上下分割线boundup = new QLabel(this);boundup->setStyleSheet("border-image:url(:/bound.png);");boundup->setGeometry(30, 0, 540, 30);boundunder = new QLabel(this);boundunder->setStyleSheet("border-image:url(:/bound.png);");boundunder->setGeometry(30, 570, 540, 30);//设置九个网格图片int x = 0, y = 0, w = 180, h = 180;for(int i = 0; i < 3; ++ i){for(int j = 0; j < 3; ++ j){QPushButton *button = new QPushButton(this);gridButton.push_back(button);x = j * 180 + 30, y = i * 180 + 30;button->setGeometry(x, y, w, h); //设置按钮位置和大小button->setStyleSheet("border-image:url(:/grid.png);"); //设置按钮图片connect(button, SIGNAL(clicked(bool)), this, SLOT(ButtonClick()));//为每个按钮添加响应函数}}QPushButton *restart = new QPushButton(this); //重新开始按钮restart->setGeometry(650, 15, 260, 65);restart->setStyleSheet({"border-image:url(:/restart.png);"});connect(restart, SIGNAL(clicked(bool)), this, SLOT(GameOver()));next_step = new QPushButton(this); //电脑下一步next_step->setGeometry(650, 75, 260, 65);next_step->setStyleSheet({"border-image:url(:/nextstep.png);"});connect(next_step, SIGNAL(clicked(bool)), this, SLOT(NextbutClick()));//游戏类型QLabel *game_type = new QLabel(this); //游戏类型标签game_type->setGeometry(next_step->pos().x(), next_step->pos().y() + 75, 250, 65);game_type->setStyleSheet({"border-image:url(:/selecttype.png);"});//人与计算机humanVScom = new QRadioButton(this);humanVScom->setStyleSheet({"border-image:url(:/humvscom.png);"});humanVScom->setGeometry(game_type->pos().x() - 10, game_type->pos().y() + 60, 145, 65);humanVScom->setChecked(true); //默认人机select_type = 0;connect(humanVScom, SIGNAL(clicked(bool)), this, SLOT(RadioButtonClick()));//计算机与计算机comVScom = new QRadioButton(this);comVScom->setStyleSheet({"border-image:url(:/comvscom.png);"});comVScom->setGeometry(humanVScom->pos().x() + 145, humanVScom->pos().y(), 145, 65);connect(comVScom, SIGNAL(clicked(bool)), this, SLOT(RadioButtonClick()));QButtonGroup * VSgroup = new QButtonGroup(this);VSgroup->addButton(humanVScom);VSgroup->addButton(comVScom);//选择先手first_player = new QLabel(this); //选择先手标签first_player->setGeometry(game_type->pos().x(), game_type->pos().y() + 130, 250, 65);first_player->setStyleSheet({"border-image:url(:/selectfirst.png);"});//人类先手human_first = new QRadioButton(this);human_first->setStyleSheet({"border-image:url(:/humfirst.png);"});human_first->setGeometry(first_player->pos().x() - 10, first_player->pos().y() + 60, 145, 55);connect(human_first, SIGNAL(clicked(bool)), this,SLOT(RadioButtonClick()));human_first->setChecked(true); //默认人先手//计算机先手com_first = new QRadioButton(this);com_first->setStyleSheet({"border-image:url(:/comfirst.png);"});com_first->setGeometry(human_first->pos().x() + 145, human_first->pos().y(), 145, 55);connect(com_first, SIGNAL(clicked(bool)), this,SLOT(RadioButtonClick()));com_first->setChecked(false);QButtonGroup* first_group = new QButtonGroup(this);first_group->addButton(human_first);first_group->addButton(com_first);//困难级别level = new QLabel(this);level->setGeometry(first_player->pos().x(), first_player->pos().y() + 130, 300, 65);level->setStyleSheet({"border-image:url(:/selectlevel.png);"});//简单level1 = new QRadioButton(this);level1->setGeometry(level->pos().x() - 30, level->pos().y() + 60, 120, 55);level1->setStyleSheet({"border-image:url(:/easy.png);"});connect(level1, SIGNAL(clicked(bool)), this, SLOT(RadioButtonClick()));//普通level2 = new QRadioButton(this);level2->setGeometry(level1->pos().x() + 120, level1->pos().y(), 120, 55);level2->setStyleSheet({"border-image:url(:/medium.png);"});connect(level2, SIGNAL(clicked(bool)), this, SLOT(RadioButtonClick()));//困难level3 = new QRadioButton(this);level3->setGeometry(level2->pos().x() + 120, level2->pos().y(), 120, 55);level3->setStyleSheet({"border-image:url(:/hard.png);"});connect(level3, SIGNAL(clicked(bool)), this, SLOT(RadioButtonClick()));level3->setChecked(true); // 默认困难select_level = 0;QButtonGroup * level_group = new QButtonGroup(this);level_group->addButton(level1);level_group->addButton(level2);level_group->addButton(level3);}//棋盘响应函数void MainWindow::ButtonClick(){QPushButton *button = qobject_cast<QPushButton*>(sender());//qDebug()<<"类型:"<<select_type<<endl;HumanAndComputer(button);}void MainWindow::NextbutClick(){ComputerAndComputer();}//计算机与计算机void MainWindow::ComputerAndComputer(){qDebug()<<"计算机与计算机被调用"<<endl;cur_player = 1;if(ComputerChess() == 1) --cur_depth;if(cur_player == GetWinPeople()){QMessageBox::information(this, "井字棋", "Computer One Win");GameOver();return;}else if(Tie()) return;else cur_player = -1;qDebug()<<"计算机与计算机one"<<best_point.first<<","<<best_point.second<<endl;if(ComputerChess() == 1) --cur_depth;if(cur_player == GetWinPeople()){QMessageBox::information(this, "井字棋", "Computer Two Win");GameOver();return;}else if(Tie()) return;else cur_player = 1;qDebug()<<"计算机与计算机Two"<<best_point.first<<","<<best_point.second<<endl;}void MainWindow::RadioButtonClick(){QRadioButton *button = qobject_cast<QRadioButton*>(sender());if(button == humanVScom) select_type = 0;if(button == comVScom) select_type = 1;else if(button == human_first) select_type = 0;else if(button == com_first) select_type = 0;else if(button == level1) select_level = 3;else if(button == level2) select_level = 1;else if(button == level3) select_level = 0;qDebug()<<"类型2："<<select_type<<endl;GameOver();}//人与计算机void MainWindow::HumanAndComputer(QPushButton *button){//人类下棋if(HumanChess(button) == 1) --cur_depth;//搜索深度减一if(cur_player == GetWinPeople()){//当前玩家赢了QMessageBox::information(this, "井字棋", "Congratulations. You Win!");GameOver();return;}else if(Tie()) return; //平局else cur_player = -1; //更改当前玩家为计算机//计算机下棋if(ComputerChess() == 1) --cur_depth;if(cur_player == GetWinPeople()){QMessageBox::information(this, "井字棋", "egrettably . Computer Win");GameOver();return;}else if(Tie()) return;else cur_player = 1; //更改当前玩家为人类}//人类下棋int MainWindow::HumanChess(QPushButton *button){if(button == false) return -1;//下棋失败int i = button->pos().x() / 180;int j = (button->pos().y() - 30) / 180;chess[j][i] = 1; //人类在点(i, j)下了一个子button->setStyleSheet("border-image: url(:/circle.png);");button->setEnabled(false); //只能下一次return 1; //下棋成功}//电脑下棋int MainWindow::ComputerChess(){MinMaxSolution(cur_depth, -N, N); //根据算法获得最优解if(comVScom->isChecked()) chess[best_point.first][best_point.second] = cur_player;else chess[best_point.first][best_point.second] = -1;int point = (best_point.first * 3) + best_point.second;for(int i = 0; i < 9; ++ i){//显示电脑下棋点if(i == point){if(cur_player == -1)gridButton[i]->setStyleSheet("border-image: url(:/fork.png);");else gridButton[i]->setStyleSheet("border-image: url(:/circle.png);");gridButton[i]->setEnabled(false);}}return 1; //下棋成功}//计算评估值int MainWindow::CalEvalute(){int win_people = GetWinPeople();//胜负已分if(win_people == -1 ) return N; // 计算机胜返回最大值if(win_people == 1 ) return -N; // 人类胜返回最小值//胜负未分int value = 0;int new_chess[3][3]; //临时棋盘//计算机for(int i = 0; i < 3; ++ i){for(int j = 0; j < 3; ++ j){if(chess[i][j] == 0) new_chess[i][j] = -1;else new_chess[i][j] = chess[i][j];}}for(int i = 0; i < 3; ++ i) //对于水平方向value = value - (new_chess[i][0] + new_chess[i][1] + new_chess[i][2])/3;for(int i = 0; i < 3; ++ i) //对于垂直方向value = value - (new_chess[0][i] + new_chess[1][i] + new_chess[2][i])/3;value = value - (new_chess[0][0] + new_chess[1][1] + new_chess[2][2])/3;//主对角线value = value - (new_chess[2][0] + new_chess[1][1] + new_chess[0][2])/3;//副对角线//人类for(int i = 0; i < 3; ++ i){for(int j = 0; j < 3; ++ j){if(chess[i][j] == 0) new_chess[i][j] = 1;else new_chess[i][j] = chess[i][j];}}for(int i = 0; i < 3; ++ i) //对于水平方向value = value - (new_chess[i][0] + new_chess[i][1] + new_chess[i][2])/3;for(int i = 0; i < 3; ++ i) //对于垂直方向value = value - (new_chess[0][i] + new_chess[1][i] + new_chess[2][i])/3;value = value - (new_chess[0][0] + new_chess[1][1] + new_chess[2][2])/3;//主对角线value = value - (new_chess[2][0] + new_chess[1][1] + new_chess[0][2])/3;//副对角线return value;}int MainWindow::MinMaxSolution(int depth, int alpha, int beta){int cur_value = 0, best_value = 0, cnt = 0;pair<int, int> location[10];int win_people = GetWinPeople();if(win_people == -1 || win_people == 1 ||depth == 0) {// qDebug() << CalEvalute()<<endl;return CalEvalute();}//深度未耗尽，给定初始值if(cur_player == -1) best_value = -N;else if(cur_player == 1) best_value = N;//获取棋盘上剩余的位置for(int i = 0; i < 3; ++ i){for(int j = 0; j < 3; ++ j){if(chess[i][j] == 0){//qDebug()<<i<<","<<j<<endl;location[cnt].first = i;location[cnt++].second = j;}}}cnt -= select_level; //困难级别// qDebug()<<select_level<<'\n';if(cnt < 1) {best_point = location[0];//qDebug()<<"0: "<<best_value<<"("<<location[0].first<<","<<location[0].second<<endl;return best_value;}for(int i = 0; i < cnt; ++ i){pair<int, int> cur_pos = location[i];int x = cur_pos.first, y = cur_pos.second;chess[x][y] = cur_player; //当前点下一个棋cur_player = (cur_player == 1) ? -1 : 1;cur_value = MinMaxSolution(depth - 1, alpha, beta); //向下递归chess[x][y] = 0; //取消下棋cur_player = (cur_player == 1) ? -1 : 1;if(cur_player == -1){// 当前玩家是Max节点if(cur_value > best_value){best_value = cur_value;if(depth == cur_depth) best_point = cur_pos;alpha = best_value;}if(beta <= alpha) return beta; // Max中上界小于下界返回较小值}else if(cur_player == 1){// 当前是Min节点if(cur_value < best_value){best_value = cur_value;if(depth == cur_depth) best_point = cur_pos;beta = best_value;}if(beta <= alpha) return alpha; // Min中上界小于下界返回较大值}}return best_value;}void MainWindow::GameOver() //游戏结束{for(int i = 0; i < 9; ++ i){gridButton[i]->setStyleSheet("border-image: url(:/grid.png);");gridButton[i]->setEnabled(true);}//棋盘重置for(int i = 0; i < 3; ++ i){for(int j = 0; j < 3; ++ j){chess[i][j] = 0;}}cur_depth = 9;ComFirst();}//电脑先手void MainWindow::ComFirst(){if(humanVScom->isChecked()){if(com_first->isChecked()){//人机对战模式且电脑先手ComputerChess();--cur_depth;cur_player = 1;}else cur_player = -1;}}bool MainWindow::Tie() //平局{int cnt = 0; //有多少个格子走过for(int i = 0; i < 3; ++ i){for(int j = 0; j < 3; ++ j){if(chess[i][j] != 0){++cnt;}}}if(cnt == 9){//9个格子都走过QMessageBox::information(this, tr("井字棋"), tr("Draw！"), QMessageBox::Ok);GameOver(); //游戏结束return true;}return false;}int MainWindow::GetWinPeople() //判断输赢{int sum = 0;for(int i = 0; i < 3; ++ i){//水平方向sum = chess[i][0] +chess[i][1] + chess[i][2];if( sum == 3) return 1;else if(sum == -3) return -1;}for(int i = 0; i < 3; ++ i){//垂直方向sum = chess[0][i] + chess[1][i] + chess[2][i];if(sum == 3) return 1;else if(sum == -3) return -1;}int psum = chess[0][0] + chess[1][1] + chess[2][2];//正对角线int csum = chess[2][0] + chess[1][1] + chess[0][2];//副对角线if(psum == 3 || csum == 3) return 1;else if(psum == -3 || csum == -3) return -1;return 0; //未决胜负}MainWindow::~MainWindow(){delete ui;}