打ち歩詰めのチェックに比べたら簡単
前回の記事で将棋アプリの静的評価関数内で玉を２枚持っていれば勝ち（玉を取れば勝ち）と判定していて、ステイルメイト＝引き分けというチェスのルールに対応出来ないことを書きましたが、ステイルメイトに対応するために２つのやり方を試してみました。
方法１：詰み判定（ゲーム終了判定）処理を追加する
王様が取られていたらゲーム終了とするのではなく、手番と駒の利きと王手（チェック）の有無などの情報を駆使して現時点の局面が詰んでいる（チェックメイト状態）かどうかの判断を含めて評価関数内で評価するやり方です。王様（キング）が取られているかどうかだけを見て判断するより処理は複雑で重い処理になります。こういう場合は先手勝ち、こういう場合は王手放置で後手負け、こういう場合はステイルメイトで引き分け、と評価関数内でいちいち定義していくのでif文、case文だらけになり重たい処理になります。でも、その分先読みの深さを一手から二手省略できるのでメリットも大きいです。
じつは以前にも将棋アプリで思考時間短縮になるかと思い試してみたことがあったのですが、思ったほど効果が上がらなかったのでリリース版には採用しませんでした。それに一つ一つのケースについて勝ち負けの判定をするので漏れが生じてバグが発生し易いのも採用を見送った理由です。
あと、この方法で作ると王様を取る以前の段階で評価しますので、ユーザーに相手玉を取るところまで指し手を進めさせることが出来なくなりますが、チェスの場合もチェックメイト（詰み）の段階でゲームを終えるのが一般的なようなので問題ないと思います。
方法２：一定条件下で追加で先読みする
王様（キング）を二つ持っていれば勝ちという評価関数は変更せずに、先読みの過程でキングがチェックされていなくてキングを動かせない局面の場合には指定されている先読みの深さを無視して、さらに一手余計に先読みするという方法です。以前の記事に書いた打ち歩詰めチェックの方法と同じです。ステイルメイトの局面である可能性がある時は、先読み時に指定する何手先まで読むかを制限する引数を無視してさらに一手読むようにするところがミソです。打ち歩詰めと違って２手読む必要はなく、次にキングが取られるかどうかだけを見ればいいので追加で先読みするのは一手（チェス流に言えば0.5手読み）で済みます。打ち歩詰めチェックよりは楽だし、十分実績のある既存のコードなので新たなバグが発生する可能性も低いと思って、まずこの方法で実装しました。
このサイトによるとステイルメイトの定義は以下のようになっています。
- チェックされていない
- キング以外に動かせる駒がない。
- キングをどこに動かしても取られてしまう。（自殺行為でルール上そのようなマスには移動できない）
条件１．と３．は軽い処理で済みますが、２．の条件をチェックするには結局全ての駒の動きを調べる必要があるので、それをするぐらいならもう一手余分に先読みさせて済まそうという考え方です。条件１．と３．を満たす局面が現れた時だけ条件２．を調べて、勝ち（最大値）か負け（最小値）の評価値が返ってきたら評価値を強制的にDraw（評価値＝０）に変更するということです。打ち歩詰め対策の時は評価値に−1を掛けて打ち歩詰めをした方が負けになるようにしましたが、ステイルメイトの場合は評価が逆転するわけではないので０に置き換えるだけでいいと思います。←評価値０にするのは問題ありました、詳細は次の記事参照
とりあえず「方法２」で実装
例１：Bf6のステイルメイトを避ける
（クリックで画像拡大）
前回の記事で挙げた例ではとりあえずステイルメイトを避けるようになりました。但しNf7（Knightをf7に移動する手）がこの局面での最善手かどうかは分かりません。
例２：c8=Qのステイルメイトを避ける
（クリックで画像拡大）
修正前はポーンがc8に移動してQueenに成っていた（＝ステイルメイト）のですが、修正後はBishopに成ってステイルメイトを避けるようになりました。以下Kb8,Qb7と進んでチェックメイトで白の勝ちです。
打ち歩詰めやステイルメイトの負担
以下のコードはgithubの将棋アプリの先読み探索部分のコードですが、全コードの２５％（青い部分）が打ち歩詰めチェックのためだけのコードになっています。今回のチェスプログラムのコードも同様にステイルメイトチェックのために随分プログラムのレスポンスが悪くなってしまいました。仕方がないこととは言えこの特殊なルールのためにパフォーマンスが低下してしまいます。
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])
今回は方法２でステイルメイト対策をしましたが、方法１のやり方も検討中です。
ステイルメイトも打ち歩詰めもゲームを面白くする要素かも
チェスプログラムのテストをしている際に「引き分けがチェスを面白くしている」という意見を見かけました（質問１に対する回答）。
前回の記事でステイルメイトは合理的でないと貶しましたが、いろいろなケースをテストしている内に「ステイルメイト（引き分け）がチェスを面白くしている」という意見の意味が少し分かってきました。将棋の打ち歩詰め同様ゲームを面白くしている要素なのかもしれません。