スーパーパズにおける成功可能な局面と成功不可能な局面の分類
2
0
0
全文
(2) 情報処理学会第 75 回全国大会. 図 1，2 において手順はカードの交換として 表記しており、例えば (DK,D3) は DK の場所 (穴)に D3 を移動することを表す。 4． 成功可能な局面と成功不可能な局面 ある特定の局面から生成されるすべての局面 についてそれらの各々の局面が成功可能かどう かによって分類するアルゴリズムを次に示す。 0) 初期局面 t0 から生成可能な局面を深さ優先探 索によって生成していく。 1) 生成された局面は初期状態を「成功不可能」 とする。 2) 成功局面 s が見つかれば、s から t0 に至る道 P 上にある局面を「成功可能」とする。 3) ある局面 t から生成した子局面のなかに既に 「成功可能」となっているものがあれば、そ の局面 t を「成功可能」とし、t から t0 に至 る道 Q 上にあるすべての局面を「成功可能」 とする。 4) step2 と 3 を生成可能な局面がすべて生成さ れるまで続ける。 このアルゴリズムが正しく動作することは以 下のように証明できる。 t0 c. 至ったときに上記アルゴリズムの step2 を適用 し成功可能な局面を集計していく。また、ルー ル c) ① を適用すると左端に穴が複数個存在す る場合に元の局面に戻ることがあるので、同じ 局面を生成しないように工夫している。その際 など既に存在する成功可能な局面が生成された ときに上記アルゴリズムの step3 を適用して成 功可能な局面をさらに集計していく。全探索が 終了した時点で成功可能にならなかった局面は 成功不可能な局面である。表 1 に列数 4 から 8 の場合について疑似乱数を用いて生成した各々 1000 個の初期局面に対して計算を実行した結 果 を 示 す 。 な お 計 算 に は CPU が Opteron 6128 ( Dual ) で、主記憶の容量が 240GB のマ シンを用いた。 列数. 成功数. 4 5 6 7 8. 868 841 819 803 817. 成功可能な局面の割合 最小値 平均値 最大値 1.25% 60.01% 83.86% 1.16% 46.50% 90.40% 0.09% 34.85% 69.76% 0.04% 26.32% 71.29% 0.01% 18.16% 68.70%. 表 1 列数と成功可能な局面の割合の関係 この結果から、成功不可能な局面の割合は、 列数に対して平均値は単調に減少することと、 列数 8 の場合に 20％未満なのでフルサイズの 場合には 10％未満であることが予想できる。 図 2 の初期局面の場合では、全局面数 1,366,761,020 に 対 して成功可能な局面数は 73,288,067 であり、割合は 5.36％であった。. a b. s. 図 3. 成功局面に至る道. 6． あとがき. 本報告では、スーパーパズにおいて、ある特 図 3 のように step2 の道 P 上に局面 a と b 定の初期局面から深さ優先探索により全探索を があって、P 上にない局面 c から b にも枝があ 行って生成される局面の集合を成功可能かどう るとする。もし、c が a より先に生成されてい かによってふたつの部分集合に分割できること るとすると「深さ優先探索」の定義より t0 か を示した。これにより成功局面に至る解を導く ら c と b を結ぶ枝を通って s に至る P とは異な アルゴリズムあるいはヒューリスティックな方 る道 R が先に発見されることになる。しかし 法を考察するためのひとつのツールが得られた これは道 P が先に探索されていることと矛盾 と考えられる。そして実際に計算を実行して成 するので、c が a より先に生成されたものであ 功可能な局面の割合を確認した。 る こ とはあり得ない。従って c に対しては step 3 が適用されることになる。 文献 明らかに次の系が成り立つ。 (1) 南雲, bit Vol.23, No. 5, pp99-100, 共立出版（1991） 系 最初の成功局面 s0 が見つけられた時点では、 (2) 新谷,情報処理学会シンポジウム論文集 Vol.99, No.14, pp.84-91（1999） t0 から s0 に至る道上の節点のみが成功可能で あって、それ以外の節点は成功不可能である。 5． 計算方法と結果 文献(2)のプログラムにおいて、成功局面に. 2-22. Partition of States into Possible and Impossible in Superpuzz † Toshio Shintani ， Faculty of Engineering, Fukuyama University. Copyright 2013 Information Processing Society of Japan. All Rights Reserved..
(3)
関連したドキュメント
既存の尺度の構成概念をほぼ網羅する多面的な評価が可能と考えられた。SFS‑Yと既存の
攻撃者は安定して攻撃を成功させるためにメモリ空間 の固定領域に配置された ROPgadget コードを用いようとす る．2.4 節で示した ASLR が機能している場合は困難とな
前章 / 節からの流れで、計算可能な関数のもつ性質を抽象的に捉えることから始めよう。話を 単純にするために、以下では次のような型のプログラム を考える。 は部分関数 (
点から見たときに、 債務者に、 複数債権者の有する債権額を考慮することなく弁済することを可能にしているものとしては、
本論文での分析は、叙述関係の Subject であれば、 Predicate に対して分配される ことが可能というものである。そして o
とディグナーガが考えていると Pind は言うのである（このような見解はダルマキールティなら十分に 可能である）． Pind [1999:327]: “The underlying argument seems to be
（自分で感じられ得る［もの］）という用例は注目に値する（脚注 24 ）．接頭辞の sam は「正しい」と
「マネジメントモデル」の各分野における達成すべき目標と重要成功要因の策定を、CFAM（Corporate Functional Area
