精华内容
下载资源
问答
  • 极大值极小值搜索设计五子棋

    千次阅读 2018-07-26 11:49:30
    极大值极小值搜索设计五子棋 源代码可在这里下载 摘要: 设计一个五子棋对战AI,使用极大值极小值搜索,并使用α-β剪枝减少复杂度。采用启发式函数对整个棋局形式进行评估,并作为极大值极小值搜索的依据。 一...

    极大值极小值搜索设计五子棋

    源代码可在这里下载

    摘要:

    设计一个五子棋对战AI,使用极大值极小值搜索,并使用α-β剪枝减少复杂度。采用启发式函数对整个棋局形式进行评估,并作为极大值极小值搜索的依据。

    一、导言

    1.1 问题描述:

    本次实验要求设计一个五子棋的AI,要求能与人类对战,并具有较好的用户交互界面。

    1.2 背景介绍:

    五子棋是世界智力运动会竞技项目之一,是一种两人对弈的纯策略型棋类游戏,是世界智力运动会竞技项目之一,通常双方分别使用黑白两色的棋子,下在棋盘直线与横线的交叉点上,先形成5子连线者获胜。棋盘由横纵各15条等距离,垂直交叉的平行线构成,在棋盘上,横纵线交叉形成了225个交叉点为对弈时的落子点。

    尽管五子棋先后于1992年、2001年被计算机证明原始无禁手、原始有禁手规则下先手必胜,在五子棋专业比赛中采用现代开局规则(如基于无禁手的两次交换规则(Swap-2),基于有禁手的索索夫-8规则(Soosorv-8))远比原始规则复杂,并未被终结。然而,相比电脑象棋,电脑五子棋的发展是缓慢的。顶级五子棋程序虽长于局部计算,但缺乏大局观,因此很多五子棋专家相信目前的五子棋程序依旧无法超越最强的人类棋手。

    1.3 使用方法:

    极大极小搜索算法、α-β剪枝算法。

    1.4 方法介绍:

    极大极小策略是考虑双方对弈若干步之后,从可能的步中选一步相对好的步法来走,即在有限的搜索深度范围内进行求解。

    定义一个静态估价函数f,以便对棋局的态势做出优劣评估。

    规定:
    max和min代表对弈双方;
    p代表一个棋局(即一个状态);
    有利于MAX的态势,f(p)取正值;
    有利于MIN的态势,f(p)取负值;
    态势均衡,f(p)取零值;

    1.5 MINMAX的基本思想:

    • 当轮到MIN走步时,MAX应该考虑最坏的情况(即f(p)取极小值)
    • 当轮到MAX走步时,MAX应该考虑最好的情况(即f(p)取极大值)
    • 相应于两位棋手的对抗策略,交替使用上面两种方法传递倒推值。

    α-β剪枝算法是采用有界深度优先策略进行搜索,当生成节点达到规定的深度时,就立即进行静态估计,而一旦某个非端节点有条件确定倒推值时,就立即赋值。

    定义:

    • α值:有或后继的节点,取当前子节点中的最大倒推值为其下界,称为α值。节点倒推值>=α;
    • β值:有与后继的节点,取当前子节点中的最小倒推值为其上界,称为β值。节点倒推值<=β;

    α-β 剪枝:

    • β剪枝:节点x的α值不能降低其父节点的β值,x以下的分支可停止搜索,且x的倒推值为α;
    • α 剪枝:节点x的β值不能升高其父节点的α值,x以下的分支可停止搜索,且x的倒推值为β;

    二、对弈AI落子的程序设计

    AI落子的函数如下。当前落子轮到AI时,进行落子。如果是先手第一步,直接下天元位置,否则调用choose函数选择一个落子位置。最后改变下棋的次序状态。

    void AI::putChess()
    {
        if(AIBoard->now) return;        //不是AI下时,跳过 
        if(first == 1 && AIBoard->chess[7][7] == 0)
        {           //先手第一步直接下中间 
            AIBoard->chess[7][7] = 1;
        }
        else
        {
            choose();       //选择一个位置 
            AIBoard->chess[chooseX][chooseY] = first;   //将这个位置放置我们的棋子 
        }
        AIBoard->now = !AIBoard->now;       //改变下棋次序的状态 
    }

    在计算落子位置之前,有两个预备的函数。一个是就算某一条线的分值,一个是计算整个棋盘的分值,后者需调用前者。而计算落子时,又需要计算整个棋盘的分值。

    int AI::getGoalOfPoint(int *a, int color)
    {
        if(a[0] == color && a[1] == color && a[2] == color && a[3] == color && a[4] == color) return 100000;  //五子 
        if(a[0] == 0 && a[1] == color && a[2] == color && a[3] == color && a[4] == color && a[5] == 0) return 10000;  //活四子 
        if(a[0] == 0 && a[1] == color && a[2] == color && a[3] == color && a[4] == 0) return 1000;              //活三子 
        if((a[0] == -1*color && a[1] == color && a[2] == color && a[3] == color && a[4] == color && a[5] == 0) ||
            (a[0] == 0 && a[1] == color && a[2] == color && a[3] == color && a[4] == color && a[5] == -1*color)) return 1000;   //死四子 
        if(a[0] == 0 && a[1] == color && a[2] == color && a[3] == 0) return 100;    //活二子 
        if((a[0] == -1*color && a[1] == color && a[2] == color && a[3] == color && a[4] == 0) ||
            (a[0] == 0 && a[1] == color && a[2] == color && a[3] == color && a[4] == -1*color)) return 100; //死三子 
        if(a[0] == 0 && a[1] == color && a[2] == 0) return 10;  //活一子 
        if((a[0] == -1*color && a[1] == color && a[2] == color && a[3] == 0) ||
            (a[0] == 0 && a[1] == color && a[2] == color && a[3] == -1*color)) return 10;   //死二子 
        return 0; 
    }

    计算棋盘的分值的函数如下。SumGoal为总分数,然后遍历每一个点。

    int AI::getGoalOfChess(board nowBoard, int color)
    {
        int sumGoal = 0;
        for(int i = 0; i < ROW; i++)
        {
            for(int j = 0; j < COL; j++)        
            {                       //扫描所有的点 

    每一个点的处理如下。

    int line[6];        //记录该点出发的线,一个六个 
    line[0] = nowBoard.chess[i][j];     //第一个是当前点 
    int x1 = i, y1 = j;
    int x2 = i, y2 = j;
    int x3 = i, y3 = j;
    int x4 = i, y4 = j;     //朝四个方向变化的x,y坐标 
    for(int it = 1; it < 6; it++)
    {
        y1--;
        if(y1 >= 0) line[it] = nowBoard.chess[i][y1];   //如果有棋子,就赋值 
        else line[it] = -2;     //没有就赋一个无效值,下同 
    }
    sumGoal += getGoalOfPoint(line,color);      //计算这一点的分值后相加 
    for(int it = 1; it < 6; it++)
    {
        x2++; y2--;
        if(y2 >= 0 && x2 < 15) line[it] = nowBoard.chess[x2][y2];
        else line[it] = -2;
    }
    sumGoal += getGoalOfPoint(line,color);
    for(int it = 1; it < 6; it++)
    {
        x3++;
        if(x3 < 15) line[it] = nowBoard.chess[x3][y3];
        else line[it] = -2;
    }
    sumGoal += getGoalOfPoint(line,color);
    for(int it = 1; it < 6; it++)
    {
        x4++; y4++;
        if(x4 < 15 && y4 < 15) line[it] = nowBoard.chess[x4][y4];
        else line[it] = -2;
    }
    sumGoal += getGoalOfPoint(line,color);

    对于每一个点,我们朝其四个方向取6个点(含其自身)。如果某一方向超出棋盘范围,就设一个无效值。每取一次,就调用刚刚那个函数计算一次分值,加到sumGoal。四个方向均如此,遍历的每个子均如此,最后得出当前棋局对于color方的局势分数。

    接下来是使用极大值极小值搜索和α-β剪枝搜索落子位置。首先,深拷贝一个棋盘,用来进行预估。

        board virtual0;     
        srand(time(0)); 
        for(int i = 0; i < ROW; i++)
        {
            for(int j = 0; j < COL; j++)
                virtual0.chess[i][j] = AIBoard->chess[i][j];
        }           //拷贝一个棋盘用来预估 

    然后是第一层极大值的搜索,首先将MAX值设一个最小值。然后遍历棋盘,如果某一点无子且其周围有子,则为一个预估点,假设这一点放置了本方的棋子。然后进行局势判断,如果已经赢了,就直接将MAX设为一个最大的值(添加了一个非常小的随机因子)。然后给落子位置chooseX和chooseY赋值。最后取消这个落子,恢复棋盘。

    int MAX = -1000000;         //极大值先设为最小 
    for(int i0 = 0; i0 < ROW; i0++)
    {
        for(int j0 = 0; j0 < COL; j0++)
        {
            if(virtual0.chess[i0][j0] == 0 && isAround(virtual0, i0, j0))
            {           //如果该处没有棋子,并且周围有棋子 
                virtual0.chess[i0][j0] = first;     //放置棋子预测 
                if(getGoalOfChess(virtual0,first) >= 100000) 
                {
                    MAX = 1000000-rand()%100;
                    chooseX = i0;
                    chooseY = j0;       //如果能获胜,直接将MAX值设最大 
                    virtual0.chess[i0][j0] = 0;     //取消刚刚放置的棋子 

    如果没有直接获胜,就进行下一步预测,也就是极小值层的搜索。先将MIN设为最大,变量cut1用于剪枝以及判断对方是否直接获胜时使用。同样遍历棋盘,如果五子且其周围有子,则为一个预估点,放置对手方的棋子。

    int MIN = 1000000;          //极小值先设为最小 
                bool cut1 = false;
                for(int p0 = 0; p0 < ROW; p0++)
                {
                    for(int q0 = 0; q0 < COL; q0++)
                    {
                        if(virtual0.chess[p0][q0] == 0 && isAround(virtual0, p0, q0))
                        {
                            virtual0.chess[p0][q0] = -1*first;      //放置一个棋子 
                            if(getGoalOfChess(virtual0,-1*first) >= 100000 && getGoalOfChess(virtual0,first) < 10000) 
                            {
                                MIN = -1000000+rand()%100;      //如果对手方能赢,将极小值设为最小 
                                cut1 = true;            //跳出此次预测 
                                virtual0.chess[p0][q0] = 0;     //恢复棋盘 
                                break;
                            }

    然后判断对手方能否直接获胜且本方无法获胜。如果是则将MIN改为一个最小值。然后修改cut1的值,使这次极小层的搜索结束,还原棋盘,然后跳出循环。

    如果对手方没有直接取胜的点,继续向下进行一层极大值的搜索,MAX1也是先设为最小。变量Cut2用来剪枝。同样遍历棋盘,如果五子且其周围有子,则为一个预估点,放置本方的棋子。然后计算本方棋盘局势减去对方棋盘局势的分数(评估函数)。如果这个极大值小于这个分数,就重新为其赋值,最后还原这一步的棋盘。

    int MAX1 = -1000000;
    bool cut2 = false; 
    for(int i1 = 0; i1 < ROW; i1++)         //又一层极大值的搜索 
    {
        for(int j1 = 0; j1 < ROW; j1++)
        {
            if(virtual0.chess[i1][j1] == 0 && isAround(virtual0, i1, j1))
            {
                virtual0.chess[i1][j1] = first;     //预测放置棋子 
                if(MAX1 < getGoalOfChess(virtual0,first)-getGoalOfChess(virtual0,-1*first)) 
                    MAX1 = getGoalOfChess(virtual0,first)-getGoalOfChess(virtual0,-1*first);
                                    //如果极大值小于启发式函数,就重新赋值 
                virtual0.chess[i1][j1] = 0;     //恢复棋盘 
            }

    接下来是一个β剪枝

        if(MIN < MAX1)      //剪枝 
        {
            cut2 = true;
            break;      
        }   
    }
    if(cut2) break;

    然后是第二层的极小值与第三层的极大值的一个倒推值的比较。如果极小值大,则重新赋值。最后恢复棋盘

    if(MIN > MAX1) MIN = MAX1;  //如果极小值大于倒推值,重新赋值 
    virtual0.chess[p0][q0]  = 0;    //恢复棋盘 

    然后是一个α剪枝。

        if(MAX > MIN)               //剪枝 
        {
            cut1 = true;
            break;
        }
    }
    if(cut1) break;

    然后是最外一层的极大值和第二层的极小值的倒推值的比较。如果极大值小,则重新赋值,并且修改落子的坐标为当前预估落子的坐标。最后恢复棋盘。

    if(MAX < MIN)       //如果极大值小于倒推值 
    {
        MAX = MIN;      //重新赋值 
        chooseX = i0;   //改变放置的x,y坐标 
        chooseY = j0;
    }
    virtual0.chess[i0][j0] = 0;

    以上就是AI落子的搜索过程。接下来是一些界面的设计和棋盘有关的代码。

    三、人类落子的相关代码

    人类落子的代码和AI的基本思想是相同的,不同的是AI要通过算法计算落子坐标,而人类是根据鼠标点击位置计算落子坐标。

    如下,形参x,y为鼠标点击的像素点的位置,我们通过计算将其转化为棋盘下标。并且这个下标处没有棋子时,放置人类的棋子。最后也要修改落子次序的状态。

    void human::putChess(int x, int y)
    {
        if(!humanBoard->now) return;        //如果不是人类下,则放置棋子无效 
        int index_x = 0;
        int index_y = 0;
        if(x > 50) index_x = (x-50)/40+1;
        if(y > 50) index_y = (y-50)/40+1;       //根据鼠标点击的位置,计算放置棋子的下标 
        if(humanBoard->chess[index_x][index_y] == 0)
        {
            humanBoard->chess[index_x][index_y] = first;        //将该坐标放置上我们的棋子 
            humanBoard->now = !humanBoard->now;             //改变下棋次序的状态 
        }
    }

    四、与绘制棋盘,胜负判断有关的代码

    有一个棋盘的board类,负责绘制棋盘,存储棋局信息,判定胜负等。这个类的构造函数如下。

    首先是声明一个二维数组用以存储棋局信息。变量now代表当前应为哪方下,前文已用到。变量runState代表当前棋局是已经结束还是在正常对弈。RED_PEN是一个自定义的红色画笔。

    接下来是绘制棋盘和棋子。绘制棋盘的代码如下。hdc为窗口句柄,chooseX和chooseY为AI落子位置,默认为一个无效位置,我们要为AI的落子画一个红圈方便我们识别其先前落子位置。然后是两个for循环,绘制了棋盘的横线和竖线。

    接下来是绘制棋子的过程。首先是获取系统的黑色和白色画刷。然后选择黑色画刷为天元点画一个小黑点。

    接下来遍历棋盘画棋子,每次遍历棋盘,如果落子为1,则画一个黑色圆圈,如果是-1则画一个白色圆圈。(先手为黑子,后手为白子)画完棋子后,再选择红色画笔根据chooseX和chooseY画一个圆圈作为AI落子提示。(如果chooseX和chooseY取值无效,这个红色圆圈是画不出来的,chooseX和chooseY默认值是一个无效值。)每次画完红圈后,要恢复默认的黑色画笔。

    接下来是检测棋盘当中是否有一方(color方)已经获胜,其思想与AI评估棋盘局势基本相同,也是遍历棋盘,每个点朝四个方向延伸,观察是否有已成五子的线。如下是进行遍历。

    然后是每个点的处理,先是定义朝四个方向变化的x,y坐标,已经用于计数的count。首先,判断当前的子是不是color颜色,如果不是直接过掉。如果是进行四次迭代,朝四个方向取四子,每有一子为color色,则count++,如果count最终为4,说明此线五子连珠,则sum++。最后如果sum大于0,则说明color色的棋子已有连成五子的线,则棋局结束,将代表棋局运行状态的变量runState改为false。最后返回sum值,可以根据sum值,判断某一方是否获胜。

    下边是重置棋盘的reset函数,就是将整个二维数组置0,相关变量再度初始化。

    五、与MFC、鼠标点击相关的部分代码

    本次实验是使用了win32程序,以及相关的MFC库,用以实现界面和鼠标监听等。先前已提到过少许界面方面的代码,下边将剩余代码展示。

    WM_PAINT是MFC中绘制窗口的消息,在窗口被创建时会被调用,也可以通过发送该条消息进行调用。每次调用时,先绘制棋盘,然后我们使用MessageBox语句弹出消息,询问是否选择先手,并根据其选择,为AI和人类的先手变量first赋值,以及下棋次序的变量now赋值。如果是AI先手,则先让AI落一子,然后再画一次棋盘。

    消息WM_LBUTTONDOWN,代表鼠标左键被按下。

    监听到此消息后,我们先获取点击的像素值。如果棋局尚未结束,我们将点击的位置做为形参传入到人类落子的函数中供其落子使用。然后绘制棋盘,判断落子之后人类是否获胜,如果获胜则弹出消息框提示,否则就继续进行。

    紧接着便是AI落子的代码,步骤与人类落子基本相同,不过无需获取鼠标点击位置。最终游戏结束时也是弹出消息框提醒。

    如果检测到棋局已经结束,我们再度弹出消息框,询问是否再来一次。如果是,则重置棋盘,发送绘制棋盘的消息。否则就直接销毁窗口。

    以上为整个五子棋项目设计的主要部分。

    六、结果分析

    实验环境:

    本次实验使用DEV C++编译器,创建了DEV win32项目程序,并使用了MFC的库进行界面和功能的设计。在代码上,使用了多文件编辑,共有main.cpp, board.h, board.cpp, AI.h, AI.cpp, human.h, human.cpp等文件,以及board、AI、human等自定义类。

    算法性能:

    本次实验采用极大极小搜索算法。搜索了三层(两层极大值,一层极小值)。每次搜索均需要遍历棋盘,棋盘大小为15*15,故三层搜索的复杂度为15的6次方。最后还需要遍历棋盘进行局势评估,所以最复杂的情况时,复杂度为15的8次方。这样每走一步棋需要大约25.6亿次左右的计算。对于目前的CPU处理速度,基本上在一秒钟左右下一步棋,可以满足与人正常对弈的时间需求。另外,由于使用了α-β剪枝算法,实际所需时间应当少于最复杂的时间。

    对于本次的AI,三层的极大极小搜索基本可以在时间和对战性能上取得平衡。

    如果想要在对战性能上取得更为突破性的进步,一种情况是进行更深层次的搜索,但是时间和计算能力上已无法满足此需求,考虑可以使用多线程编程以加快计算。另一种情况是优化评估函数,根据网上的知识,大多数的五子棋AI在搜索上是大同小异的,真正产生差距的是评估函数的优化,所以改进对战能力的更好的方法是优化评估函数,使其更能适应五子棋的规则,这方面所需要的是对于五子棋的一个深入了解。

    主要参考文献
    展开全文
  • 本程序使用matlab求取二维数组的极大值与极小值
  • 中国象棋项目中的极大值,极小值算法以及α-β剪枝技术技术极大值,极小值算法1. 问题提出2. 代码实现α-β剪枝优化1. 代码实现,注意和上面的代码进行比较(其实差别并不大)2. 代码分析3.其他可优化点 极大值,...

    极大值,极小值算法

    1. 问题提出

    在中国象棋的人机对战模块的开发中,对于电脑如何选择下一步要走的棋时,首先很自然的想到要设立一个估值函数,然后暴力遍历所有可以移动的己方棋子以及每个棋子可以移动的目标位置,找到一个移动后估值函数值最大的移动方式。这里的估值函数最开始只是简单的为每颗棋子固定的设置不同的价值,然后用己方棋子价值之和减去对方棋子价值之和的最大值作为估值函数的返回值。这种方式效果很差,电脑在走的时候老是容易在原地打转,其实对比我们平常下棋就可以发现,我们在每走一步时,都会思考对方会怎么走,我们吃掉对方的一个棋子,会不会反而损失更多,总而言之,就是人会考虑多步,而我们只让电脑考虑了一步,那么就想到让电脑也考虑多步,可是要如何来实现呢?我们仔细分析一下,我们走棋(正常人下棋,不说高手)是要尽量可以吃掉对方的棋,然后让对方无法吃掉自己的棋,换句话说,就是我们选择时尽量得到最高的分,并且让对方得到尽量小的分,这就引出了极大值,极小值算法,在对方作出的所有对它自己价值大的选择中(意味着对己方价值小,或者为负)的选择中选择一个对自己价值最大的。

    2. 代码实现

    (1)需要考虑多少层
    (2)递归调用终止条件
    (3)求最大值(getMaxScore)和求最小值(getMinScore)函数中会调用getAllPossible函数,而这个函数会根据被谁调用内部会有不同的处理方式,因为求最大值相当于己方走一步棋,而求最小值相当于对方走一步棋(对于本项目,内部是根据该红棋走还是黑棋走返回对应的可能步骤)
    (4)在最顶层之上,还应该有一个函数getBestStep开始去调用getMaxScore函数,并传入初始层级(对于本项目,这个函数会返回一个表示最佳选择的step,而不是一个分数)
    (5)在本项目中,因为人走完一步后,电脑会立刻去计算它需要走的一步,如何考虑的层级较高,则会阻塞前端的渲染,解决方案为延时一点时间(使用定时器实现)再让电脑去计算(或者还可以考虑使用子线程)

    //step是代表一步棋
    int getMaxScore(int level)
    {
    	//层级为0,直接计算当前分数返回
    	if(level == 0) return calcScore();
    	vector<step*> steps;//存放所有可能的走法
    	getAllPossibleStep(steps);//获取所有可能的走法并放到steps中
    	//step * res;//保存返回值
    	int maxScore = int(1<<31);//保存最大分数
    	for(auto it = steps.begin(); it != steps.end(); it++)
    	{
    		step * cur = *it;
    		fakeMove(step);//尝试去走某一步
    		int score = getMinScore(level-1);//走完某一步后计算得分
    		unFakeMove(step);//把这一步退回来
    		if(score > maxScore)
    		{
    			maxScore = score;
    		}
    	}
    	return maxScore;
    }
    //取得最小分数函数和取得最大分数函数基本一样
    int getMinScore(int level)
    {
    	//层级为0,直接计算当前分返回
    	if(level == 0) return calcScore();
    	vector<step*> steps;//存放所有可能的走法
    	getAllPossibleStep(steps);//获取所有可能的走法并放到steps中
    	//step * res;//保存返回值
    	int minScore = int(~(1<<31));//保存最大分数
    	for(auto it = steps.begin(); it != steps.end(); it++)
    	{
    		step * cur = *it;
    		fakeMove(step);//尝试去走某一步
    		int score = getMaxScore(level-1);//走完某一步后计算得分
    		unFakeMove(step);//把这一步退回来
    		if(score < maxScore)
    		{
    			maxScore = score;
    		}
    	}
    	return minScore;
    }
    

    α-β剪枝优化

    1. 代码实现,注意和上面的代码进行比较(其实差别并不大)

    int getMaxScore(int level, int currentMin)
    {
    	//层级为0,直接计算当前分返回
    	if(level == 0) return calcScore();
    	vector<step*> steps;//存放所有可能的走法
    	getAllPossibleStep(steps);//获取所有可能的走法并放到steps中
    	//step * res;//保存返回值
    	int maxScore = int(1<<31);//保存最大分数
    	for(auto it = steps.begin(); it != steps.end(); it++)
    	{
    		step * cur = *it;
    		fakeMove(step);//尝试去走某一步
    		int score = getMinScore(level-1);//走完某一步后计算得分
    		unFakeMove(step);//把这一步退回来
    		//剪枝代码,注意等号(有没有等号对最后的选择出来的结果都是不可控的,因为处理
    		//各个情况的顺序无法控制,或者说无法确定得分相同的两种情况到底哪个好,所以
    		//使用等号反而会提高一些效率,
    		//因为我们在计算时棋子的类别并不多,这个分数很有可能相等)
    		if(score >= currentMin)
    		{
    			return score;
    		}
    		
    		if(score > maxScore)
    		{
    			maxScore = score;
    		}
    	}
    	return maxScore;
    }
    //取得最小分数函数和取得最大分数函数基本一样
    int getMinScore(int level, int currentMax)
    {
    	//层级为0,直接计算当前分返回
    	if(level == 0) return calcScore();
    	vector<step*> steps;//存放所有可能的走法
    	getAllPossibleStep(steps);//获取所有可能的走法并放到steps中
    	//step * res;//保存返回值
    	int minScore = int(~(1<<31));//保存最大分数
    	for(auto it = steps.begin(); it != steps.end(); it++)
    	{
    		step * cur = *it;
    		fakeMove(step);//尝试去走某一步
    		int score = getMaxScore(level-1);//走完某一步后计算得分
    		unFakeMove(step);//把这一步退回来
    		
    		if(score <= currentMax)
    		{
    			return socre;
    		}
    		
    		if(score < maxScore)
    		{
    			maxScore = score;
    		}
    	}
    	return minScore;
    }
    

    2. 代码分析

    相比较与未优化状态,只是多了一个参数,多了一个判断。为什么可以直接剪掉呢?
    首先,我们需要明确一点,对分数的计算是在最底那一层进行的(也就是level等与0的时候),就好比一个树的结构中的叶子节点,计算结果一层一层往上送,在送的过程中一层一层比较,未经剪枝的时候,所有的叶子节点都会被计算,然后往上送,进行比较,选出最大值或最小值继续往上送,直到递归起点,即获得所需的得分最好的走法。而剪枝剪掉的就是不必要的计算,因为这里的递归是一次到底后进行计算,然后回溯,再到底进行计算,这样的话,叶子节点的计算并没有连续进行,中间有一个回溯的过程。
    (1)在求最大值函数中调用求最小值和函数,向其中传入一个当前的最大值,在求最小值函数中,若得到下层送上来的某个分数小于传入的最大值,则可以肯定在求最小值函数中的下层递归求解过程可以被剪掉,因为求最小值函数返回的值肯定不会大于那个比传入的最大值小的值。
    (2)在求最小值函数中调用求最大值的函数,向其传入一个当前的最小值,在求最大值的函数中,若得到下层传上来的值大于传入的最小值,则可以肯定在求最大值函数中的下层递归求解过程可以被剪掉,因为要递交给上层求最小值函数一个自己的最大值,而这个最大值肯定不会小于那个比传入的最小值大的值,那么在求最小值的函数中肯定不会被使用。

    3.其他可优化点

    (1)若对当前层所有可能的情况以某种方式进行排序,使得可以更早的得到需要返回的值,那么在调用下一层时可以得到更好的剪枝效果。(具体的可以在求所有情况的函数中,遍历棋子的顺序作出调整,比如说车所有可以走的步先与兵所有可走的步放入下一步集合中,其实这个做的更细的话,应该结合估值函数来进行调整,有点像在中间层先简易的使用一下估值函数)。
    (2)对估值函数的优化,原程序中每个棋子设定固定的分值,其实在不同的局势下,棋子应该有不同的价值,对其进行调整,应该能得到更好的选择。
    (3)判断某个棋子是否可以移动到某个位置时用到的函数应该可以优化,以提高判断的效率,在获取所有可能步骤的时候,对于不同的棋子,可以确定它不能走到某个位置,那么可以直接过滤掉,而不是调用判断是否可以移动的函数,用填充的方法(而非遍历)去获取所有可能的移动步骤。

    展开全文
  • 判断极值点是极大值还是极小值

    万次阅读 2018-10-18 14:40:49
    ①求函数的二阶导数,将极值点代入,...0, 为极小值点,反之为极大值点 二级导数值=0,有可能不是极值点; ②判断极值点左右邻域的导数值的正负:左+右- 为极大值点,左-右+ 为极小值点,左右正负不变,不是极值点。...

    ①求函数的二阶导数,将极值点代入,二级导数值>0, 为极小值点,反之为极大值点
    二级导数值=0,有可能不是极值点;
    ②判断极值点左右邻域的导数值的正负:左+右- 为极大值点,左-右+ 为极小值点,左右正负不变,不是极值点。

    展开全文
  • 1、求数组中的极大值和极小值 from scipy import signal import numpy as np import matplotlib.pyplot as plt data_x = np.arange(start = 0, stop = 40, step = 1, dtype='int') data_y = np.array([98,96,97,100...
    from scipy import signal
    import numpy as np
    import matplotlib.pyplot as plt
    
    data_x = np.arange(start = 0, stop = 40, step = 1, dtype='int')
    data_y = np.array([98,96,97,100,95,105,75,50,45,42,
    					51,85,90,92,91,89,101,62,65,52,
    					47,58,55,75,89,92,94,91,89,79,
    					85,65,42,55,48,50,85,88,95,100])
    
    # Find peaks
    # order:两侧使用多少点进行比较
    peak_indexes = signal.argrelextrema(data_y, np.greater, order=1)
    peak_indexes = peak_indexes[0]
    
    # Find valleys
    # order:两侧使用多少点进行比较
    valley_indexes = signal.argrelextrema(data_y, np.less, order=1)
    valley_indexes = valley_indexes[0]
    
    (fig, ax) = plt.subplots()
    
    # Plot all data
    ax.plot(data_x, data_y)
    
    # Plot peaks
    peak_x = peak_indexes
    peak_y = data_y[peak_indexes]
    ax.scatter(peak_x, peak_y, marker='o', color='red', label="Peaks")
    
    # Plot valleys
    valley_x = valley_indexes
    valley_y = data_y[valley_indexes]
    ax.scatter(valley_x, valley_y, marker='o', color='green', label="Valleys")
    
    # 添加标题
    plt.title('Find peaks and valleys using argrelextrema()')
    # 添加图例
    plt.legend(loc='best')
    # 保存图像
    plt.savefig('peaks-valleys.png')
    # 显示图像
    plt.show()
    

    设置order = 1,运行结果:
    在这里插入图片描述
    设置order = 3,运行结果:
    在这里插入图片描述

    展开全文
  • 这个评价函数应该从什么角度来写,极大值和极小值叶子节点的评价函数是不是需要评价角度不同? 如果AI方是极大者,按照极大值叶子节点评价极大者方的落子利益,值取正; 极小值叶子节点评价极小值方的落子效益,值取...
  • 编程中有时候需要一个初始极大值(或极小值)作为temp,当然可以自定义设置为10000(whatever),不过python中有一个值可以代替之:在python2.7中可以用这个(不过python3版本就没得了)>>> import sys >>> sys....
  • 庞特里亚金极小值原理 庞特里亚金极小值原理是在控制向量u(t)受限制的情况下,使得目标函数J取极小,从而求解最优控制问题的原理和方法,又称极大值原理。λ是协态向量,系统模型有多少个变量就有多少个协态。s和u...
  • 五子棋AI算法第二篇-极大极小值搜索算法

    万次阅读 多人点赞 2016-02-02 18:17:02
    AI实现的基本思路-极大极小值搜索算法五子棋看起来有各种各样的走法,而实际上把每一步的走法展开,就是一颗巨大的博弈树。在这个树中,从根节点为0开始,奇数层表示电脑可能的走法,偶数层表示玩家可能的走法。假设...
  • 计算神经网络隐藏层节点数极小值

    千次阅读 2018-05-14 21:56:42
    神经网络的隐藏层的节点数越少网络的速度越快,那么神经网络的隐藏层的节点数是否有一个可以保证性能的极小值,本文用mnist数据集做了实验。首先制作一个784*n*2的神经网络,用于测试0-9中的任意两个数的隐藏层的...
  • 功能:黄金分割法求函数极小值点。 源码 function [xo, fo] = MinValue_Gold(func, a, b, eps, MaxIter) %{ 函数功能:黄金分割法确定最小值点,func在[a, b]上为单峰; 输入: func:目标函数句柄; a:左...
  • 极小值极大值算法-井字棋

    千次阅读 2015-08-24 08:56:56
    极小值极大值算法写的井字棋: #include #include #define COM -1 #define MAN 1 #define STEP 9 #define DRAW 0 #define ROW 3 #define COL 3 #define MAX_NUM 1000; struct Move { int x; int y; }; ...
  • 分别用MATLAB和C#编程实现二元函数梯度下降法求极小值
  • 极大极小值算法、α-β剪枝算法的理解

    万次阅读 多人点赞 2019-03-27 23:04:41
    定义:极大极小值算法(摘自百度百科) Minimax算法 又名极小化极大算法,是一种找出失败的最大可能性中的最小值的算法(即最小化对手的最大得益)。通常以递归形式来实现。 ========================= 谈一下我的...
  • 解决echarts柱形图数值差距大,极小值渲染问题 对于一个初学者,echarts柱形图渲染极小值,指数类数据, 由于数据存在数量级差异太大,导致渲染出这种问题,下图: 很明显,这不是我想要的效果,经过查看官网实例,...
  • 学过函数曲线的极小值和最小值的概念吧,局部最佳和全局最佳是类似的关系。 一般训练陷入停滞主要是两方面的原因: 陷入误差曲面凹陷点。 神经网络的激活函数是S函数,这个函数的两端是平坦的,算法...
  • 极大极小值算法

    万次阅读 2013-08-24 18:32:30
    极小极大的定义 Minimax算法 又名极小化极大算法,是一种找出失败的最大可能性中的最小值的算法(即最小化对手的最大得益)。通常以递归形式来实现。 Minimax算法常用于棋类等由两方较量的游戏和程序。该算法是...
  • 我们都知道,如果想对int型变量清极大值或极小值,我们一般选择memset(a,0x3f,sizeof a);或者memset(a,0xef,sizeof a);。然而,如果对double型清0x3f,我们经常会得到一个连1都不到的小数。那么对double清极值是否...
  • 从人落子开始到出现胜负...极大极小值搜索算法,来搜索(回溯)这个解空间:它假设人和电脑都是极其聪明的,他们都会选择出最优的一步。 但是搜索整棵树是不现实的,16*16!指数级,所以只回溯n步,即这个AI考虑的是N
  • 功能:进退法和黄金分割法确定极小值。 源码 function result = Advance_Retreat_Gold(func, t0, step, eps) % 进退法和黄金分割法确定极小值 % ===============================================================...
  • 利用0.618法(黄金分割法)求极小值

    万次阅读 多人点赞 2018-09-22 18:28:55
    利用0.618法(黄金分割法)求极小值 思路图解: MATLAB程序如下: clc,clear; epsilon=10^-4; phi=@(x) x^2-sin(x); %phi为目标函数 a=0;b=1; %a,b,分别为区间(a,b)的端点 t=(sqrt(5)-1)/2; %t为区间长度缩短率,即...
  • MATLAB中利用最速下降法求解Rosenbrock函数的局部极小值 % Meringue % 2017/4/14
  • 作求解无约束极小值点范例。 代码: import scipy.optimize as opt import numpy as np def test_fmin(fminfunc,x0,a): """ x0为优化算法的初始值,各种优化算法必须 a为目标函数的参数 """ def targetfunc...
  • 题目大意:给定一个n∗mn*m的矩阵,标记出其中的局部极小值,要求填入1...n∗m1...n*m,求方案数《多年的心头大恨终于切掉了系列》 考虑将数字从小到大一个一个填进去 由于局部极小值最多88个,我们可以状压DP 令...
  • python函数极小值

    万次阅读 2018-01-26 12:13:28
    min1=fmin(f,3)#求3附近的极小值 min2=fmin(f,0)#求0附近的极小值 min_global=fminbound(f,-10,10)#这个区域的最小值 print(min1) print(min2) print(min_global) plt.plot(x,f(x)) plt.show() 输出: Optimization ...
  • 局部极小值定义: 全局极小值定义: 下图给出了一个存在很多局部极小值的函数,对于像这样的函数,寻找全局最优会很困难,因为算法往往被“困”在局部极小值上。有一类规划问题很特殊,它是凸规划(目标函数和约束...
  • python:时间序列 求极大值,极小值

    千次阅读 2020-10-05 15:28:33
    )): j = num_peaks[0][i] print(j, week_max.iloc[j,:]) # 求极小值 week_min = df.groupby(df.index.week).min() #print('week_min:',week_min) wek_min = week_min['close'].values num_less = signal....

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 459,411
精华内容 183,764
关键字:

极小值