将棋プログラム「激指」
鶴岡 慶雅
概要
ゲーム研究と将棋プログラム
 実際の将棋プログラムの中身

 探索アルゴリズム
 指し手生成
 評価関数

展望
コンピュータ将棋選手権
コンピュータ将棋選手権
コンピュータ将棋選手権
コンピュータ将棋選手権
ゲームプログラムの現状

チェス
 1997年 Deep Blue (IBM)
 Deep Blue の2勝1敗3分

オセロ
 1997年 Logistello vs
 Logistello の6勝0敗

将棋
 アマ5段

vs カスパロフ
囲碁
 アマ初段(?)
村上健
コンピュータ将棋

チェス





取った駒は使えない
終盤になるほど盤上の駒が減るので branching factor が減少
全幅探索でもかなり強いプログラムが作れる
収束 ⇒ 終盤データベース
将棋




取った駒を持ち駒としていつでも使える
中終盤になると盤上の駒は減るが持ち駒が増えるのでbranching
factor が増大
全幅探索では全然だめ
収束しない
激指 Overview




言語
開発OS
探索法
探索速度
: C++ (約25000行)
: Linux
: 実現確率打ち切り
: 10~15万 node / sec
5~10万 leaves / sec
(AthlonXP 2000)
データ構造
将棋盤
駒
 きき
角

直接きいている駒
 間接的にきいている駒
 近距離・遠距離

 ピン
金 歩
桂
玉
香
探索アルゴリズム

実現確率打ち切り
 局面の実現確率を探索打ち切り条件とする
 (実現確率)=(直前の局面の実現確率)x(遷移確率)
1.0
0.5
0.3
0.5
0.7
0.35
0.3
0.2
0.1
遷移確率
0.5
0.15
実現確率
遷移確率

指し手のカテゴリに基づいて決定
カテゴリ
駒得で取り返す
駒得で駒を取る
駒得で王手をかける
飛車が成る
角が成る
:
遷移確率
58~89%
16~42%
43%
21%
20%
:
探索の振る舞い
取り返しなどの手順が続く局面は深く読む
 駒をただで取られるような手順は深く読まれ
ない


ありそうな展開を中心に読むため、トリッキー
な手の見落としの危険はあるが、資源配分の
効率化の効果の方が大きい
指し手生成

カテゴリごとに生成
 「ある升目へ移動する手」等の
primitive を組み
合わせて生成

可能な指し手を差分更新する方法もあるが、
そうすると指し手のカテゴリを判別する処理
が重くなる
探索の深さ
中盤の局面で約1分探索
3500000
3000000
2500000
ノード数

2000000
1500000
1000000
500000
0
1
2
3
4
5
6
7
8
9
10
11
12
深さ
13
14
15
16
17
18
19
20
21
22
評価関数
駒の損得
 駒の働き

 相手玉および自玉に近いほどプラス

玉の危険度
 相手玉の周辺に自分のききがあるほどプラス

序盤の駒組み
 悪形はマイナス、など、
駒の損得

駒の価値
参考) TD法による学習(飯田2002)
駒種
価値
駒種
価値
駒種
価値
駒種
価値
王
∞
竜
1300
王
∞
竜
1535
飛
950
馬
1150
飛
943
馬
1196
角
800
成銀
600
角
675
成銀
481
金
600
成桂
600
金
570
成桂
443
銀
550
成香
600
銀
492
成香
284
桂
400
と
600
桂
223
と
586
香
400
香
196
歩
100
歩
100
だいたいききの数の比例?
駒の働き
序盤は駒の損得だけ考えていればよい
 終盤は「駒の損得より速度」

 どうでもいい駒を取りにいっている間に自分の玉
が追い詰められる
⇒ コンピュータの典型的な負けパターン

駒の働きを考える必要
駒の働きの計算
盤面の進行度を0~100%の数値で評価
 進行度に応じて位置の評価を重く
 進行度はルートノードだけで判断するべき
か?

 探索結果の評価値の一貫性がなくなる
 局面が急激に変化するときにまずい
局面の進行度

