02 November 2019

    打ち歩詰めのチェックに比べたら簡単

     前回の記事で将棋アプリの静的評価関数内で玉を2枚持っていれば勝ち(玉を取れば勝ち)と判定していて、ステイルメイト=引き分けというチェスのルールに対応出来ないことを書きましたが、ステイルメイトに対応するために2つのやり方を試してみました。

    方法1:詰み判定(ゲーム終了判定)処理を追加する

     王様が取られていたらゲーム終了とするのではなく、手番と駒の利きと王手(チェック)の有無などの情報を駆使して現時点の局面が詰んでいる(チェックメイト状態)かどうかの判断を含めて評価関数内で評価するやり方です。王様(キング)が取られているかどうかだけを見て判断するより処理は複雑で重い処理になります。こういう場合は先手勝ち、こういう場合は王手放置で後手負け、こういう場合はステイルメイトで引き分け、と評価関数内でいちいち定義していくのでif文、case文だらけになり重たい処理になります。でも、その分先読みの深さを一手から二手省略できるのでメリットも大きいです。
     じつは以前にも将棋アプリで思考時間短縮になるかと思い試してみたことがあったのですが、思ったほど効果が上がらなかったのでリリース版には採用しませんでした。それに一つ一つのケースについて勝ち負けの判定をするので漏れが生じてバグが発生し易いのも採用を見送った理由です。
     あと、この方法で作ると王様を取る以前の段階で評価しますので、ユーザーに相手玉を取るところまで指し手を進めることは出来なくなりますが、チェスの場合もチェックメイト(詰み)の段階でゲームを終えるのが一般的なようなので問題ないと思います。

    方法2:一定条件下で追加で先読みする

     王様(キング)を二つ持っていれば勝ちという評価関数は変更せずに、先読みの過程でキングがチェックされていなくてキングを動かせない局面の場合には指定されている先読みの深さを無視して、さらに一手余計に先読みするという方法です。以前の記事に書いた打ち歩詰めチェックの方法と同じです。ステイルメイトの局面である可能性がある時は、先読み時に指定する何手先まで読むかを制限する引数を無視してさらに一手読むようにするところがミソです。打ち歩詰めと違って2手読む必要はなく、次にキングが取られるかどうかだけを見ればいいので追加で先読みするのは一手(チェス流に言えば0.5手読み)で済みます。打ち歩詰めチェックよりは楽だし、十分実績のある既存のコードなので新たなバグが発生する可能性も低いと思って、まずこの方法で実装しました。
     このサイトによるとステイルメイトの定義は以下のようになっています。

    1. チェックされていない
    2. キング以外に動かせる駒がない。
    3. キングをどこに動かしても取られてしまう。(自殺行為でルール上そのようなマスには移動できない)

     条件1.と3.は軽い処理で済みますが、2.の条件をチェックするには結局全ての駒の動きを調べる必要があるので、それをするぐらいならもう一手余分に先読みさせて済まそうという考え方です。条件1.と3.を満たす局面が現れた時だけ条件2.を調べて、勝ち(最大値)か負け(最小値)の評価値が返ってきたら評価値を強制的にDraw(評価値=0)に変更するということです。打ち歩詰め対策の時は評価値に−1を掛けて打ち歩詰めをした方が負けになるようにしましたが、ステイルメイトの場合は評価が逆転するわけではないので0に置き換えるだけでいいと思います。←評価値0にするのは問題ありました、詳細は次の記事参照

    とりあえず「方法2」で実装

    例1:Bf6のステイルメイトを避ける

    (クリックで画像拡大)

    テスト1

     前回の記事で挙げた例ではとりあえずステイルメイトを避けるようになりました。但しNf7(Knightをf7に移動する手)がこの局面での最善手かどうかは分かりません。

    例2:c8=Qのステイルメイトを避ける

    (クリックで画像拡大)

    テスト2

     修正前はポーンがc8に移動してQueenに成っていた(=ステイルメイト)のですが、修正後はBishopに成ってステイルメイトを避けるようになりました。以下Kb8,Qb7と進んでチェックメイトで白の勝ちです。

    打ち歩詰めやステイルメイトの負担

     以下のコードはgithubの将棋アプリの先読み探索部分のコードですが、全コードの25%(青い部分)が打ち歩詰めチェックのためだけのコードになっています。今回のチェスプログラムのコードも同様にステイルメイトチェックのために随分プログラムのレスポンスが悪くなってしまいました。仕方がないこととは言えこの特殊なルールのためにパフォーマンスが低下してしまいます。

    
        think: (board, oppo, limit, preValue, utifudume = null) ->
            spare = {}
            lastscore = if @turn == Const.FIRST then Const.MIN_VALUE else Const.MAX_VALUE
            lastposi = null
            lastkoma = null
            laststatus = null
            score = 0
            kinds = []
            move_piece = null
    
            utifudume_flg = null
    
            for koma in board.pieces when koma.turn == @turn
                if koma.status == Const.Status.MOTIGOMA
                    continue if koma.kind() in kinds
                    kinds.push(koma.kind())
                    for col in [1..board.cols]
                        for row in [1..board.rows]
                            dest = (v for v in board.pieces when v.posi? && v.posi[0] == row && v.posi[1] == col)
                            continue if dest.length != 0
    
                            if koma.kind() == 'Fu' && is_utifuOute.call @, board, koma, [row, col]
                                if board.check_utifudume(koma, [row, col])
                                    utifudume_flg = null
                                    continue
                                else
                                    utifudume_flg = koma
                            else
                                utifudume_flg = null
    
                            move_piece = new Piece.Piece(koma.turn, koma.status, koma.posi)
                            if board.check_move(koma, [row, col])
                                board.move_capture(koma, [row, col])
                                result = board.gameover()
                                if limit > 0 && !result
                                    ret = oppo.think(board, @, limit - 1, lastscore, utifudume_flg)
                                    score = ret[2]
                                else
                                    score = check_tumi.call @, board
                                shortCut = false
                                if (score > lastscore && @turn == Const.FIRST) || (score < lastscore && @turn == Const.SECOND)
                                    spare["koma"] = lastkoma
                                    spare["posi"] = [].concat(lastposi)
                                    spare["score"] = lastscore
                                    spare["status"] = laststatus
                                    lastkoma = koma
                                    lastscore = score
                                    lastposi = [].concat([row, col])
                                    laststatus = koma.status
                                    if ((preValue < score && @turn == Const.FIRST) || (preValue > score && @turn == Const.SECOND))
                                        shortCut = true
                            koma.turn = move_piece.turn
                            koma.status = move_piece.status
                            koma.posi = move_piece.posi
                            return [lastkoma, lastposi, lastscore, laststatus, spare] if (score >= Const.MAX_VALUE && @turn == Const.FIRST) || (score <= Const.MIN_VALUE && @turn == Const.SECOND)
                            return [lastkoma, lastposi, lastscore, laststatus, spare] if shortCut
                else
                    for v in eval("Piece." + koma.kind()).getD(koma.turn, koma.status)
                        buf = [].concat(koma.posi)
                        loop
                            break unless ((buf[0] + v.xd in [1..board.cols]) && (buf[1] + v.yd in [1..board.rows]))
                            promotion = false
                            buf[0] += v.xd; buf[1] += v.yd
                            dest = (o for o in board.pieces when o.posi? && o.posi[0] == buf[0] && o.posi[1] == buf[1])
                            break if dest.length != 0 && dest[0].turn == koma.turn
                            move_piece = new Piece.Piece(koma.turn, koma.status, koma.posi)
                            if dest.length != 0
                                dest_piece = new Piece.Piece(dest[0].turn, dest[0].status, dest[0].posi)
                            if board.check_move(koma, buf)
                                promotion = true if board.check_promotion(koma, buf)
                                board.move_capture(koma, buf)
                                loop
                                    result = board.gameover()
    
                                    if utifudume? && !result && dest.length != 0 && dest[0].id == utifudume.id && koma.kind() != 'Ou'
                                        ret = oppo.think(board, @, 0, lastscore, null)
                                        if ret[2] >= Const.MAX_VALUE || ret[2] <= Const.MIN_VALUE
                                            score = ret[2] * -1
                                        else
                                            if limit > 0
                                                ret = oppo.think(board, @, limit - 1, lastscore, null)
                                                score = ret[2]
                                            else
                                                score = check_tumi.call @, board
                                    else
        
                                        if limit > 0 && !result
                                            ret = oppo.think(board, @, limit - 1, lastscore, null)
                                            score = ret[2]
                                        else
                                            score = check_tumi.call @, board
                                    shortCut = false
                                    if (score > lastscore && @turn == Const.FIRST) || (score < lastscore && @turn == Const.SECOND)
                                        spare["koma"] = lastkoma
                                        spare["posi"] = [].concat(lastposi)
                                        spare["score"] = lastscore
                                        spare["status"] = laststatus
                                        lastkoma = koma
                                        lastscore = score
                                        lastposi = [].concat(buf)
                                        laststatus = koma.status
                                        if ((preValue < score && @turn == Const.FIRST) || (preValue > score && @turn == Const.SECOND))
                                            shortCut = true
                                    # 駒が成れる場合は成ってからもう一度評価する
                                    if promotion
                                        promotion = false
                                        koma.status = Const.Status.URA
                                    else
                                        break
                            koma.turn = move_piece.turn
                            koma.status = move_piece.status
                            koma.posi = move_piece.posi
                            if dest.length != 0
                                dest[0].turn = dest_piece.turn
                                dest[0].status = dest_piece.status
                                dest[0].posi = dest_piece.posi
                            return [lastkoma, lastposi, lastscore, laststatus, spare] if (score >= Const.MAX_VALUE && @turn == Const.FIRST) || (score <= Const.MIN_VALUE && @turn == Const.SECOND)
                            return [lastkoma, lastposi, lastscore, laststatus, spare] if shortCut
                            break unless (dest.length == 0 && v.series)
            return [lastkoma, lastposi, lastscore, laststatus, spare]
    
        is_utifuOute = (board, piece, d_posi) ->
            oppo = if piece.turn == Const.FIRST then Const.SECOND else Const.FIRST
            oppo_king = (v for v in board.pieces when v.turn == oppo && v.kind() == 'Ou')[0]
            buf = [].concat(d_posi)
            buf[0] += Piece.Fu.getD(piece.turn, piece.status)[0].xd
            buf[1] += Piece.Fu.getD(piece.turn, piece.status)[0].yd
            return (oppo_king.posi[0] == buf[0] && oppo_king.posi[1] == buf[1])
    
    

     今回は方法2でステイルメイト対策をしましたが、方法1のやり方も検討中です。

    ステイルメイトも打ち歩詰めもゲームを面白くする要素かも

     チェスプログラムのテストをしている際に「引き分けがチェスを面白くしている」という意見を見かけました(質問1に対する回答)
     前回の記事でステイルメイトは合理的でないと貶しましたが、いろいろなケースをテストしている内に「ステイルメイト(引き分け)がチェスを面白くしている」という意見の意味が少し分かってきました。将棋の打ち歩詰め同様ゲームを面白くしている要素なのかもしれません。




    blog comments powered by Disqus