27 October 2019

    持ち駒が使えないチェスなら強いAIが作れるかも

     チェスに関してはルールもよく理解しないままネットやアプリで少し遊んだことはあるのですが、チェス盤を使った実戦経験もない初心者です。ゲームに詳しくなくても初心者の自分が楽しめる程度の対戦AIなら開発することは出来ると思って、今の将棋アプリを流用してチェスアプリを作って見ることにしました。チェスは持ち駒が使えないので読む手の数も大幅に減るので、たとえJavaScript製のアプリであってもそこそこ強いAIが作れるだろうと目論んでいます。
     今リリースしている5五将棋アプリ(=5×5の盤面)はそこそこ強いのですが、局面の数が増える禽将棋アプリ7七将棋アプリ(=7×7の盤面)は自分が低レベル(マシン語に近いという意味)のプログラミング経験が少ないこともあって非常に弱いです。でも持ち駒が使えないチェスなら8×8と盤面は広くなりますが、読むべき局面数が減るのでそこそこ強いものが作れそうな気がしています。

    今まで深く考えたことがなかったステイルメイト

     アンパッサン、キャスリング、ポーンの成りが4種類(クイーン、ビショップ、ナイト、ルーク)になることなど、チェス独特のルールをなんとか実装出来て、将棋アプリをチェスアプリに変更するのは思ったより順調だなと思っていたところ、思わぬ問題にぶつかりました。

    チェスの一局面

     プログラムにチェスのルールを反映して、上の局面でAIに指させると、ビショップ(♗)をe7からf6に移動します。

    チェスの一局面

     上の局面は斜めに動くビショップ(♗)がh8の相手のキング(♚)を睨んでいて、将棋でいうなら準王手飛車です。将棋なら当然の一手のように思います。
     上の局面は将棋で表すと以下のようになります。

    チェスの一局面を将棋で現す

     持ち駒が使えないチェスではここで後手の受け方がありません。桂馬(チェスの場合はナイト♘)と玉が利いていて後手玉は動けませんし、角が後手玉を睨んでいて飛車も動かせないので後手の指す手がありません、必至の状態です。将棋なら後手の指す手がないので後手は投了するしかないのですが、チェスのルールでは、なんと!ステイルメイトとなって引き分けになります。チェスでは後手に合法手がない状態になると先手の勝ちになるのではなく、引き分けになるのです。
     将棋道場とかで先手が3三角(成りでも不成でも同じ)と指した時に、後手の人が「はい、ステイルメイトで引き分けね( ´,_ゝ`)プッ」なんて言ったら喧嘩になるのではないでしょうか
     この局面から指し進めたら必ず先手が後手玉を取ることが出来るので先手の勝ちというのが将棋のルールですが、チェスでは後手の指す手がない(合法手がない)場合は引き分けとなるそうです。

    将棋の評価関数

     githubに公開しているソースもそうですが、自分の将棋アプリの評価関数は大体以下のような構造になっています。

        check_tumi = (board) ->
            first = 0; second = 0
            kings = (v for v in board.pieces when v.kind() == 'Ou' && v.turn == Const.FIRST)
            switch kings.length
                when 2
                    return Const.MAX_VALUE
                when 0
                    return Const.MIN_VALUE
                else
                    for v in board.pieces
                        first += v.omomi() if v.turn == Const.FIRST
                        second += v.omomi() if v.turn == Const.SECOND
                    return (first - second)
    

     先手の玉が2枚あれば先手の勝ち、0枚なら後手が勝ち、それ以外は局面の静的評価値を計算するという感じです。つまり相手玉を取ることが最善、相手玉を取れば勝ちとなっています。ステイルメイトの上図のような局面では、その後ゲームを続ければ必ず先手が後手の玉を取れるので、先手勝ちと判断してしまいます。
     学習機能を持ったAIはまた違ったものになると思いますが、MIN-MAX法(+αβ法)を使った探索部分と静的評価関数を使っているものは大体似たような構造になっていると思います。特に、相手玉を取れるとこまで対戦を続けることが出来るようになっている将棋AIはこんな感じで作られているはずです。評価関数というのは先読みの過程で最も呼び出し回数が多いものの一つで、出来るだけ軽い処理(玉の数を数えれば済む)になるように考えて、このようにしたことは以前の記事にも書きました。
     でもステイルメイト(合法手が無い時)は引き分けと判定するには、玉が取られていない状態でも勝ちか負けか引き分けかの判断をする必要があるので、このままでは局面を正確に判断出来ません。将棋の場合も相手玉を取るまで指し続けることは稀で、相手玉が詰んだらゲームを終了しますが、将棋AIは相手玉を取ることを前提に局面を先読みし、その先ゲームを続けても玉が取られることが確定しているので詰みの段階でゲームを終了させているだけに過ぎません。でもチェスのステイルメイトの局面の場合は、王手が掛かっていない(=詰みではない)とは言え、その先ゲームを進めたらキングが取られることが確定しているのは将棋と同じなのにもかかわらず、別の判断(引き分け)をしなければいけないので評価関数を修正する必要が出てきます。自分の玉が取られることは確定しているのに、その時王手が掛かっていなければ引き分けという大逆転と言ってもいい評価をしなければなりません、納得できません。

    不合理なルール

     将棋やチェスを「相手の王様を取るゲーム」と考えるとステイルメイトというルールは筋が通らない不合理なルールに感じます。ステイルメイトというのは自分の駒がほとんど取られて圧倒的に劣勢になっている時に生じるのだと思いますが、どこかの権力者が強いチェスプレイヤーと対戦して劣勢になって、「指す手が無い(合法手が無い)状態にしたお前が悪い」と言いがかりをつけたことがルールの起源だったりするのでしょうか(適当)
     ←適当に書いたのですが、wikipediaにもそれに近いことが書いてありました

    かつて王侯貴族の相手をしていた客分のプロフェッショナルチェスプレーヤーは王侯貴族の面子をつぶさないため、ステイルメイトは引き分けというルールを思いついた。これが、いつの間にか、王侯貴族相手でなくても一般的になり、チェスでは公式戦においてもステイルメイトは引き分けと規定されている

     海外にも忖度があるようです。:sweat_smile:
     評価関数をどのように修正したかは次の記事に書こうと思います。




    blog comments powered by Disqus