整数計画法を用いた ペグソリティアの解法 ver. 2.1

Presentation on theme: "整数計画法を用いた ペグソリティアの解法 ver. 2.1"— Presentation transcript:

1 整数計画法を用いた ペグソリティアの解法 ver. 2.1
東京大学 清見 礼 東京大学 松井知己

2 ボード: ボード上には穴が有る 〇: 穴 例 配置: 各穴には最大1つのペグ ●：ペグの有る穴 ジャンプ: ●●〇→〇〇● ● 〇 〇 ●
Definitions ボード: ボード上には穴が有る 〇: 穴 例 配置: 各穴には最大1つのペグ ●：ペグの有る穴 ジャンプ: ●●〇→〇〇● ● 〇 〇 ● 〇●●→●〇〇 ●→〇 ●→〇 〇 ● ● 〇

3 Definitions (jump positions)
ジャンプ位置: ジャンプが起こる場所 38 種類の縦の ＋ 38 種類の横の ジャンプ 位置 ジャンプ位置 = 計 76 種類のジャンプ位置

4 与えられた問題: 開始配置 終了配置 解 ジャンプ列を（あれば）見つける. 存在しない際は ``無い’’と答える.
peg solitaire problem 与えられた問題: 開始配置 終了配置 解 ジャンプ列を（あれば）見つける. 存在しない際は ``無い’’と答える.

5 Berlekamp, Conway, Guy (1982):(Winning Ways) パゴダ関数を用いた必要条件
previous results 問題の複雑さ Uehara, Iwata (1990): ペグソリティア問題はNP-完全 解の存在性の必要条件 de Bruijn (1972): 有限体を用いた必要条件 Berlekamp, Conway, Guy (1982):(Winning Ways) パゴダ関数を用いた必要条件 (線形不等式系を用いたもの) Avis, Deza (1996): solitaire cone (多面体的アプローチ)

6 イギリス盤のペグソリティア問題を解く 解法の提案を行う. 主なアイデア: 通常の深さ優先探索 ＋ 探索空間の削減 整数計画法を用いる
our results イギリス盤のペグソリティア問題を解く 解法の提案を行う. 主なアイデア: 通常の深さ優先探索 ＋ 探索空間の削減 整数計画法を用いる

7 整数計画法を用いて，各ジャンプ位置での ジャンプ回数の上限を求める. 開始 終了 ∀解, この位置でのジャンプの回数 （ジャンプ回数） ≦1
upper bound 整数計画法を用いて，各ジャンプ位置での ジャンプ回数の上限を求める. 開始 終了 ∀解, この位置でのジャンプの回数 （ジャンプ回数） ≦1 右辺項 の値は きつい 上界

8 n: 穴の数 イギリス盤: n=33 配置ベクトル: n-次元 0‐1ベクトル ペグがあるとき1としたもの 1 2 3 4 5 6
notations 7 ･ ･ n: 穴の数 イギリス盤: n=33 配置ベクトル: n-次元 0‐1ベクトル ペグがあるとき1としたもの ･ ･ 27 1 ･ ∈{0,1}33 1: ペグ有り 0: ペグ無し

9 ジャンプベクトル ジャンプ = ジャンプベクトルを引く (ジャンプベクトルは2個の 1 と1個の -1) 1 1 1 ー -1 ー -1 ＝
jump vector ジャンプベクトル ジャンプ = ジャンプベクトルを引く (ジャンプベクトルは2個の 1 と1個の -1) 1 -1 1 1 1 -1 ー ー ＝

10 ⇔ p’=p - A uj (uj ：第j 単位ベクトル)
jump matrix ジャンプ行列: (穴の位置)×(ジャンプ位置) ジャンプ位置 1 ‐1 ‥‥‥ ‐1 0 1 1 ‥‥‥ A ＝ ‥‥‥ 0 0 ‥‥‥ 1 ‐1 0 0 ‥‥‥ 配置 p → 配置 p’ ジャンプ位置jでのジャンプ ⇔ p’=p - A uj (uj ：第j 単位ベクトル) 穴の位置

11 jump matrix and peg solitaire problem
ps: 開始配置の配置ベクトル. pf: 終了配置の配置ベクトル. 与えられたペグソリティア問題が解を持つなら, ∃x=(x1,x2,...,xm)Ｔ： (1) ジャンプ位置でインデックスされた 整数ベクトル (2) ps - Ax = pf xj : ジャンプ位置 j でのジャンプ回数