序盤~終盤を、0~128の数値で表現
駒種
重み
段
重み
王
15
1
4
飛
10
2
4
角
7
3
4
金
8
4
3
銀
7
5
2
桂
5
6
1
香
5
7
0
歩
2
8
0
9
0
重要な駒が敵陣に近づいて
いるほど終盤に近い
(進行度)
=Σ(駒の重み)x(段の重み)
駒の働き
• 敵玉に対する働き
39
46
54
66
88
120
150
150
110
97
70
50
31
15
7
3
0
37
44
50
62
84
110
140
140
110
89
62
39
19
7
0
0
0
35
39
48
57
80
100
115
120
107
78
46
31
15
7
0
0
0
34
36
45
50
62
74
78
74
65
48
35
15
7
0
0
0
0
28
35
42
46
50
52
54
50
46
31
23
7
3
0
0
0
0
15
19
27
31
32
34
35
32
31
23
19
11
5
0
0
0
0
9
11
15
19
23
31
29
27
23
19
11
7
3
0
0
0
0
3
5
9
14
19
25
25
25
15
7
3
0
0
0
0
0
0
• 自玉に対する働き
3
4
6
11
15
19
23
19
7
0
0
0
0
0
0
0
0
23 21
27 25
31 28
39 36
54 53
80 80
95 98
113 112
120 110
100 105
90 85
64 60
39 35
27 19
19 11
11
7
7
0
21
25
26
34
50
70
84
92
92
88
76
46
31
15
7
0
0
20
23
26
31
42
55
65
65
65
62
46
35
21
11
5
0
0
17
17
19
27
31
39
42
42
42
39
27
19
7
0
0
0
0
7
10
12
15
17
19
23
23
23
19
15
7
0
0
0
0
0
3
4
5
6
6
7
9
9
9
8
6
1
0
0
0
0
0
0
0
0
1
1
1
2
2
2
2
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
駒の働き(例)
敵玉に対する働き
玉

位置の評価 140%
進行度
85%
金
(1.4  1.0)  0.85  0.34
駒の価値が 34%UP!
序盤の駒組

よくある方法
 矢倉囲い、美濃囲いなどの形を覚えておく
 それらの形に近いほど評価値を高くする

激指では
 囲いの形は(ほとんど)知らない
 部分的な悪形を減点
探索と評価関数の関係
探索アルゴリズムによって最適な評価関数は
異なる
 探索の深さによっても異なる

 原則的には、探索が深いほど単純でよい
完全に探索できるのなら0か1
 1手しか探索できないなら非常に複雑な局面評価

詰めルーチン
王手の連続で相手玉を詰ます
 詰む手順が見つかれば勝ち
 それぞれのノードの先頭で呼ぶ
 残りの実現確率に応じて詰めルーチンの探
索ノード数の上限を設定
 アルゴリズム: PDS (長井1998)

 証明数と反証明数を用いた深さ優先探索
コンピュータ将棋の棋力

レーティング
 強さを数値化
参考) 段級位とレーティング(飯田2002)
レーティング
段級位
ソフトの達成年
 強い相手に勝つと
1400
アマ2級
1995年
大きく増える
 弱い相手に負ける
と大きく減る
1600
アマ初段
1996年
1800
アマ二段
1997年
2000
アマ三段
1999年
2200
アマ四段
2001年
2400
アマ六段
2600
プロ
2800
タイトル保持者
探索量と強さの関係
勝敗
勝率
レベル12 vs レベル11 167勝25敗8分 0.870
レベル11 vs レベル10 155勝38敗7分 0.803
レベル10 vs レベル9
165勝28敗7分 0.855
レベル9 vs レベル8
173勝21敗6分 0.892
レベル8 vs レベル7
182勝16敗2分 0.919
棋力の伸びの予想

自己対戦の結果から
 思考時間が2.5倍でレーティング200点上昇

コンピュータの速度向上
 5年で10倍

10年でレーティング1000点上昇?
 ちょっと楽観的すぎる
なぜ楽観的すぎるのか

Diminishing return
 コンピュータチェスでは、探索が深くなるほど、一
手深く探索する効果が減少していく

自己対戦では勝率が過大になる
 理由
同じ探索アルゴリズム、評価関数を用いているため、
浅い方の探索が深い方に包含される
 評価関数の欠点が顕在化しない

高速化するための努力

盤面情報の更新の差分化
 駒を移動したときのききの更新など

評価関数を差分化
 駒の損得と働きに関しては完全に差分化
 他の細かいところは差分化が大変
並列化
 プロファイラで重い所を探す

どの処理に時間がかかっている
か?
処理
割合
局面評価
28%
駒の移動
22%
指し手生成
16%
詰みチェック
15%
仮評価
10%
:
:
並列化

αβ法
 探索結果を利用して
window を狭めていく
 sequential に実行するのが最も効率的
 もともと並列化には適さない

それでも無理やり並列化すると
 Opteron
Dual で約1.5倍の速度向上
プログラムの改良・修正

やみくもにプログラムを変更するのは危険
 バグが入るかも?
 強くしたつもりが弱くなってるかも?
序盤の500局面をプロの実戦譜から抽出
 変更のたびに1000局(先後入れ替え)対戦

 変更前
vs 変更後
 520勝480敗なら強くなったと言えるのか?
統計的検定

