【コンピュータ将棋】ゴルーチンでお手軽持ち時間管理＆並行探索

前書き

この記事は、
コンピュータ将棋 Advent Calendar 2016
http://www.adventar.org/calendars/1457
の12/5分の記事になります。

自己紹介

将棋ソフトHoneyWaffle開発者の渡辺です。
普段は仕事でJavaとかRubyでの開発をやっています。
ちょうど去年の今頃からGoの勉強とともにコンピュータ将棋の開発を始めました。

Go言語で将棋ソフトHoneyWaffleをスクラッチ開発し、
第4回将棋電王トーナメントに初参加しました。
予選リーグにて3勝5敗で35チーム中31位でした。
アマチュア級位者レベルの棋力の、いわゆるネタ勢です。

第4回将棋電王トーナメント PR文書[PDF注意!!!]
http://denou.jp/tournament2016/img/PR/HoneyWaffle.pdf

参戦レポ的なもの
http://shiroigohanp.tumblr.com/post/151659399414/%E7%AC%AC4%E5%9B%9E%E5%B0%86%E6%A3%8B%E9%9B%BB%E7%8E%8B%E3%83%88%E3%83%BC%E3%83%8A%E3%83%A1%E3%83%B3%E3%83%88-honeywaffle%E8%A6%96%E7%82%B9%E3%81%A0%E3%81%91%E3%81%AE%E3%81%BE%E3%81%A8%E3%82%81

この記事に書いていないこと

• Goの正確な理解、ベストプラクティス
• 機械学習
• 高度な最先端の探索
• C++等とのパフォーマンス比較

本文

持ち時間管理と並行探索について、ソースコードとともにざっくりと説明します。

持ち時間管理

将棋ソフトは、基本的にサーバ（や相手）から指定された持ち時間の範囲で、与えられた局面に対する指し手を返す必要があります。探索でいい手を発見できても、それを持ち時間以内に返せない場合、時間切れの負けとなってしまいます。そこで持ち時間管理が必要になります。

Goでは、通常の関数の前にgoとつけてやるだけで、非同期で（ゴルーチン上で）実行されるようになります。（★）

以下のコードでは、player.search（指し手の検索ロジック）を非同期で実行するよう呼び出し、後段のselectのブロックでその結果を待ち受けます。
※Go 1.7からはこのような実装はchannelではなくcontextを使うとシンプルに書けるかと思います。

main.go(139)

    // mainでの時間管理
    main_timer := time.NewTimer(time.Duration(available_ms) * time.Millisecond)
    // 指し手の取得用
    result_ch := make(chan SearchResult)
    // goroutine停止用
    stop_ch := make(chan string)

    go player.search(result_ch, stop_ch, available_ms) // ★非同期で実行される

    select { // 待ちに入り、先にchannelから値が出てきた方のcaseの処理だけ実行される
    case result := <-result_ch:
        usiResponseBy(result)
    case <-main_timer.C:
        close(stop_ch)
        result := <-result_ch
        usiResponseBy(result)
    }

selectのブロックでは、指し手の検索ロジックに渡しておいた、指し手の取得用channelのresult_chから指し手が返されるのを待っています。一方、時間切れに備えてmain_timerもセットしてあります。main_timerに渡す時間（available_ms）には、ギリギリ一杯の時間ではなく、若干のバッファを加味した時間を設定します。

• 時間内に指し手が返ってきた場合、その指し手をサーバに返す（usiResponseBy）
• 時間内に指し手が返ってこない場合、指し手の探索ロジックに渡したstop_chをcloseすることで、指し手の催促をし、その指し手をサーバに返す

という動作になります。
他の言語ならばforとかの無限ループで、一定時間間隔で時間が過ぎていないか？とかチェックするような実装になるかと思いますが、Goならこのように条件が明確になります。

探索ロジック側でも同様にタイマーで持ち時間管理をしています。
読みを深めるごとに現在の指し手候補はキープしており、持ち時間内に探索が完了した場合はそれを返しますが、基本的にはmainから渡されたstop_chがcloseされるまで、読みの深さを増やしながら探索を繰り返します。

並行探索

現在の将棋ソフトでは、マルチコアCPUを活用するために、複数スレッドで並行して探索するのが一般的だと思います。局面が与えられたら、まずその局面で可能な指し手を生成し、それぞれの指し手を複数スレッドで分担して並行して探索（読みを深める）をします。

現局面から生成した指し手move1つ1つについて、自殺手ではないかどうかのチェックと、1手進めた局面を評価する関数checkAndEvaluateを、 goをつけてゴルーチンで実行させています。（★）次のforブロックでその結果を全部待っているので一見非同期で実行する意味がないように思えますが、Goをマルチコアで動かす設定にしておけばそのコア数分並列で実行されるはずです。（はずですというのは、将棋電王トーナメントの実戦では、バグによりシングルコアでしか動かせていないため）

変数名がローマ字と英単語で混ざっていますが気にしないでください。

player.go(192)

    move_ch := make(chan Record)
    // 全部の手の自殺手チェックをし、評価を出す
    for _, move := range moves.moves_map {
        go checkAndEvaluate(move_ch, base_sfen, move, teban) //★
    }
    for i := 0; i < moves.count(); i++ {
        // 上記goroutineの結果待ち
        record := <-move_ch
        // (略)
    }

余談ですが、ある指し手が反則かどうかについては比較的複雑なチェックが必要になります。もともと動かせない指し手（歩が横移動するとか）、味方の駒がいるマスに動かす手、王を相手の駒の利いているマスに動かす手、二歩を打つ、行き所のない駒を打つ等、反則の種類によってどのタイミングでチェックするかがパフォーマンスや実装に影響してきます。

参考文献

みんなのGo言語
http://gihyo.jp/book/2016/978-4-7741-8392-3
Goをやるなら買う一手。

ソース

本当に暇を持て余した人やどうしてもC++だけは一瞥もしたくない人向け。
https://github.com/32hiko/honey_waffle

最後に

ここまで読んでいただき、ありがとうございました。

/*
叡王戦の第1局はニコファーレで観戦していました。
すごい将棋だったけど千田さんが勝てず、残念。
*/