【勉強会メモ】コンピュータ将棋【歌舞伎座tech】

勉強会情報

会場

株式会社ドワンゴ　歌舞伎座タワーF14セミナールーム

時間

2014/6/21 19:00-21:30

詳細

connpass - 歌舞伎座.tech#4「コンピュータ将棋プログラミング」

配信

ニコ生 - 歌舞伎座.tech#4「コンピュータ将棋プログラミング」

「コンピュータ将棋の歴史と基本アルゴリズム」　ー　瀧澤 武信（コンピュータ将棋協会会長）

これまでの戦績の説明

プエラアルファ

塚田９段：かつて非常に強かった。この時は最高に強いというわけではなかった（笑）
持将棋：必敗の形から

三浦 vs GPS

７五歩　同歩 ８四銀
珍しい形、プロでもさされるようになる

第三回

今回は事前にプロ側に貸出
今度は勝つだろうと思われていたが、１勝４敗

コンピュータ将棋の歴史

コンピュータの歴史とコンピュータチェスの歴史はほぼ同じ

• １９９７年　実力:アマ二段
  カスパロフに６局戦って勝ち越した
  今では普通のPCでもプロは勝てない

• ２００５年　アマ竜王戦ベスト１６ 実力:アマ五段
  TACOSが橋本７段に勝ちそうになった

コンピュータ将棋の基本技術

mini-max原理３０ノード（評価：１８ノード）
↓
α-β法 ２２ノード（評価:：１２ノード）
「カットされる」先を読まなくていい
↓
効率良い場合 １６ノード（評価：８ノード）
より短く、時には深く読める
並び方が勝負（今のコンピュータ将棋の関心事）

その他の技術

• 反復進化
• トランスポジションテーブル
• Futility枝刈り、null-move枝刈り
• singular拡張
• 静止探索（捕獲探索）
• 証明数探索（詰将棋の研究で得られた）

他分野への応用が期待されるアルゴリズム

• 実現確率探索（激指）
• 評価関数のパラメータの自動調整（Bonanza） 偏微分方程式を解く
• 並列探索（大規模クラスタ）（GPS）
• 合議（もんじゅ、あから２０１０） ※人間（棋士）だとうまくいかないが、コンピュータだと何故かうまくいく

質疑応答

合議が人間（棋士）だとうまくいかないが、コンピュータだと何故かうまくいくのはなぜか？

統一性がない。コンピュータは何故かうまくいく

何年ぐらい先に人間のトップに勝てるか？

• 今はトップ（森内さん、羽生さん）のレベルにはまだ到達していない
• ３年くらい経ったら同じくらいになっている。さらに３年たったら人間は勝てなくなるかも

棋風はどこから出てくるのか

元となる棋譜のどこを重点的に取るかで変わる

「Bonanza のヒューリスティック探索法：前向き枝かりと勝利の三角形」　ー　保木 邦仁（Bonanza開発者）

思考アルゴリズム概要

• ゲーム木探索
• 最善応手系列を計算すると次の一手が出る
• 将棋は平均して８０手（枝が８０本伸びる）
• どうすれば効率よく探索できるか？

mini-max探索の効率化

上記と同様

前向き枝刈り

part1（Extended Futility 枝刈り）

なんで上手くいくのかわからないが、経験的になぜか上手くいく
1. コマをとる手
2. 1.をもう少し探索（浅い探索）
3. 他は枝刈り

part2（Late Move Reduction法）

1. コマを取る手
2. 1.の深い探索
3. 他の手も一応浅い探索
4. いい手が見つかる
5. 4.をもう少し探索
6. 他は枝刈り

part3 （null move 枝刈り）

1. コマを取る手
2. 1.の深い探索
3. 他の手
4. パス(実際は将棋にパスはないが)
5. 浅い探索
6. 枝刈り

数値分析

アルファベータ、３種の前向き枝刈り、有効分岐因子は３程度
普通のノートパソコンで１秒程度の時間で、深さ８の全幅探索

評価関数の自動学習法

1. ルート局面
2. 子局面
3. プロ棋士の選択、コンピュータの選択に点数の偏りがあればプロ棋士の選択に近付けるように調整
4. 目的関数を設計して最適化していく

目的関数の特徴

• 複数の極小点を持つ
• 大局的極小点の方が合理的なコマ価値を持つ
• 偏導関数は連続でない
• 目的関数は連続

大規模な機械学習の成功

• 目的関数に含まれる階段型関数をなめらかな関数で近似
• 束縛条件付加による無限遠点の局所最適解除法
• 正則化による過学習の回避

王を含む３駒全通りに対する値付け

※図で説明してました

評価関数自動学習の問題点

• 局面評価の精度で人間を超えることが出来ない
• 探索の深さで改善（１０ミリ秒程度の時間で人間の１分程度の思考に到達）

まとめ

コンピュータチェスでは１９９７年力ずく探索の改良で人間に勝った
↓
将棋でもデータ処理の量が多ければ多いほど強くなるようになって来た

質疑応答

他のソフトとの類似はあるのか

他のソフトが公開してくれていないから分からない

何故Bonanzaは公開したか

お金持ちになれるのであれば、公開しなかった（笑）
あとは他のソフトも公開していた

勝利の三角形を評価する方法について

Bonanzaは３駒全通り力ずく
他のソフトは力ずくでないアルゴリズムを採用しているものもある

