MATLAB—一字棋（极大极小搜索）

刺骨的言语ヽ痛彻心扉 2022-06-14 05:06 144阅读 0赞

## init.m ##

%初始化棋盘状态
    function cur=init()
        cur=rand(3,3);  %存储当前棋盘的状态
        %计算机为先手时的初值，即均为0
        for i=1:3
            for j=1:3
                cur(i,j)=0;
            end
        end
    end

## checkWin.m ##

%检查是否有一方赢棋（0：没有任何一方赢；1：计算机赢；-1：人赢）
    function flag = checkWin(cur)
        %该方法没有判断平局
        for i=1:3        
                          %判断一行
            if cur(i,1)==1&&cur(i,2)==1&&cur(i,3)==1     %是否计算机赢
                flag=1;
                return;
            end
            if cur(i,1)==-1&&cur(i,2)==-1&&cur(i,3)==-1  %是否人赢
                flag=-1;
                return;
            end
                          %判断一列
            if cur(1,i)==1&&cur(2,i)==1&&cur(3,i)==1     %是否计算机赢
                flag=1;
                return;
            end
            if cur(1,i)==-1&&cur(2,i)==-1&&cur(3,i)==-1  %是否人赢
                flag=-1;
                return;
            end
        end
        
        %判断两个对角线
        if (cur(1,1)==1&&cur(2,2)==1&&cur(3,3)==1)||(cur(3,1)==1&&cur(2,2)==1&&cur(1,3)==1)  %是否计算机赢
            flag=1;
            return;
        end
        if((cur(1,1)==-1&&cur(2,2)==-1&&cur(3,3)==-1)||(cur(3,1)==-1&&cur(2,2)==-1&&cur(1,3)==-1))%是否人赢
            flag=-1;
            return;
        end
        
        %没有任何一方赢
        flag=0;  
        return;
    end

## value.m ##

%评估当前棋盘状态的值（同时可以用p或q判断是否平局）
    function pq= value(cur)
    p=0;
    q=0;
    isWin=checkWin(cur);
    tmpQP=rand(3,3);   %表示棋盘数据的临时数组，其中的元素0表示该格为空
    
    if(isWin==-1)      %如果用户玩家赢了，置棋盘估计值为负无穷
        pq=-10000;
        return;
    end
    if(isWin==1)       %如果计算机赢了，置棋盘估计值为无穷
        pq=10000;
        return;  
    end
    
    %计算机一方（MAX）
    for i=1:3
        %将棋盘中的空格填满自己的棋子，既将棋盘数组中的0变为1
        for j=1:3
            if cur(i,j)==0
                tmpQP(i,j)=1;
            else
                tmpQP(i,j)=cur(i,j);
            end
        end
    end
    for i=1:3         %计算共有多少连成3个1的行
        if tmpQP(i,1)+tmpQP(i,2)+tmpQP(i,3)==3
            p=p+1;
        end
    end
    for i=1:3         %计算共有多少连成3个1的列
        if tmpQP(1,i)+tmpQP(2,i)+tmpQP(3,i)==3
            p=p+1;
        end
    end
    if tmpQP(1,1)+tmpQP(2,2)+tmpQP(3,3)==3
        p=p+1;        %计算共有多少连成3个1的对角线
    end
    if tmpQP(3,1)+tmpQP(2,2)+tmpQP(1,3)==3
        p=p+1;
    end
    
    %人一方（MIN）
    for i=1:3
        %将棋盘中的空格填满自己的棋子，既将棋盘数组中的0变为-1
        for j=1:3
            if cur(i,j)==0
                tmpQP(i,j)=-1;
            else
                tmpQP(i,j)=cur(i,j);
            end
        end
    end
    for i=1:3        %计算共有多少连成3个-1的行
        if tmpQP(i,1)+tmpQP(i,2)+tmpQP(i,3)==-3
            q=q+1;
        end
    end
    for i=1:3        %计算共有多少连成3个-1的列
        if tmpQP(1,i)+tmpQP(2,i)+tmpQP(3,i)==-3
            q=q+1;
        end
    end
    if tmpQP(1,1)+tmpQP(2,2)+tmpQP(3,3)==-3
        q=q+1;       %计算共有多少连成3个-1的对角线
    end
    if tmpQP(3,1)+tmpQP(2,2)+tmpQP(1,3)==-3
        q=q+1;
    end
    
    %返回评估出的棋盘状态的值
    pq=p-q;  
    end

## tuozhan.m ##