12 (2) (位置jでのジャンプ回数 )≦（ IPjの最適値) IPj の最適値は，ジャンプ位置jでの ジャンプ回数の上限. 提案する解法では，
integer programming IPj: max xj sub. to ps - Ax = pf , x≧0, x=(x1,x2,...,xm)Ｔ は整数ベクトル. (1) IPjs が許容解を持たない ⇒ ペグソリティア問題は解を持たない (2) (位置jでのジャンプ回数 )≦（ IPjの最適値) IPj の最適値は，ジャンプ位置jでの ジャンプ回数の上限. 提案する解法では， 各ジャンプ位置jに対し問題IPjを解く. ジャンプ位置76, 変数76, 制約式33

13 example of upper bounds
問題例: 76 問の整数計画を解く: 得られた上界: 1 2

14 example of infeasible peg solitaire problem
問題例: 76 問の整数計画: IPj は実行不能 ⇒ ペグソリティア問題は解を持たない 計算機実験によると， このチェック法は非常に強力.

15 pagoda function approach
Berlekamp, Conway, Guy (1982):(Winning Ways) パゴダ関数存在 ⇔∃y, yＴA≧0, yＴ(ps - pf ）＜0 ⇒ ペグソリティアも問題は解を持たない Farkas の補題 (1) と (2) のどちらかちょうど一方が成り立つ (1) ∃y, yＴA≧0, yＴ(ps - pf ）＜0, (2) ∃x, ps - Ax = pf , x≧0. IPj: max｛xj | ps - Ax = pf , x≧0, x∈Zn ｝ IPjによる解の非存在性判定はパゴダ関数による判定より強い．

16 example of infeasible peg solitaire problems (2)
問題例: 解無し! 76 問の整数計画は解を持つ 得られた上界 IP は実行不能 ⇒ ペグソリティアは解無し IP は実行不能 ペグソリティアは解無し 1 2

17 イギリス盤のペグソリティア問題を解く 解法の提案を行う. 主なアイデア: 通常の深さ優先探索 ＋ 探索空間の削減 整数計画法を用いる
algorithm イギリス盤のペグソリティア問題を解く 解法の提案を行う. 主なアイデア: 通常の深さ優先探索 ＋ 探索空間の削減 整数計画法を用いる

18 問題例: ゲーム木: スタート配置からの 全ての可能なジャンプ. 点: 配置 根: 開始配置. 子=親+ジャンプ 終了配置.
game tree 問題例: ゲーム木: スタート配置からの 全ての可能なジャンプ. 点: 配置 根: 開始配置. 子=親+ジャンプ 終了配置.

19 search of game tree ゲーム木上の 深さ優先探索 開始配置 終了配置

20 DFS+UB 深さ優先探索 ＋上界 開始配置 2 1 1 ジャンプ数 上界 ジャンプ 1 2 1 1 1 1 1 1 1 終了配置

21 DFS+UB 深さ優先探索 ＋上界 開始配置 探索範囲の削減 2 1 1 1 2 1 1 1 1 1 1 1 終了配置

22 ハッシュ：1回出現した配置を全て覚えておく． 計算効率が大幅にアップした．
hash table 同じ配置の探索を2度以上しないために, ハッシュを用いる. ハッシュサイズ: 2,000,000 ハッシュ：1回出現した配置を全て覚えておく． 計算効率が大幅にアップした．

23 前向き探索: 通常の深さ優先探索 前向き-後ろ向き探索: 終了配置 ハッシュ に記憶 開始配置 半分の高さの 逆ゲーム木 半分の高さの
search method 前向き探索: 通常の深さ優先探索 前向き-後ろ向き探索: 終了配置 半分の高さの 逆ゲーム木 ハッシュ に記憶 開始配置 半分の高さの ゲーム木

24 computational experience
MMX Pentium 233MHz with 64MB memory 問題 (i) 76 IPs: 9.1 sec. 前向き探索: 37 min. 前-後向き探索:1.4 sec. 問題 (ii) 76 IPs: 122 sec. 前向き探索: 3.0 sec. 前-後向き探索: hash overflow

25 END

26

27

28

29

30