歌舞伎座.tech#4「コンピュータ将棋プログラミング」 参加メモ
コンピュータ将棋の歴史と基本アルゴリズム (瀧澤 武信氏 (コンピュータ将棋協会会長))
コンピュータ将棋の基本技術
- min-max原理
- alpha-beta法
- 木の並び方によって読むノードを減らせる
その他の技術
- 反復深化
- トランスポジションテーブル
- Futility枝刈り、null-move枝刈り
- singular拡張
- 静止探索（捕獲探索）
- 証明数探索（詰め将棋の研究で得られた）
他分野への応用が期待されるアルゴリズム
Bonanza のヒューリスティック探索法：前向き枝かりと勝利の三角形 (保木 邦仁氏 (Bonanza開発者))
Minmax探索の効率化 (前向き枝刈り)
- 前向き枝刈法(1)：Extended Futility枝刈り
- 有望な手を浅い探索 -> 評価値が変わらないようなら他の手を枝刈り
- 前向き枝刈法(2)：Late Move Reduction法
- 有望な手を深い探索 -> 他の手を浅い探索 -> いい手が見つかれば深い探索
- 前向き枝刈法(3)：Null move枝刈
- 有望な手を深い探索 -> 相手の手をパスさせて浅い探索をする -> 評価値が上がらなければ枝刈り
将棋の局面評価法
- 玉を含む3駒全通りに対する値付け（勝利の三角形）
- 評価関数自動学習の問題点
- 局面評価の精度で人間を超えることができない
- 棋譜に現れにくい局面の特徴を学習できない
Magic Bitboardとはなにか？ (山本 一成氏 (Ponanza開発者))
将棋プログラムに大切なこと
- 正確な評価関数？
- 精密な探索技術？
- > ただただ速く!! １局面でも多く探索したい
- いかに速い将棋プログラムを作るか
Bitboardとは
- 1マスを1ビットとして表現する
- 81マスの将棋を81ビットで表現
- 敵駒の効きの判定
- 自分の駒の効きのBB と 敵駒のBB のAND演算によって自分の駒でとれる相手の駒の座標が分かる
- メリット
- 条件分岐がなくなる
- ビット演算で同時にできる
Magic Bitboard
- MagicNumberを使うからMagic Bitboard
- Chessは64bit変数だから掛け算ができるが将棋は64bit×2が必要
- Bitboardのレイアウト
- 8,9筋で1つの64bit変数、1〜7筋で1つの64bit変数と分けるのがキモ
- BitboardのTips
- 歩の移動の算出
- 1bitシフトで算出可能
- 歩の移動の算出
- SSEと将棋プログラム
- SSE(Streaming SIMD Extensions)：128bitの変数みたいなもの
- 32bit変数×3の演算が128bitの変数みたいなものの演算一発ですむ
参考文献
コンピュータ囲碁の仕組み 〜将棋との違い〜 (山下 宏氏 (YSS開発者))
ある局面で乱数で最後まで打ってみるという試行を繰り返す
-> その局面はどちらが優勢かが分かる
- シミュレーション＝評価関数
- 将棋・・・評価関数の正確さ
- 囲碁・・・シミュレーションの正確さ
- 囲碁の木探索
- 着手候補からシミュレーションを行う。開始局面から最終局面へ、を何度も繰り返す。
- モンテカルロ法 + 木探索は応用範囲が広い
- ルールだけの実装で評価関数を作れる
- 多人数ゲームでもリアルタイムゲームでも使える
習甦における非線形評価関数と確率モデル (竹内 章氏 (習甦開発者))
- 習甦の評価関数群
- 玉の安全度（先手/後手）
-
- 駒の現在価値（先手/後手）
- 駒の潜在価値（先手/後手）
- 2駒間の位置評価
- ProbCut by M.Buro
- 浅い探索の結果を用いて深い探索の評価値の確率分布を予測し、一定以上の確率で結果に影響がない指し手を枝刈りする手法