function [tail,open] = tuozhan(g,tail,open,index)
    cur=open{1,index}.S;
    k=0;
    %对当前状态进行拓展
    for i=1:3
        for j=1:3
            flag=1;         %标志拓展后的结点是否与之前拓展的结点同构
            
            if cur(i,j)==0
                k=k+1;
                tmpcur=cur;
                tail=tail+1;
                %判断当前结点是MAX还是MIN走的
                if g/2~=1            %根据拓展深度的不同，值有所变化，此程序只试探两步
                    tmpcur(i,j)=1;   %若是MIN走的，下一步MAX走
                else
                    tmpcur(i,j)=-1;  %若是MAX走的，下一步MIN走
                end
                %判断拓展后的结点是否和之前的结点同构，若同构flag=0，否则flag=1
                for k=index:tail-1
                    if open{1,k}.S==rot90(tmpcur,1)
                        flag=0;
                        tail=tail-1;
                        break;
                    end
                    if open{1,k}.S==rot90(tmpcur,2)
                        flag=0;
                        tail=tail-1;
                        break;
                    end
                    if open{1,k}.S==rot90(tmpcur,3)
                        flag=0;
                        tail=tail-1;
                        break;
                    end
                    if open{1,k}.S==fliplr(tmpcur)
                        flag=0;
                        tail=tail-1;
                        break;
                    end
                    if open{1,k}.S==flipud(tmpcur)
                        flag=0;
                        tail=tail-1;
                        break;
                    end
                    
                    if open{1,k}.S==rot90(flipud(tmpcur),1)
                        flag=0;
                        tail=tail-1;
                        break;
                    end
                    if open{1,k}.S==rot90(flipud(tmpcur),2)
                        flag=0;
                        tail=tail-1;
                        break;
                    end
                    if open{1,k}.S==rot90(flipud(tmpcur),3)
                        flag=0;
                        tail=tail-1;
                        break;
                    end
                    if open{1,k}.S==rot90(fliplr(tmpcur),1)
                        flag=0;
                        tail=tail-1;
                        break;
                    end
                    if open{1,k}.S==rot90(fliplr(tmpcur),2)
                        flag=0;
                        tail=tail-1;
                        break;
                    end
                    if open{1,k}.S==rot90(fliplr(tmpcur),3)
                        flag=0;
                        tail=tail-1;
                        break;
                    end
                end
                %如果flag不为0，说明没有同构，可以拓展，加入open表里
                if flag~=0
                    open{1,tail}.g=g;
                    open{1,tail}.v=value(tmpcur);
                    open{1,tail}.S=tmpcur;   
                    open{1,tail}.fa=cur;
                end 
            end 
            
        end
    end
    
    end

## chushi.m ##

function table=chushi(cur)
        table=cell(1);
        table{1,1}.g=0;
        table{1,1}.v=value(cur);
        table{1,1}.S=cur;  %当前节点的状态
        table{1,1}.fa=[]; %父节点的状态，这样的保留可以从找到的目标状态追踪到初始状态

## yunxing.m ##

%第一阶段 A=[0 0 0;0 0 0;0 0 0]
    %第二阶段 A=[0 -1 0;0 1 0;0 0 0]
    %第三阶段 A=[0 -1 -1;0 1 0;1 0 0]
    function jieguo = yunxing(cur)
        
        close=cell(1);
        open=chushi(cur);
        index=1;            %记录拓展结点的下标，为tuozhan.m方便
        tail=1;
        g=1;
        c=1;
        
        while 1
            if g>2          %若深度大于2，则停止
                break;
            end
            [tail,open]=tuozhan(g,tail,open,index);
            close{1,c}=open{1,index};   %将已扩展的节点放入CLOSED8表中
            c=c+1;
            index=index+1; 
            if index<=tail
                g=open{1,index}.g;
                g=g+1;         
            else     %当只剩程序方最后一步时
                break;
            end
        end
        
        %端结点静态估值和倒推值计算
        i=c-1;             %查close表
        while i>0
            max=-1000000;
            min=1000000;
            j=tail;         %查open表
            while j>1
                if open{1,j}.fa==close{1,i}.S
                    if close{1,i}.g==1     %因只拓展两层，所以可以直接写1和0，若拓展深度大于2，则做出相应的改变
                      if open{1,j}.v<min
                         min=open{1,j}.v;
                      end
                    end
                    if close{1,i}.g==0  
                      if open{1,j}.v>max
                         max=open{1,j}.v;
                      end
                    end
                end
                j=j-1;
            end
            
            for k=1:tail                  %将改过的v写回open表
                if open{1,k}.S==close{1,i}.S
                    if close{1,i}.g==1
                        open{1,k}.v=min;
                    end
                    if close{1,i}.g==0
                        open{1,k}.v=max;
                    end
                end   
            end
            if close{1,i}.g==1
                close{1,i}.v=min;%更新close表中的值
            end
            if close{1,i}.g==0
                close{1,i}.v=max;%更新close表中的值
            end
            i=i-1;
        end
        
        %输出结果
        for i=1:tail
            if open{1,i}.g==1
               if open{1,i}.v==open{1,1}.v
                   jieguo=open{1,i}.S;
                   disp('程序方：');
                   disp(open{1,i}.S);   %查找open表，看取的哪一个MIN中的MAX值，然后输出此矩阵
                   break;
               end
            end
        end
        
    end

## operation.m ##

function []=operation()
    input('*****程序方先手*****');
    step=0;              %记录走的步数，以判断是否最后的平局
    cur=init();          %当程序方为先手时
        while 1
    
            jieguo=yunxing(cur);
            step=step+1;
            if checkWin(jieguo)==1
               disp('计算机赢，您输了！'); 
               break;
            end
            if checkWin(jieguo)==-1
                disp('恭喜，您赢了！');
                break;
            end
            if checkWin(jieguo)==0
                if step==9
                    disp('平局');
                    break;
                end
            end
            disp('请输入位置：');
            matri = input('[a b] = ');
            a = matri(1);    %横坐标
            b = matri(2);    %纵坐标
            while jieguo(a,b)~=0
                disp('输入有误！');
                disp('请重新输入位置：');
                matri = input('[a b] = ');
                a = matri(1);    %横坐标
                b = matri(2);    %纵坐标
            end
    
            jieguo(a,b)=-1;
            disp('我方：');
            disp(jieguo);
            step=step+1;
            cur=jieguo;     
        end
        
    end

运行结果：

![Center][]

![Center 1][]

[Center]: /images/20220614/4f71169f413d4bbe865119b49920242e.png
[Center 1]: /images/20220614/0cb37a5feeaa479c89b5b1bd71155e08.png