MinMax 法による思考

ミニマックス法による基本的な考え方です。

前田稔(Maeda Minoru)の超初心者のプログラム入門

ミニマックス法による思考

残り手数が3手になった白の手番です。
 ・白は「A,B,C」の三箇所に駒を置くことができるものとします。
 ・黒は「A,B,C」のそれぞれに対して「1,2]の二箇所に駒が置くことができます。
 ・最後の一箇所に白の駒を置いて終局です。
残り3手(白の手番) Aの手Bの手Cの手
残り2手(黒の手番) 1の手2の手1の手2の手1の手2の手
最後の1手(白の手番) 2の手1の手2の手1の手2の手1の手
結果 ●20○44●33○31●30○34●32○32●38○26●35○29
○の評価 +24-2+40-12-6

あなたなら白の手番で「A,B,C」のどの手を選びますか?
  1. Aの手は黒が間違えれば大勝(+24)しますが、正しく打たれると負け(-2)ます。
  2. Bの手は黒が間違えれば勝(+4)ですし、正しく打たれても引き分け(0)です。
  3. Cの手は黒が間違えても負け(-6)ですし、正しく打たれたら大負け(-12)します。
このようなときに相手が最善の手を打つことを前提に、最良の手を選ぶ考え方がミニマックス法です。

【演習1】

「最後の2手」を読み切って、どこに置くのが有利かを判定する関数を作成して下さい。
【例】
黒の手番(Think2) 1の場所 2の場所
白の手番(Think1) 2の場所 1の場所
結果 ●20 ○44 ●33 ○31
my● の評価 -22 +2

B_think() から Think2() を呼び出す

  1. 黒の思考関数 B_think() から Think2() 関数を呼び出します。
    Think2 は最後の2手のときに呼び出されます。
    if (App->Countdown<3) { //最後の2手
    Think2 は、これまでパスが無ければ先手(●)の手番で呼び出されます。
    呼び出す前にパスのチェックをするので、パスのときに Think2 が呼び出されることはありません。
        EXPORT BYTE B_think(OseroApp *App)
        {
                    :
            my= App->Teban();                   //黒(手番)の駒
            n= App->Search(my);                 //黒の手番で打てる場所を検索
            if (n==0)   return(0xFF);           //パスのとき
            if (App->Countdown<3)               //最後の2手
            {   Think2(App,&pos);               //最後の二手の有利な方
                return(pos);
            }
            return(App->S[rand()%n]);           //乱数で決める
        }
        

「最後の2手」を読み切る関数 Think2()

  1. 「最後の2手」のどちらに置くのが有利かを判定する関数を作成します。
  2. my には自分の駒が you には対戦相手の駒が格納されているものとします。
    my の打つ手が一箇所のときは、無条件にプレイします。
    「先手の手番で最後の2手で二箇所を選択できる」ときに Think2() 関数が機能を発揮するので、この関数が働くのは3回に1度ぐらいです。
        int  Think2(OseroApp *App,BYTE *pos)
        {       :
            BYTE    s[30];
            short   sn;
                :
            App->CopyST();                      //T[8][8] を ST[8][8] にコピー
            sn= App->Search(my,s,App->ST);      //手番で打てる場所を検索
            if (sn==1)                          //打てる手は一箇所
            {   *pos= s[0];
                return(0);
            }
        
  3. 二箇所の打つ手を p1, p2 とします。
    p1 に my のコマを置いた局面を設定します。
    設定した局面を評価する関数(Think1)の値を val1 に格納します。
            //1手目の手を打つ
            App->Reverse(p1,my,App->ST);
            val1= Think1(App);                  //p1 にコマを置いたときの評価値
        
  4. p2 に my のコマを置いた局面を設定します。
    設定した局面を評価する関数(Think1)の値を val2 に格納します。
            //2手目の手を打つ
            App->CopyST();                      //T[8][8] を ST[8][8] にコピー
            App->Reverse(p2,my,App->ST);
            val2= Think1(App);                  //p2 にコマを置いたときの評価値
        
  5. val1 と val2 を比べて評価値の大きい方の手を *pos に格納します。
            //二手の有利な方を返す
            if (val1>=val2)
            {   *pos= p1;
                return(val1);
            }
            *pos= p2;
            return(val2);
        }
        

最後の駒を置いて、局面を評価する関数(Think1)

  1. 普通この関数が呼ばれたときには p1 か p2 のいずれか片方が残されています。
  2. 残された方に you のコマを置きます。
        sn= App->Search(you,s,App->ST);             //相手の手番で打てる場所を検索
        if (sn>0)   App->Reverse(s[0],you,App->ST); //you でプレイする
        
  3. you のコマがパスのときには my のコマを置きます。
    my のコマもパスのときは、そのまま終局です。
        else                                        //パスのときは my でプレイする
        {   sn= App->Search(my,s,App->ST);
            if (sn>0)   App->Reverse(s[0],my,App->ST);
        } 
        
  4. my のコマの数を数えてリターンします。
        return(App->Count(my,App->ST));
        

【演習2】

  1. 残り手数が3手になった白の手番で、最後まで読みきる関数を作成して下さい。
    ○残り3手 Aの手Bの手Cの手
    ●残り2手 1の手2の手1の手2の手1の手2の手
    ○最後の1手 2の手1の手2の手1の手2の手1の手
    結果 ●20○44●33○31●30○34●32○32●38○26●35○29
  2. 最初は「三箇所に駒を置くことができるもの」としますが、二手目や三手目でパスや終局のときはどうすれば良いのでしょう。
    当然ながら、どんなケースでもプログラムが正しく動作することが求められます。

[Next Chapter ↓] 残り3手を読み切る
[Previous Chapter ↑] ST[8][8] を利用した思考関数

超初心者のプログラム入門(Win32API C++)