精华内容
下载资源
问答
  • Minimax算法——井字棋

    2021-09-22 18:48:01
    Minimax算法——井字棋 前言 本文将介绍Minimax算法以及α-β剪枝算法并实现井字棋游戏 介绍 Minimax算法

    Minimax算法——井字棋

    前言

    本文将介绍Minimax算法以及α-β剪枝算法并实现井字棋游戏

    介绍

    Minimax算法常用于双人对战棋牌类游戏中,该算法需满足零和博弈。

    Minimax算法

    在双人游戏中,我们将模拟双方可能的操作,并且对于当前局面进行评分,在我方回合,即选择评分最高的局面,在对方回合,即选择评分最低的局面,以此类推。这就是Minimax算法的基本过程。
    在这里插入图片描述

    from : http://blog.codinglabs.org/articles/2048-ai-analysis.html

    此为模拟对弈过程的流程图。

    α-β剪枝算法

    在这里插入图片描述

    以上图为例,在此流程中,从下往上,正方形→三角形为min过程,三角形→正方形为max过程。在第一个三角形已经确定为20的情况下,开始搜索第二个三角形,若确定了第一个正方形为10以后,就可结束第二个三角形的后继搜索,即不需要知道后面两个正方形为100,因为在10已经确定的时候,第二个三角形肯定小于等于10,而在max过程中,一定不会取10,因为已经有20比10大了,这就是α-β剪枝算法的原理。以上图为例,如果全部遍历,则需要计算六个局面的分数,如果使用α-β剪枝算法,则只需计算四个局面的分数。

    井字棋游戏

    展开全文
  • 采用α-β算法实现井字棋游戏

    千次阅读 2020-11-12 21:25:16
    题目描述 (1)图形化界面。 (2)随机选取先手后手。 (3)可以人-计算机或计算机-计算机 算法 α是MAX至今为止的路径上所有选择点中发现的最好选择的值,即是最大值。 如果v比α差,MAX会避免它,即发生剪枝。 ...

    题目描述

    (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_OBJECT
    
    public:
        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,计算机-计算机为1
        int 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;
    }
    

    运行效果

    hard困难模式

    在此模式下,人类与计算机基本上总是平手,计算机几乎不会失误,当平手时系统弹出Draw信息提示对话框提示用户。
    在这里插入图片描述

    Easy简单模式

    在此模式下,赢得游戏变得非常容易,几乎每次必赢,平局的局面很少
    在这里插入图片描述

    计算机与计算机互搏

    当选择计算机与计算机下棋时,往往总是平局,并且它们每次下棋的落子点都一样。因为它们都是使用极大极小的剪枝算法下棋所以每次获取的都是最有利于自己的点就会不断的平局。
    在这里插入图片描述

    完整项目下载

    CSDN下载:(https://download.csdn.net/download/qq_45364953/15172911)

    展开全文
  • Q-learning 是强化学习中的一种常见的算法,近年来由于深度学习革命而取得了很大的成功。本教程不会解释什么是深度 Q-learning,但我们将通过 Q-learning 算法来使得代理学习如何玩 tic-tac-toe 游戏。尽管它很简单...

    Q-learning 是强化学习中的一种常见的算法,近年来由于深度学习革命而取得了很大的成功。本教程不会解释什么是深度 Q-learning,但我们将通过 Q-learning 算法来使得代理学习如何玩 tic-tac-toe 游戏。尽管它很简单,但我们将看到它能产生非常好的效果。

    要理解本教程,不必有任何关于强化学习的知识,但最好有一定的微积分和线性代数基础。首先,我们将通过一些必要的背景知识来快速了解强化学习,然后我们将介绍 Q-learning 算法,最后我们将介绍如何通过它来使得一个代理学会玩 tic-tac-toe。

    强化学习简介

    强化学习是指代理在不同状态的环境中,根据某种奖励函数来优化其行为的一门学科。在本教程中,环境是 tic-tac-toe 游戏,它有明确定义的动作,代理必须决定选择哪些动作才能赢得游戏。此外,代理人赢得游戏将获得一定奖励,这鼓励它在游戏中学习更好的策略。

    强化学习的一个常见框架是(有限)马尔可夫决策过程(MDP, Markov Decision Process)。它帮助我们定义一组动作和状态,代理基于这些动作和状态进行决策。

    MDP 通常包括有:

    一组有限的动作 A(在游戏面板上所有可以放置标记的位置)一组有限的状态 S(游戏面板上的所有可能情形)一种奖励函数 R(s,a)转移函数 T(s,a,s')转换函数给出了在执行动作 a 时从状态 s 移动到 s' 的概率。当我们不确定动作是否总是产生期望结果时,转移函数十分必要。但是需要注意的是,对于 tic-tac-toe 游戏,我们确切地知道每个动作会做什么,所以我们不会使用转移函数。

    d5ff9ad28473bf3a2265ce2b3f9955db.png


    在本例中,当前玩家可以执行六个可能的操作

    MDP框架帮助我们将问题形式化,这样我们就可以根据当前状态确定哪些操作将在游戏期间使代理的总回报最大化。本教程中奖励函数 R(s,a) 将非常简单:

    如果代理在状态 s 执行一个操作 ,最终赢得游戏,那么 R(s,)=1.如果代理在状态 s 执行一个操作 ,最终输了游戏,那么 R(s,)=-1.否则,R(s,)=0.在强化学习中,我们通常找到一个最优策略,代理通过该策略决定选择哪些动作。本教程中我们使用 Q-learning,简单地将策略表示为当代理处于s状态时执行动作 a 使函数 Q(s,a) 最大化:

    68e07d7050e019d8c3bae8b0a8663869.png

    Q-learning 中的状态更新

    Q(s,a) 即代理在 s 状态下选择动作 a,则在游戏最后给出对应的奖励或惩罚。由于代理希望将其报酬最大化,因此它会选择使 Q 最大化的动作。

    76e975e6476ee1cdc665c5274d651795.png


    在场景中,首先计算当前玩家X所有动作的Q值,然后选择Q值最大的动作

    要计算 Q(s,a),代理必须探索所有可能的状态和动作,同时从奖励函数 R(s,a) 获得反馈。在 tic-tac-toe 游戏中,我们通过让代理与对手进行多场比赛来迭代更新 Q(s,a),用于更新 Q 的方程如下:

    b2efd04de64f514d9e16c6212349c2de.png

    在当前状态 s 下执行动作 a考虑执行动作后的所有状态,计算其中的最大 Q 值。是执行动作 a 之后的新状态, 是下一个状态中的最佳动作学习率 α 决定我们覆盖旧值的程度,本例中将使用 α=0.1折现因子 γ 决定了在当前时间步 t 中,未来的奖励应加权多少。通常选择 γ=0.9Q-learning 算法实现

    为了得到一个经过充分训练的代理,我们需要获得 Q(s,a) 的值,这将通过让两个代理互相比赛来完成。首先,引入一个概率 ε,即每个代理选择一个随机动作,否则,它将根据 Q(s,a) 选择最佳动作。这样,我们就保证了学习的平衡,使代理有时探索新的行为,而其他时候则利用代理已经学习到的信息来执行动作。

    训练阶段可以通过以下伪代码进行描述:

    Initialise: Q(s,a) = 0, starting state s, starting player P, iterations Nfor t = 0 : N With probability ε : P picks random action a Else, pick action a that maximise Q(s,a) Observe new state and reward R(s,a) If current player is our agent, update Q(s,a) = (1-α)Q(s,a) + α[R(s,a) + γ*max(Q(,))] s = Switch turn, P = the other player

    值得注意的是,迭代次数 N 必须相对较大,本例中进行了大约 500000 次迭代。此外,Q(s,a) 可以通过 Python dict 的数据格式进行存储;如果我们将 (s,a) 表示为整数,则可以通过二维数组的数据格式进行存储。最后,可以随时间改变概率 ε,以强调在早期迭代中更多的随机探索,从而加快学习速度。

    在用上述算法训练代理之后,可以保存 Q(s,a) 并在想要进行比赛时加载它。然后,代理只需遵循最优策略,选择使 Q(s,a) 最大化的动作来赢得比赛。虽然由于 tic-tac-toe 游戏并不复杂,代理并没有获得高级智能,但是尝试这个方法可以学习如何实现 Q-learning 并了解它是如何工作的。

    结语

    本文首先介绍了马尔可夫决策过程以及如何在强化学习中应用它。然后使用状态、行动、奖励函数来对 tic-tac-toe 游戏进行建模。除此之外,我们还定义了函数 Q(s,a),该函数通过在状态 s 中选择动作 a 来量化预期的奖励,并通过重复玩游戏来计算 Q(s,a)。

    作者:Rickard Karlsson

    deephub翻译组:oliver lee

    本文github代码: RickardKarl/bill-the-bot

    展开全文
  • 用python井字棋

    2020-11-30 05:45:59
    上篇文章 python 井字棋-文字版(上)电脑端下棋策略是随机的,有哪些位置可下棋,就随机选择一个位置; 实际中是不存这么傻的对手的,赋予电脑一个正常的智商还是很有必要的:至少当对手下一步要赢了,我们应该马上...

    o55g08d9dv.jpg广告关闭

    腾讯云11.11云上盛惠 ,精选热门产品助力上云,云服务器首年88元起,买的越多返的越多,最高返5000元!

    ka57pchhef.png

    上篇文章 python 井字棋-文字版(上)电脑端下棋策略是随机的,有哪些位置可下棋,就随机选择一个位置; 实际中是不存这么傻的对手的,赋予电脑一个正常的智商还是很有必要的:至少当对手下一步要赢了,我们应该马上堵住哪个位置; 如果电脑自己能赢了,那就应该下能够赢的位置; 如果双方都赢不了,那就找一个比较好...

    python井字棋游戏虽然看上去非常简陋,但是却非常值得学习。 先看怎么玩的:1. 显示规则说明,这里写上游戏玩法说明,以及如何判断胜负等等。 2.决定谁先走。 ?3. 打印棋盘。 ?4. 玩家行棋,电脑自动行棋(这里没有采用算法计算,只是自动随机下空的位置)? 5.判断结果,祝贺玩家。 ? ----上面是玩的过程,用代码该...

    4v3vukm97n.jpeg

    本文实例为大家分享了python实现井字棋小游戏的具体代码,供大家参考,具体内容如下import os def print_board(board):print(board + | + board + | + board) print(-+-+-)print(board + | + board + | + board) print(-+-+-)print(board + | + board + | + board) def main():init_board = { tl: , tm: , tr: , ml: ...

    计算机的算法--寻找最佳落子位置首先简单的将棋盘划分为三个部分——中心(1),角(4),边(4)。 中心虽然只有一个但却不是最重要的,三个部分落子的优先顺序依次为:角、中心、边。 因此,井字棋的计算机算法计算最佳落子位置的顺序如下:1 直接落子获胜2 阻止玩家获胜3 在角上落子4 在中心落子5在边上落子游戏...

    本文为大家分享了python实现井字棋小游戏,供大家参考,具体内容如下周五晚上上了python的选修课,本来以为老师是从python的基础语法开始的,没想到是从turtle画图开始,正好补上了我以前一些不懂的地方,有人讲一下还是比啃书好一点。 之前从图书馆借了一本python游戏编程,看了前面几章后就没怎么看了,晚上突然想...

    横、竖、斜三个方向; 游戏的代码:#! usrbinenv python3# -*- coding:utf-8 -*-ucreated on 2019年4月13日 @author:wuluo__author__ = wuluo__version__ = 1. 0. 0__company__ = u重庆交大__updated__ = 2019-04-13 # 创建井字棋的程序definitboard():global board # 调用全局的board board = * 3 print(井字棋:) ...

    用python实现的一个井字棋游戏,供大家参考,具体内容如下#tic-tac-toe 井字棋游戏#全局常量x=xo=oempty= #询问是否继续defask_yes_no(question):response=none; while response not in(y,n):response=input(question).lower()return response#输入位置数字defask_number(question ,low,high):response=nonewhile ...

    start:开始上代码了,希望有更好的逻辑思维来写,自己也是用最笨拙的思路去写的,如果有可以优化的代码请各位大神指教#! userbinpython# -*- coding:utf-8 -*-import osimport sys#棋盘模块def model(dictionary,serial=false):if serial:print(-(初版)井字棋游戏,输入棋号进行对战,print(对应棋号为第一行:a1-a2-a3...

    6gm4l2od5h.png

    empty 表示棋位为空; tie 表示平局; num_squares 表示有 9 个棋位 x = x o = o empty = tie = tie num_squares =92、定义调用到的函数def ask_yes_no(question):问一个是或否的问题,用 y 或 n 回答。 response = nonewhile response not in (y, n):response = input(question).lower()return responsedefask...

    问题描述a 和 b 在一个 3 x 3 的网格上玩井字棋。 井字棋游戏的规则如下:玩家轮流将棋子放在空方格 ( ) 上。 第一个玩家 a 总是用 x 作为棋子,而第二个玩家 b 总是用 o 作为棋子。 x 和 o 只能放在空方格中,而不能放在已经被占用的方格上。 只要有 3 个相同的(非空)棋子排成一条直线(行、列、对角线)时,游戏...

    p = the other player值得注意的是,迭代次数 n 必须相对较大,本例中进行了大约 500000 次迭代。 此外,q(s,a) 可以通过 python dict 的数据格式进行存储; 如果我们将 (s,a) 表示为整数,则可以通过二维数组的数据格式进行存储。 最后,可以随时间改变概率 ε,以强调在早期迭代中更多的随机探索,从而加快学习速度 ...

    lpvwe9rzxp.jpeg

    其实,在python有一个很经典的关于对数据字典的实战项目,便是我们曾经最熟悉不过的井字棋游戏,同时用二十行代码就可以将其实现! 它对数据字典进行了巧妙而又深刻的运用,因此很多python教程中都将井字棋游戏作为对数据字典的实战项目之一。 所以今天大灰狼就来和小伙伴分享一下,运用数据字典构造井字棋盘的实战...

    所以今天就来写一个最简单棋类游戏:tic tac toe,又叫井字棋。 本篇将实现游戏框架,让你可以和电脑对战,但提升电脑的“智能”会在下一篇中细说。 另外,文末会介绍一个 github 上的 python 版 alphago 项目。 大致说下井字棋的规则:棋盘为 3*3 共 9 格,类似汉字“井”; 一方为 o,一方为 x,轮流落子; 任一方...

    f2ahc611zx.png

    单列表,嵌套列表或者其它的都可以,之前的井字棋由于网格少,采用的是单列表,这里虽然也可以,但是采用嵌套列表可以减少计算; 2.如何想要以那种格式...欢迎关注公众微信号:叶子陪你玩编程 分享自己的python学习之路...最后采用的是在格子里面下棋。 ...

    xgl1l2xz3n.png

    棋类游戏最基本的 ai 方法就是给棋盘上每个位置的优劣程度打分,然后选择的最高分的位置来走。 打分算法的好坏,就决定了这个 ai 的“智能”程度。 要给我们的井字棋 ai 制定打分方法,首先就得分析一下井字棋本身的对局策略。 好在这个游戏的规则很简单,总结下来基本就是:尽可能让自己走成 3 个在自己走成 3 个...

    main()综合案例3:井字棋游戏import os def print_board(board):print(board + | + board + | + board) print(-+-+-)print(board + | + board + | + board) print(-+-+-)print(board + | + board + | + board) def main():init_board = { tl: , tm: , tr: , ml: , mm: , mr: , bl: , bm: , br:} begin = true while ...

    m5qn2uzqqs.jpeg

    fibonacci数列 杨辉三角综合案例 - 双色球选号 井字棋day08 -面向对象编程基础类和对象 - 什么是类 什么是对象 面向对象其他相关概念定义类 -基本结构 属性和方法 构造器 析构器 __str__方法使用对象 - 创建对象给对象发消息面向对象的四大支柱 - 抽象 封装 继承 多态基础练习 - 定义学生类定义时钟类 定义图形类 ...

    第7天,介绍字符串和常用数据结构知识点,包括字符串、列表、元组 、集合、字典等知识点。 要能用这些知识带你完成杨辉三角、双色球选号、井字棋等经典案例。 第8天,面向对象编程基础,介绍类和对象的以及基础练习:定义学生类,定义时钟类,定义图形类,定义汽车类。 第9天,面向对象进阶,学习属性、类中的方法...

    cbxc3oa57g.jpeg

    要能用这些知识带你完成杨辉三角、双色球选号、井字棋等经典案例。 第 8 天,面向对象编程基础,介绍类和对象的以及基础练习:定义学生类,定义时钟类...说明:我最近整理了一份python基础系列文章,如果你是python新手或者你的python基础知识点忘记了,可以看看今日第三条文章。 作为目前最火也是最实用的...

    第 7 天,介绍字符串和常用数据结构知识点,包括字符串、列表、元组 、集合、字典等知识点。 要能用这些知识带你完成杨辉三角、双色球选号、井字棋等经典案例。 第 8 天,面向对象编程基础,介绍类和对象的以及基础练习:定义学生类,定义时钟类,定义图形类,定义汽车类。 第 9 天,面向对象进阶,学习属性、类中的...

    展开全文
  • 极大极小算法完成井字棋游戏2.α-β剪枝四、 结果、反思与分析1.极大极小算法运行结果、发现的问题与解决方式2.α-β剪枝运行结果、发现的问题与解决方式3.极大极小算法和α-β剪枝的比较总结 一、 实验内容 实验...
  • 比如在井字棋中,总利益为0,以玩家A的视角看,A取得胜利获得的利益是1,则B在A获得胜利的情况下获得的利益则为-1,反之亦然,双方的利益总和为0。 棋类游戏是双方交替下棋的游戏,每一次落子都代表落子的
  • 井字棋是大家所熟知的一个小游戏,虽然简单,但其中包含了一些编程的基本技巧和基本算法,在 E c l i p s e环境下用J a v a ̄- - g编 -写一个可以人人、人机对弈的井字棋游戏。关键词: J a v a语言;井字棋;游戏编...
  • C语言—井字棋的实现

    千次阅读 2021-10-21 14:36:20
    首先,我们需要一个简单的井字棋棋盘。 #define COL 3 #define ROW 3 //利用宏定义来定义棋盘的大小,因为井字棋需要一个3*3的棋盘,为了避免魔幻数字(在后续代码中出现,不能很直观的看出是长还是宽)的出现,...
  • Java实现井字棋AI

    2021-03-17 23:19:51
    井字棋,英文名叫Tic-Tac-Toe,是一种在3*3格子上进行的连珠游戏,和五子棋类似,由于棋盘一般不画边框,格线排成井字故得名。游戏需要的工具仅为纸和笔,然后由分别代表O和X的两个游戏者轮流在格子里留下标记...
  • 欢迎点击「算法与编程之美」↑关注我们!本文首发于微信公众号:"算法与编程之美",欢迎关注,及时了解更多此系列文章。问题描述A 和 B 在一个 3 x 3 的网格上玩井字棋...
  • 问题描述 采用α-β剪枝算法实现井字棋游戏 图形化界面 随机选取先手后手 可以人-计算机或计算机-计算机 界面展示 源代码 完整项目下载点这里QwQ
  • 说明用python实现了井字棋,整个框架是本人自己构思的,自认为比较满意。另外,90%+的代码也是本人逐字逐句敲的。minimax算法还没完全理解,所以参考了这里的代码,并作了修改。特点可以选择人人、人机、机人、机机...
  • 编程题——井字棋

    千次阅读 2019-06-03 21:21:26
    对于一个给定的井字棋棋盘,请设计一个高效算法判断当前玩家是否获胜。 给定一个二维数组board,代表当前棋盘,其中元素为1的代表是当前玩家的棋子,为0表示没有棋子,为-1代表是对方玩家的棋子。 本代码适用于所有...
  • 题目描述设计一个在n×n网格上两个玩家之间玩的Tic-tac-toe游戏。您可以假定以下规则:1.一个移动被保证是有效的,并且被放置在一个空块上。2.一旦达到获胜条件,就不再允许移动。3.成功地在水平、垂直或对角线行中...
  • 基于极大极小算法和alpha-beta剪枝实现AI井字棋

    万次阅读 多人点赞 2016-11-01 20:54:50
    说一下实现这个AI井字棋的思路:简单的来说就是计算机希望估值函数值最大,而下棋人希望这个估值最小,因此在计算机决策是就用递归的向前看,这里的递归其实蛮不好理解的,但是可以宏观的去理解。下面是代码的构成:...
  • 但是环境类中的4个函数都是空的,本文将描述怎么实现那4个函数,实现一个完整的井字棋游戏的环境。游戏规则:两个玩家在3x3的棋盘上,一方执X,一方执O。哪方先下的连续3个子(不管在对角,竖直还是水平方向)为胜。...
  • 在写这个2048的过程中,我考虑是否可以在其中加入一个 AI 算法来自动进行游戏,于是我找到了这篇文章:2048-AI程序算法分析,文中介绍了 minimax 算法和 alpha-beta 剪枝算法。于是我决定先学习下这两种算法,并以此...
  • Java之井字棋游戏实现

    千次阅读 2017-07-20 23:07:07
    你的程序先要读入一个整数n,范围是[3,100],这表示井字棋棋盘的边长。比如n=3就表示是一个3x3的棋盘。然后,要读入n行,每行n个数字,每个数字是1或0,依次表示[0,0]到[n-1,n-1]位置上的棋子。1表示X,0表示O(大写...
  • 对于一个给定的井字棋棋盘,请设计一个高效算法判断当前玩家是否获胜。 给定一个二维数组board,代表当前棋盘,其中元素为1的代表是当前玩家的棋子,为0表示没有棋子,为-1代表是对方玩家的棋子。 ...
  • 井字棋

    千次阅读 2019-05-31 23:35:13
    对于一个给定的井字棋棋盘,请设计一个高效算法判断当前玩家是否获胜。 给定一个二维数组board,代表当前棋盘,其中元素为1的代表是当前玩家的棋子,为0表示没有棋子,为-1代表是对方玩家的棋子。 测试样例: [[1,...
  • 在写这个2048的过程中,我考虑是否可以在其中加入一个 AI 算法来自动进行游戏,于是我找到了这篇文章:2048-AI程序算法分析,文中介绍了 minimax 算法和 alpha-beta 剪枝算法。于是我决定先学习下这两种算法,并以此...
  • 强化学习井字棋游戏

    千次阅读 2020-01-14 17:09:46
    强化学习井字棋游戏实现   这是一个简单的强化学习例子Tic-Tac-Toe。在一个3×3的九宫格里,两个人人论留下,直到有个人的棋子满足三个一横一竖或者一斜,赢得比赛游戏结束,或者九宫格填满也没有人赢,则和棋。 ...
  • 井字棋决策的Cpp描述

    2019-09-14 22:51:30
    井字棋决策的Cpp描述 本文在vs17环境下对井字棋的决策算法做出了部分解释 博弈双方的棋权,运用了布尔型变量 通过对布尔型变量的次序互换实现双方函数的交替运行 char ww, X, O; int qz; bool h; static ...
  • 返回true当且仅当在一个合法的井字棋游戏当中可能到达当前这种棋盘情况。 board是一个 3 x 3 的数组, 包含字符' ', 'X', 和'O'。字符 ’ '意味着这一格是空的。 以下是井字棋的游戏规则: 玩家需要轮流在空格上...
  • 对于一个给定的井字棋棋盘,请设计一个高效算法判断当前玩家是否获胜。 给定一个二维数组board,代表当前棋盘,其中元素为1的代表是当前玩家的棋子,为0表示没有棋子,为-1代表是对方玩家的棋子。 测试样例: [[1,0,...
  • 对于一个给定的井字棋棋盘,请设计一个高效算法判断当前玩家是否获胜。给定一个二维数组 board ,代表当前棋盘,其中元素为 1 的代表是当前玩家的棋子,为 0 表示没有棋子,为 -1 代表是对方玩家的棋子 ...
  • 【编程题】井字棋(Java实现)

    千次阅读 2019-07-22 17:37:24
    【编程题】井字棋(Java实现) 题目来源 程序员面试金典 https://www.nowcoder.com/practice/e1bb714eb9924188a0d5a6df2216a3d1?tpId=8&tqId=11055&rp=4&ru=/ta/cracking-the-coding-interview&qru=...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 637
精华内容 254
关键字:

井字棋算法描述