帰無仮説
 「2つのプログラムは同じ強さである」
帰無仮説が正しいとして、観測データの尤度
(起きる確率)を求める
 尤度が小さければ帰無仮説を棄却

 「2つのプログラムは同じ強さであるとはいえな
い」
統計的検定

尤度
 ベルヌーイ試行なので二項分布
 正規分布で近似

対局数が1000回で、σ=15

530勝470敗なら、強くなったと言ってもいい
かも
展望
評価関数の自動学習
 大規模PCクラスタによる並列化
 上達のパートナーとしてのプログラム
 名人を超えるのはいつか?

評価関数の自動学習

TD法
 局面が進んだときの評価値の変化が少なくなる
ようにパラメータを調整していく

(評価値のグラフ)
名人を超えるのはいつか?

NHK人間講座「大局を観る」 米長邦雄 永世棋聖
「…さて、では将棋のトッププロとコンピュータではどうでしょ
うか。現在は人間のほうがずっと強いし、コンピュータ科
学が思いもかけない飛躍でもしなかぎり、少なくともあと1
00年は人間の力のほうが上でありつづけるだろうと、私
は思っています。
(中略)
この、手を渡したり、金を寄せたりといった微妙な駆け引
きがコンピュータは苦手です。というより、わからない。そ
れらは過去のデータや計算からは導き出せない微妙な、
ある意味では摩訶不思議な手なので、どう対応していい
かわからなくなってしまうのです。…」
強くなるだけではだめ?

将棋プログラムは強くなりすぎた
 1000人に一人しか勝てない

強さ以外に楽しめる要素
 「悪手」「好手」の指摘
 検討のツール
 指導対局
 棋風のシミュレーションによる仮想棋士
最大エントロピー法を
利用した棋譜集から
の指し手学習
鶴岡慶雅
大山名人はこの局面でどう指す?
後手番
正解 2五歩
激指の予測
2五歩(9.2%)
8四歩(7.3%)
4五歩(5.9%)
5三銀(5.4%)
:
指し手を確率的に予測

用途
 棋士の棋風を再現
 実現確率打ち切り探索の遷移確率
 探索の枝狩り/延長


:
方法
 大量の棋譜から確率モデルを利用して機械学習
最大エントロピー法による
機械学習

Log-linear model 素性の重み 素性関数
1
 F

qx   exp  i f i x 
Z
 i 1



2値分類: 「指される」 or 「指されない」
訓練データの尤度を最大化するようにパラメータ
(素性の重み)を決定
学習に利用する素性(特徴量)









指し手そのもの(移動元と移動先の座標、駒の種類)
駒の種類
駒の移動元の局所的な盤面情報(3x3)
駒の移動先の局所的な盤面情報(3x3)
駒の移動先に敵のききがあるかどうか
駒得をする手かどうか
直前に動いた駒を取り返す手かどうか
相手の飛車の位置と局所的な盤面情報の組み合わせ
:
学習

大山十五世名人の棋譜650局を分割
 訓練データ:
512局
 テストデータ:100局

中盤までの全ての局面(進行度40以内)にお
いて、可能な指し手を全て生成し、学習デー
タとする
指し手予測の正解率
順位
訓練データに
存在する局面
訓練データに
存在しない局面
計
1
77.7
35.3
46.9
2
91.0
49.4
60.8
3
95.5
58.0
68.2
4
98.5
63.8
73.2
5
99.1
69.1
77.3
6
99.4
73.3
80.4
7
99.8
76.8
83.1
8
99.8
79.4
84.9
9
99.9
82.2
87.0
10
99.9
84.6
88.8
※局面ごとに上位n個の
指し手を出力し、そ
の中に正解手が含ま
れているかどうかの
パーセンテージ
※訓練データ:512局

訓練データに存在し
ない局面でも3割以
上の確率で正解手を
当てている。
正解率と訓練データ量の関係
known
unknown
total
100
90
80
正解率(%)
70
60
50

40
30
20

10
0
10
100
訓練データ数(局数)
1000
訓練データは多けれ
ば多いほどよい
500局でもまだ不足
指し手予測の例
先手番
正解 1六歩
激指の予測
6六歩(25%)
6八銀(11%)
4七銀(10%)
3七銀(9%)
:
指し手予測の例
先手番
正解 4五歩
激指の予測
4五歩(70.1%)
5五歩(23.2%)
4五桂(6.4%)
2五歩(3.8%)
:
課題

予測精度
 学習に利用する特徴量をさらに工夫する
 訓練データを増やす

探索への利用
 実現確率打ち切りに適用

棋風の再現
 探索による結果とどう折り合いをつけるか
ダウンロード

激指の棋譜解説及び 実装について