勝利の三角形はどこから着想を得られたのか

そんなに突拍子もないことではない
二つの組み合わせはすでに他のソフトやチェスでもあった
それを単純に三つにした
因みに四つはメモリに乗り切らない（笑）

「SIMDと将棋プログラム / Magic Bitboard」　ー　山本 一成（Ponanza開発者）

将棋プログラムにとって大事なこと

• 正確な評価関数？
• 精密な探索技術？
• そもそもコンピュータ将棋の強さの秘訣は上記二つをただただ速く読むこと
• 人間でもたかだか１秒で１局面

２倍速くなるとどれくらい強くなる？

Pona（２倍速） vs Pona
⇒勝率７割（楽観的に８割という人も）

羽生四冠の生涯勝率はおよそ７割
⇒Ponaを２倍速くできえれば羽生四冠に勝てる？（笑）

Bitboardとはなにか？

１マスを１ビットとして表現
８１マスの将棋では８１ビットで表現
unsigned long longが使えるので効率がよい

例）６六金の動きを算出

駒を取る手をいかに速く作るか
銀の動きのBB & 敵のBB = 取る動きのBB

それで何が嬉しいの？

• 条件分岐がなくなる
• ビットパラレル（平行して演算）

BB（Bitboard）

コンピュータ将棋にとって厄介な駒

香角飛馬竜
※盤面の形によって、どこまでいけるか決まるため

どうすればよいか？

単純な解決策、マスずつ数える->遅い
forループは遅い
「因みにプログラマーの方挙手」
↓
ノノノノノノノノ
↓
「ほとんどプログラマーじゃないですかｗ」

どうやって高速化するか

まずは香車で考える
BBのレイアウト（配置）を変えておく
関係するビット列に注目
右シフト１０&ビットマスクで取れそう

事前に計算して持っておけば一発で取れる
香の効きtbl［］［］

覚えてほしいこと

必要なBitの配置をハッシュキーにできればOK

チェス界のMagicBitboard（2006）とは？

掲示板で話が盛り上がって生まれた手法

将棋でもできたらいいな

チェスの駒位置
↓低コストな操作
文字列

そう言えば掛け算ってどんな演算だっけ？

６４ビット整数 * MagicNum = garbage
掛け算でBitを上位に移動

なんとか将棋でもMBBを使えないか

チェスは64bit変数だから掛け算ができるが、
将棋は64bit変数を二つ並べて擬似的に81bit変数に

MagicNumberをどう探すか？

乱数を使って取り敢えず試す（笑）
条件を満たせば採用

MagicNumberを探すのにどれくらい掛かるか？

１万回位乱数を使って見れば見つかる（笑）

角のMBBはすぐ見つかるが、飛車のMBBはなかなか見つからない

仕様メモリを増やせば解決

実用性など

PonanzaやAperyなど新しい将棋プログラムで普通に使われる

歩の移動の算出

1bitシフトで算出可能

SSE

128bitの変数みたいなもの
Shogi SIMD Extensions
ありがとうIntelの人
でも本当は81bit変数が良かったな。。。

質疑応答

Ponanzaの場合一手何分でさせば強いか？

検証が大変で、現状分からない

テーブルはCPUのキャッシュに乗るか？メモリに乗るか？

定かではないが、キャッシュには結構乗っているのではないかと期待

今回のBB以外に新しいアルゴリズムはあるか？

ソースコードとしての関係はない
が、影響は受けている

「コンピュータ囲碁の仕組み、将棋との比較」　ー　山下 宏（YSS開発者）

私について

「囲碁もつくっています。なので今日は囲碁です」

囲碁の局面評価

将棋と同じく直接変換

２００６年を堺に急激に棋力が伸びた

なにがあったか？

モンテカルロ法を用いたアルゴリズムを導入

モンテカルロ法を使った囲碁の仕組み

1. 乱数で交互に置く
2. 打てなくなるまで繰り返す
3. 評価する（１０００回中何回勝ったか）
4. どちらに良い局面だったかが分かる

シミュレーションの制度を上げる

囲碁知識を利用

• 辺りを逃げる、石を取る

プロの棋譜から着手確率を求める

単純乱数と囲碁っぽい乱数

シミュレーションが強さを決める

１手に１００００回のシミュレーション
純粋乱数　１５級
囲碁知識を利用　２段

囲碁の木探索

手を選択 -> シミュレーション -> 勝ち負け -> 勝った手の下に降りていく
開始曲面から終了局面を何度も繰り返す
250手中30手くらいしかよまない（読み抜けの危険）

現在の囲碁棋力

アマチュアの県代表レベル
将棋に比べて１０年遅れている

「習甦における非線形評価関数と確率モデル」　ー　竹内 章（習甦開発者）

局面の評価における非線形性

非線形な評価が必要と思われるケース

確率的な局面評価

習甦の評価関数群

• 入力：効き数
• 機器評価
• 駒の価値
• 評価値
• 安定度

関数の推定手順

連立方程式を解くプログラム例

分散がどう役に立つのか

ProbCut by M. Buro
オセロで使われていた枝刈りをする手法

まとめ

線形和による評価関数群
* 玉安全度
* 駒の現在価値
* 駒の潜在価値
↓
シグモイド関数
->玉面評価の期待値
多項式の近似
->局面評価の分散