反復深化法について

 投稿者:山路 武雄  投稿日:2010年 9月14日(火)17時57分9秒
  十進Basicでオセロのプログラムを作っているのですが、
反復深化法を取り入れたいのですがどのように作ればよいのか教えていただけないでしょうか。
 

Re: 反復深化法について

 投稿者:山中和義  投稿日:2010年 9月15日(水)11時48分39秒
  > No.1386[元記事へ]

山路 武雄さんへのお返事です。

前提条件(盤面の表現、評価など)がありませんので、勝ってに設定してみました。

n手先を表示するプログラム
!オセロ

DIM CEL(8,8) !配置情報

!局面を初期化する
FOR i=1 TO 8
   FOR j=1 TO 8
      LET CEL(i,j)=0 !置いてない状態
   NEXT j
NEXT i
LET CEL(4,4)=1 !白中央
LET CEL(5,5)=1
LET CEL(4,5)=-1 !黒中央
LET CEL(5,4)=-1

CALL plot_now(CEL, stn)
PRINT

DIM S(60) !手の記録

LET stn=-1 !黒先手
CALL try(CEL,0,stn,S)

END


EXTERNAL SUB try(CEL(,),p,stn,S()) !バックトラック法(深さ優先探索)
IF p=2 THEN !2手先 ※
   FOR i=1 TO p !手順を表示する
      IF S(i)>0 THEN
         PRINT "○";INT(S(i)/10); mid$("ABCDEFGH",MOD(S(i),10),1)
      ELSE
         PRINT "●";INT(-S(i)/10); mid$("ABCDEFGH",MOD(-S(i),10),1)
      END IF
   NEXT i
   CALL plot_now(CEL, stn) !その盤面を表示する

ELSE
   DIM W(8,8) !save it
   MAT W=CEL
   FOR i=1 TO 8
      FOR J=1 TO 8
         IF CEL(i,J)=0 THEN !空きなら

            CALL check2(CEL,i,J,stn, ok) !そこに打ってみる
            IF ok=1 THEN
               LET S(p+1)=(i*10+j)*SGN(stn) !10進法
               CALL try(CEL,p+1,-stn,S) !次へ
               MAT CEL=W !restore it
            END IF

         END IF
      NEXT J
   NEXT i

END IF
END SUB


EXTERNAL SUB plot_now(CEL(,),stn) !今の局面を表示する
LET n1=0 !白、黒の数
LET n2=0
PRINT "  A B C D E F G H" !列番号
FOR i=1 TO 8
   PRINT i; !行番号
   FOR J=1 TO 8
      IF CEL(i,J)=1 THEN !白石なら
         PRINT "○";
         LET n1=n1+1
      ELSEIF CEL(i,J)=-1 THEN !黒石なら
         PRINT "●";
         LET n2=n2+1
      ELSE !空き
         PRINT "・";
      END IF
   NEXT J
   PRINT
NEXT i
PRINT "  白:";n1; " 黒:";n2
IF stn=1 THEN PRINT "次は○" ELSE PRINT "次は●"
PRINT
END SUB


EXTERNAL FUNCTION get_cell(CEL(,),i,j) !指定したマスの石を得る
LET get_cell = 0
IF i>0 AND i<9 AND j>0 AND j<9 THEN !盤内だけ
   LET get_cell = CEL(i,j)
END IF
END FUNCTION


EXTERNAL SUB check2(CEL(,),i,j,stn, ok) !はさんでいるか確認して、裏返す
LET ok=-1 !NG
FOR dx=-1 TO 1 !横方向
   FOR dy=-1 TO 1 !縦方向
      IF dx=0 AND dy=0 THEN !8方向なら
      ELSE
         LET N=0
         LET s=i+dx !ひとつ隣へ
         LET t=j+dy
         LET AA = get_cell(CEL,s,t)
         DO WHILE NOT(AA=0 OR AA=stn) !マス外か石がないか同じ色の石まで
            LET N=N+1 !間に相手の石がある
            LET s=s+dx !次のマス目へ
            LET t=t+dy
            LET AA = get_cell(CEL,s,t)
         LOOP
         IF AA=stn AND N>0 THEN !●○・・○●と●○・・○を区別する
            LET ok=1
            CALL reverse(CEL,i,j,stn,N,dx,dy) !裏返す
            LET CEL(i,j)=stn !そこに石を埋める
         END IF
      END IF
   NEXT dy
NEXT dx
END SUB


EXTERNAL SUB reverse(CEL(,),i,j,stn,N,dx,dy) !裏返す(自分の石と同じ色にする)
LET s=i+dx !ひとつ隣へ
LET t=j+dy
FOR k=1 TO N
   LET CEL(s,t) = stn
   LET s=s+dx !次のマス目へ
   LET t=t+dy
NEXT k
END SUB
 

反復深化法について

 投稿者:山路 武雄  投稿日:2010年 9月15日(水)21時05分20秒
  お返事ありがとうございます。
盤面の表現、評価など条件の設定をせず、すいませんでした。
大変参考になりました。
ありがとうございました。
 

戻る