局面の難易度




#1の局面と#169の局面を比較して#169の方がやはり難しそうだという判断ができる指標が作れないだろうか?難しさにはいろいろな要因(解く人のスキルなども含めて)が含まれているので本質的には無理すじと思っているが、ひとつの側面として目安程度の尺度を考えられないだろうか?

ここでは、局面の配置から得られる情報をもとにして2つの指標を提案してみます。(遊びですから気楽に見てください)


DR0 : Difficulty Rank 0

直感的に、”A”のカードは手前にあった方が易しいし、”K”のカードはなるべく奥の方にいてほしいという事を基準にした指標です。

A のカードは、カードの位置が各カラムの手前の方から奥に向かって1、2、...、7と順位をつける。
K のカードは、カードの位置が各カラムの奥の方から手前に向かって1、2、...、7と順位をつける。

この順位をもとに 以下の定義よりDR0を求める。


DR 0 = Σ(Aのカードの順位) + Σ(Kのカードの順位)

たとえば、#1の局面では、

1S (スペードのエース) KS (スペードのキング)
1C (クラブのエース) KC (クラブのキング)
1H (ハートのエース) KH (ハートのキング)
1D (ダイヤのエース) KD (ダイヤのキング)


となるので、DR 0(#1) = 25 です。 同様に、#169のDR0(#169)=42となります。

そして、DR0(#1) << DR(#169) なので、#169のほうが難しそうだと判定します。



DR 1: Difficulty Rank 1


DR1は、展開可能な局面の数に着目したちょっと複雑な定義です。
初期局面から、最終局面までに選択可能なすべての局面の集合を考え、これを以下のようにクラス分けします。

(1) 初期局面からm枚のカードを除いた局面をA(m)とします。

(2) A(m)に対して、取り除いたm枚のカードを、(手順は別にして)フリーセルの規約に合う形で配置できるとき、これをB(m)とする。配置の方法が複数ある場合も1つのB(m)で代表することとする。

(3) B(m)が存在mし、かつ、その親B(m−1)も存在するようなB(m)をM(m)とする。

M(m)の数が局面の選択枝の広さを表していると考え、以下のようにDR1を定義する。
(A(m)は自由な局面の数であり、M(m)がそれからどれだけ縮小しているかを平均値でみる)


DR1 = Σ{log2(#A(m)/#M(m)}/n*100

ただし、 Σは m=1〜nの和 (nは通常20)
#A(m), #M(m)は それぞれA(m),M(m)の数


なお、M(m)を求めるアルゴリズムに興味がある方は、こちら(deepgreen)にご連絡ください。
(細かな話なので、公開はしないつもりです)

#1を使用した A(m),B(m)の具体例

 例の見方は#1の局面と照合してください(時計周りに90度回転しただけ)

(0)#1の初期局面

  Home:  **  **  **  **       FC  :
  B1 :   6s  6d  3s  4c  2s  kd  jd
  B2 :   9c  8s  0d  5c  ks  kc  2d
  B3 :   2h  8d  4s  0s  9d  9s  9h
  B4 :   6h  qs  0h  qh  qd  5s  jc
  B5 :   6c  8h  4h  js  1d  5d
  B6 :   3d  2c  1c  1s  qc  7h
  B7 :   8c  jh  4d  1h  kh  7c
  B8 :   0c  7d  7s  3c  3h  5h


(1)A(5)の例 : B(5)を作れる場合
      6s  6d  3s  4c  2s の5枚を除いた局面
   
  Home:  **  **  **  **       FC  :
  B1 :   kd  jd
  B2 :   9c  8s  0d  5c  ks  kc  2d
  B3 :   2h  8d  4s  0s  9d  9s  9h
  B4 :   6h  qs  0h  qh  qd  5s  jc
  B5 :   6c  8h  4h  js  1d  5d
  B6 :   3d  2c  1c  1s  qc  7h
  B7 :   8c  jh  4d  1h  kh  7c
  B8 :   0c  7d  7s  3c  3h  5h


(2)B(5)の例:上記の5枚を配置する以下のように配置
      4枚をFCに、2sをB6に配置できる

  Home:  **  **  **  **       FC  : 6s  6d  3s  4c  
  B1 :   kd  jd
  B2 :   9c  8s  0d  5c  ks  kc  2d
  B3 :   2h  8d  4s  0s  9d  9s  9h
  B4 :   6h  qs  0h  qh  qd  5s  jc
  B5 :   6c  8h  4h  js  1d  5d
  B6 :   2s  3d  2c  1c  1s  qc  7h
  B7 :   8c  jh  4d  1h  kh  7c
  B8 :   0c  7d  7s  3c  3h  5h


(3)A(5)の例 :B(5)が作れない場合
      6h  qs  0h  qh  qd の5枚を除いた局面
  
  Home:  **  **  **  **       FC  :
  B1 :   6s  6d  3s  4c  2s  kd  jd
  B2 :   9c  8s  0d  5c  ks  kc  2d
  B3 :   2h  8d  4s  0s  9d  9s  9h
  B4 :   5s  jc
  B5 :   6c  8h  4h  js  1d  5d
  B6 :   3d  2c  1c  1s  qc  7h
  B7 :   8c  jh  4d  1h  kh  7c
  B8 :   0c  7d  7s  3c  3h  5h
   


DR1(#1) vs DR1(#169) (added 98.11.13)

#1,#169のDR1は、293,491となる。 DR0と同様に、DR1(#1)<<DR1(#169)となり、#169が難しそうという判定となる。

さらに、DR1の差200の意味するものは?

DR1の定義より、

DR1(#169)−DR1(#1) = Σ{log2(#M(m,#1)/#M(m,#169)}/n*100


となるので、#M(m,#1)/#M(m,#169)=2**(200/100)=4

すなわち、#1に比べて#169の方が、各ステップ(m)で約4倍も局面が狭いことになる。


DR0,DR1の分布


DR0,DR1はどの程度 難しさを捉えているのだろうか?

DR0,DR1の実際の分布を調べると、以下のようなグラフとなった。 ここで、標準分布とは、23001から23200の200個を代表に選んだ。難解ナンバとは、FreeCell#1941の難解ナンバリストにあるものである。

あきらかに、標準分布と難解ナンバでは、分布が別であること、DR0よりDR1の乖離の方が大きいことがわかる。




標準分布の5%(DR1が401以上)に難解ナンバの50%以上がふくまれる。
標準分布の16%(DR1が301以上)までとると、難解ナンバの75%まで含まれる。


Home
Up
Next