ゲーム解析のお願い

 投稿者：GAI  投稿日：2010年 1月27日(水)11時42分43秒
  ５２枚のカードから任意の１３枚を抜き出すと、必ず４枚の同じマークのカードが含まれるようになるので、この４枚だけが表向きで終了するような作品を作りたい。
表にしたいカードの位置として考えられる全パターンが13C4＝715通り考えられ、これらがすべて可能であるのか知りたい。

＜１３枚のパケットの操作方法＞
裏向きに持ち、上から任意の枚数でひっくり返しパケットに戻す。
この操作を何回かくり返していき、目的の４枚だけが表向きになっている状態にする。

パケットの上から持ち上げる枚数と最終表のカード（*)の例

4枚
1        *4
2        *3
3        *2
4        *1
5         5
6         6
7         7
8         8
9         9
10       10
11       11
12       12
13       13


6枚　　 3枚　　　4枚　　　9枚
1       *6        4        3        *9
2       *5        5       *6        *8
3       *4        6       *5        *7
4       *3       *3       *4         1
5       *2       *2       *2         2
6       *1       *1       *1         4
7        7        7        7         5
8        8        8        8         6
9        9        9        9        *3
10       10       10       10        10
11       11       11       11        11
12       12       12       12        12
13       13       13       13        13

最終パターンを達成するための持ち上げる枚数の戦略を知りたい。 		 

Re: ゲーム解析のお願い

 投稿者：山中和義  投稿日：2010年 1月27日(水)16時11分19秒
  > No.993[元記事へ]

GAIさんへのお返事です。

例
　1,2,3,4,5,6,7,8,9,10,11,12,13
　　　↓
　-9,-8,-7,1,2,4,5,6,-3,10,11,12,13

　枚数列{6,3,4,9}の４手が最少手数のようです。

LET t0=TIME


PUBLIC NUMERIC N !カードの枚数
LET N=13

DIM c(N) !最初のパターン　※
DATA 1,2,3,4,5,6,7,8,9,10,11,12,13
MAT READ c

PUBLIC NUMERIC GOAL(100) !最終のパターン　※
MAT GOAL=ZER(N)
DATA -9,-8,-7,1,2,4,5,6,-3,10,11,12,13
MAT READ GOAL

PUBLIC NUMERIC LIMIT !手数の上限　※
LET LIMIT=10

DIM A(LIMIT) !枚数
CALL backtrack(c,1,A)


PRINT "計算時間=";TIME-t0

END


EXTERNAL SUB reverse(c(),P) !先頭からP枚を裏返す
FOR i=1 TO INT(P/2) !交換
   LET t=c(i)
   LET c(i)=c(P-i+1)
   LET c(P-i+1)=t
NEXT i
FOR i=1 TO P !反転
   LET c(i)=-c(i)
NEXT i
END SUB

EXTERNAL SUB backtrack(c(),K,A()) !バックトラック法で検証する
IF K<=LIMIT THEN !手数の上限内なら
   DIM x(N)
   MAT x=c !save it

   FOR i=1 TO N !枚数を変える
      LET A(K)=i
      CALL reverse(c,i) !反転

      FOR j=1 TO N !最終のパターンかどうか確認する
         IF c(j)<>GOAL(j) THEN EXIT FOR
      NEXT j
      IF j>N THEN !一致したら
         LET LIMIT=K-1 !上限を狭める　※最初に見つかったもの
         PRINT K;"手"
         FOR j=1 TO K
            PRINT A(j); !枚数
         NEXT j
         PRINT
         !!!MAT PRINT c; !debug
      ELSE
         CALL backtrack(c,K+1,A) !次へ
      END IF

      MAT c=x !restore it
   NEXT i
END IF
END SUB
 

Re: ゲーム解析のお願い

 投稿者：GAI  投稿日：2010年 1月27日(水)19時12分53秒
  > No.994[元記事へ]

山中和義さんへのお返事です。

さっそく作って頂きありがとうございます。
自分で少し変更してみようと試みましたが、迷路に入り再びお願いがあります。

カードを任意の枚数でひっくり返していくとき、表が４枚になったならカードの配列を表示し（最終パターンに相当するもの。）
そこまでの、持ち上げる枚数を同時に見てみたい。


この表が４枚となるあらゆるパターン（最初の何番目のカードが表かでの違いについての）は調べることは出来ますか？ 		 

Re: ゲーム解析のお願い

 投稿者：山中和義  投稿日：2010年 1月27日(水)20時26分9秒
  > No.995[元記事へ]

GAIさんへのお返事です。
LET t0=TIME


PUBLIC NUMERIC N !カードの枚数
LET N=13

DIM c(N) !最初のパターン　※
DATA 1,2,3,4,5,6,7,8,9,10,11,12,13
MAT READ c

PUBLIC NUMERIC LIMIT !手数の上限　※
LET LIMIT=4

PUBLIC NUMERIC cMIN !最少手数
LET cMIN=LIMIT+1

DIM A(LIMIT) !枚数
CALL backtrack(c,0,A)

IF cMIN<=LIMIT THEN PRINT "最少手数=";cMIN


PRINT "計算時間=";TIME-t0

END


EXTERNAL SUB reverse(c(),P) !先頭からP枚を裏返す
FOR i=1 TO INT(P/2) !交換
   LET t=c(i)
   LET c(i)=c(P-i+1)
   LET c(P-i+1)=t
NEXT i
FOR i=1 TO P !反転
   LET c(i)=-c(i)
NEXT i
END SUB

EXTERNAL SUB backtrack(c(),K,A()) !バックトラック法で検証する
LET s=0
FOR j=1 TO N !表の枚数を確認する
   IF c(j)<0 THEN LET s=s+1
NEXT j
IF s=4 THEN !一致したら
   IF K<cMIN THEN LET cMIN=K !最少手数を記録する
   PRINT K;"手"
   FOR j=1 TO K
      PRINT A(j); !枚数列
   NEXT j
   PRINT
   MAT PRINT c; !最終のパターン
ELSE
   IF K<LIMIT THEN !手数の上限内なら
      DIM x(N)
      MAT x=c !save it

      FOR i=1 TO N !枚数を変える
         IF K>=1 AND i=A(K) THEN !同じ手が続く場合は無効！
         ELSE
            LET A(K+1)=i
            CALL reverse(c,i) !反転

            CALL backtrack(c,K+1,A) !次へ

            MAT c=x !restore it
         END IF
      NEXT i
   END IF
END IF
END SUB
 

戻る