続オセロゲーム

　　続オセロゲーム 山中和義 2005/03/16 19:20:59 
　　├プログラム 山中和義 2005/03/16 19:22:08 
　　├続き 山中和義 2005/03/16 19:24:28 
　　└続き 山中和義 2005/03/16 19:25:12 
　　　└結果：後手(白)有利 会社員 2005/03/21 18:10:58 
　　　　└おもしろいですね。 shino 2005/03/25 21:44:02 
　　　　　└思考力(＝アルゴリズム）があると、 会社員 2005/03/27 21:42:41

　　続オセロゲーム 山中和義 2005/03/16 19:20:59  ツリーへ

続オセロゲーム 返事を書く

山中和義 2005/03/16 19:20:59

任意に手を決めていった場合、どちらが優位かの実験的考察ですが、
以前の会社員さんのプログラムを改良してみました。

改良点
・空きマスから次の手を打つ。
　空きマスは左上から連番で、０～空きマスの数－１（乱数）で手を決める。
　その手が無効な場合、候補からはずし、０～空きマスの数－２から
　手を考えます。　・・・最終的に手がなければ、相手の攻撃へ。
・互いに手がない場合、そこで終了とする。（nopflg）

結果は前回と同じです。

対戦への考察
・空きマスに優先順位をつけて、次の一手を打つ
・有効な候補をすべて調べて、一番多く裏返す手を打つ

　　├プログラム 山中和義 2005/03/16 19:22:08  ツリーへ

Re: 続オセロゲーム 返事を書く

山中和義 2005/03/16 19:22:08

プログラム

!オセロゲーム
RANDOMIZE

LET CNT_WHT=0 !勝敗カウンタ
LET CNT_BLK=0
LET CNT_HKW=0

10
!初期設定
SET BITMAP SIZE 640,480 !画面サイズ640×480
SET WINDOW 0,640,0,480 !左下が原点。横がＸ、縦Ｙ
SET COLOR mode "NATIVE" !RGB指定
SET TEXT font "",12 !文字サイズ
DIM CEL(8,8) !配置情報

!盤を表示する
SET AREA COLOR colorindex(0,1,0) !緑
PLOT AREA:50,50; 50,450; 450,450; 450,50
FOR i=1 TO 8 !行番号
PLOT TEXT ,AT 25,470-50*i:STR$(i)
NEXT i
FOR i=1 TO 8 !列番号
PLOT TEXT ,AT 20+50*i,460:CHR$(i+64)
NEXT i

!マス目を表示する
SET LINE COLOR colorindex(0,0,0) !黒
PLOT LINES:50,50; 50,450; 450,450; 450,50; 50,50
FOR i=1 TO 2
PLOT LINES:50-i,50-i; 50-i,450+i; 450+i,450+i; 450+i,50-i; 50-i,50-i
NEXT i

FOR i=1 TO 8 !縦線
PLOT LINES:50*i,50; 50*i,450
NEXT i
FOR i=1 TO 8 !横線
PLOT LINES:50,50*i; 450,50*i
NEXT i

!局面を初期化する
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
LET kk = 0 !候補の中で打てなかった数
LET nopflg = 0
!◇◇◇◇◇◇以上初期設定終了◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇

LET flg = -1 !ゲーム中（黒の手）※-1は黒、1は白
CALL plot_now(CEL,flg,CNT_WHT,CNT_BLK,CNT_HKW,NoUsed) !今の局面を表示する

DO WHILE flg<>0 !※0は終了
!-----候補をあげる
LET K = INT(RND*(NoUsed-kk)) !空きマスから任意に選ぶ
PRINT K;NoUsed;kk !debug debug debug
FOR LL=0 TO 63
LET i = INT(LL/8)+1 !行、列に変換する
LET j = MOD(LL,8)+1
IF CEL(i,j)=0 THEN !左上からの連番で、該当の未使用マスを選ぶ
IF K<1 THEN EXIT FOR
LET K = K - 1
END IF
NEXT LL
!!! PRINT i;j !debug debug debug

!-----その位置に打ってみる
CALL check2(CEL,i,j,flg, ok) !はさんでいるか確認し、縦横斜めを反転させる
IF ok>0 THEN !はさんだ位置に置いたら
LET CEL(i,j) = flg !そこに石を埋める
CALL reset_stone(CEL,flg,kk)
LET nopflg = 0
ELSE
LET CEL(i,j) = 2 !候補からはずす
LET kk = kk + 1

!打つ手があるか確認する
IF kk>=NoUsed THEN !打つ手がなければ、相手の攻撃へ
CALL reset_stone(CEL,flg,kk)
LET nopflg = nopflg + 1
END IF
END IF

!-----局面を表示する
CALL plot_now(CEL,flg,CNT_WHT,CNT_BLK,CNT_HKW,NoUsed) !今の局面を表示する flg=0で終了
IF nopflg>1 THEN LET flg = 0 !互いに打つ手なし！

LOOP

WAIT DELAY 10

GOTO 10 !次の試合へ
END

　　├続き 山中和義 2005/03/16 19:24:28  ツリーへ

Re: 続オセロゲーム 返事を書く

山中和義 2005/03/16 19:24:28

続き

!候補をクリアする
EXTERNAL SUB reset_stone(CEL(,),flg,kk)
FOR i=1 TO 8 !候補をクリアする
FOR j=1 TO 8
IF CEL(i,j)=2 THEN LET CEL(i,j)=0
NEXT j
NEXT i
LET kk = 0
LET flg = -flg !交代する
END SUB

!石を描画する
EXTERNAL SUB plot_stone(i,j,c)
CALL ij2xy(i,j, x,y) !マス目からＸＹ座標に変換する
SET AREA COLOR colorindex(0,0,0) !黒の輪郭
DRAW disk WITH SCALE(21)*SHIFT(x,y)
SET AREA COLOR c !白または黒
DRAW disk WITH SCALE(20)*SHIFT(x,y)
END SUB

!マス目番号からＸＹ座標を求める ※横,縦 i,j、x,y
EXTERNAL SUB ij2xy(i,j, x,y)
LET x = i*50+25
LET y = 450-j*50+25
END SUB

!今の局面を表示する
EXTERNAL SUB plot_now(CEL(,),stn,CNT_WHT,CNT_BLK,CNT_HKW,NoUsed)
LET n1=0 !白・黒の数
LET n2=0
FOR i=1 TO 8
FOR j=1 TO 8
IF CEL(i,J)=1 THEN !白石なら
CALL plot_stone(i,j,colorindex(1,1,1))
LET n1=n1+1
END IF
IF CEL(i,J)=-1 THEN !黒石なら
CALL plot_stone(i,j,colorindex(0,0,0))
LET n2=n2+1
END IF
NEXT j
NEXT i
LET NoUsed = 64-n1-n2 !空きのマスを数える

SET AREA COLOR colorindex(1,1,1) !表示領域を消す
PLOT AREA:500,0;640,0;640,480;500,480
PLOT TEXT ,AT 500,300:"白："&STR$(n1) !石の数を表示する
PLOT TEXT ,AT 500,275:"黒："&STR$(n2)
PLOT TEXT ,AT 500,250:"白勝ち数："&STR$(CNT_WHT) !勝ち数を表示する
PLOT TEXT ,AT 500,225:"黒勝ち数："&STR$(CNT_BLK)
PLOT TEXT ,AT 500,200:"引き分数："&STR$(CNT_HKW)

IF n1+n2<64 THEN !もし 64枚以下なら
!もし 64枚以下でも
IF n1=0 THEN !全部が黒なら
PLOT TEXT ,AT 500,370:"おわり！黒勝!"
LET stn = 0
LET CNT_BLK=CNT_BLK+1
ELSE
IF n2=0 THEN
PLOT TEXT ,AT 500,370:"おわり！白勝!"
LET stn = 0
LET CNT_WHT=CNT_WHT+1
ELSE
PLOT TEXT ,AT 560,370:"の番"
IF stn=1 THEN !白なら
CALL plot_stone(10,2,colorindex(1,1,1))
ELSE
CALL plot_stone(10,2,0)
END IF
END IF
END IF
ELSE !もし64を超えたら、おわり
IF n1<n2 THEN
PLOT TEXT ,AT 500,370:"おわり！黒勝!"
LET CNT_BLK=CNT_BLK+1
ELSE
IF n1>n2 THEN
PLOT TEXT ,AT 500,370:"おわり！白勝!"
LET CNT_WHT=CNT_WHT+1
ELSE
PLOT TEXT ,AT 500,370:"引き分け!"
LET CNT_HKW=CNT_HKW+1
END IF
END IF
LET stn = 0
END IF
END SUB

　　└続き 山中和義 2005/03/16 19:25:12  ツリーへ

Re: 続オセロゲーム 返事を書く

山中和義 2005/03/16 19:25:12

続き

!指定したマスの石を得る
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
FOR dx=-1 TO 1 !横方向
FOR dy=-1 TO 1 !縦方向
IF dx=0 AND dy=0 THEN !８方向なら
ELSE
LET N = 0
LET s=i+dx !ひとつ隣へ
LET t=j+dy
LET AA = get_cell(CEL,s,t)
DO WHILE AA=-stn !マス外か石がないか同じ色の石まで
!!! IF AA=-stn THEN
LET N=N+1 !間に相手の石がある
!!! END IF
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) !裏返す
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

　　　└結果：後手(白)有利 会社員 2005/03/21 18:10:58  ツリーへ

Re: 続き 返事を書く

会社員 2005/03/21 18:10:58

結果：後手(白)有利

ありがとうございました。
黒勝(先手)　3125(46.20%)
白勝(後手)　3360(49.67%)
引き分け　279(4.12%)
でした。

又、思いのほか、引き分けが多く、
チェスで有名なディープブルーのようなコンピュータ同士が対戦したら、
現在なら、永遠に引分けを繰り返しそうです。

------------------------------------------------------------------
それと　オセロにも　白も黒も置けない「駄目」はあって
(プログラム変更して対戦させるまで完全に忘れていました)
私は、これを「ノーゲーム」扱いで処理していましたが、
正式には「置けなくなった時点」での数の多い少ないで勝敗を決めるようですね。

　　　　└おもしろいですね。 shino 2005/03/25 21:44:02  ツリーへ

Re: 結果：後手(白)有利 返事を書く

shino 2005/03/25 21:44:02

おもしろいですね。

私もいくつかアルゴリズムを作ってやってみました。
０：ランダム
１：多くひっくり返せるものを優先
２：１に加え、角・壁取り優先
３：相手に角・壁を取らせないようにし、かつ積極的に角・壁を狙う(盤面の状況から判断します)

数字が大きいほど強いアルゴリズムです。
結果は次の通りになりました。

10000回の試行(先手勝利数,後手勝利数)
対戦：一回目：二回目
0対0：(4629,5371)：(4478,5522)
1対1：(4897,5103)：(4866,5134)
2対2：(4391,5609)：(4460,5540)
3対3：(4919,5081)：(4882,5118)

アルゴリズムによって差がありますが、
後手有利というのは変わらないようです。

結果のばらつきは、
そのアルゴリズムにおける最後の一手が
どれだけの重要度を占めるかということでしょうか？
（特に３は序～中盤戦用のアルゴリズムです）

一回目と二回目に差があるものは、
それだけ強さに幅がある(運任せ)ということなのでしょうね。

　　　　　└思考力(＝アルゴリズム）があると、 会社員 2005/03/27 21:42:41  ツリーへ

Re: おもしろいですね。 返事を書く

会社員 2005/03/27 21:42:41

思考力(＝アルゴリズム）があると、
必ずしも、後手(白）有利にならないのだろうと
勝手に思っていたのですが、意外な結果です。

shino さん
とても面白い結果　ありがとうございました。

インデックスへ EXIT
新規発言を反映させるにはブラウザの更新ボタンを押してください。

続オセロゲーム	返事を書く
山中和義 2005/03/16 19:20:59
任意に手を決めていった場合、どちらが優位かの実験的考察ですが、以前の会社員さんのプログラムを改良してみました。改良点・空きマスから次の手を打つ。　空きマスは左上から連番で、０～空きマスの数－１（乱数）で手を決める。　その手が無効な場合、候補からはずし、０～空きマスの数－２から　手を考えます。　・・・最終的に手がなければ、相手の攻撃へ。・互いに手がない場合、そこで終了とする。（nopflg）結果は前回と同じです。対戦への考察・空きマスに優先順位をつけて、次の一手を打つ・有効な候補をすべて調べて、一番多く裏返す手を打つ

Re: 続オセロゲーム	返事を書く
山中和義 2005/03/16 19:22:08
プログラム !オセロゲーム RANDOMIZE LET CNT_WHT=0 !勝敗カウンタ LET CNT_BLK=0 LET CNT_HKW=0 10 !初期設定 SET BITMAP SIZE 640,480 !画面サイズ640×480 SET WINDOW 0,640,0,480 !左下が原点。横がＸ、縦Ｙ SET COLOR mode "NATIVE" !RGB指定 SET TEXT font "",12 !文字サイズ DIM CEL(8,8) !配置情報 !盤を表示する SET AREA COLOR colorindex(0,1,0) !緑 PLOT AREA:50,50; 50,450; 450,450; 450,50 FOR i=1 TO 8 !行番号 PLOT TEXT ,AT 25,470-50i:STR$(i) NEXT i FOR i=1 TO 8 !列番号 PLOT TEXT ,AT 20+50i,460:CHR$(i+64) NEXT i !マス目を表示する SET LINE COLOR colorindex(0,0,0) !黒 PLOT LINES:50,50; 50,450; 450,450; 450,50; 50,50 FOR i=1 TO 2 PLOT LINES:50-i,50-i; 50-i,450+i; 450+i,450+i; 450+i,50-i; 50-i,50-i NEXT i FOR i=1 TO 8 !縦線 PLOT LINES:50i,50; 50i,450 NEXT i FOR i=1 TO 8 !横線 PLOT LINES:50,50i; 450,50i NEXT i !局面を初期化する 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 LET kk = 0 !候補の中で打てなかった数 LET nopflg = 0 !◇◇◇◇◇◇以上初期設定終了◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇ LET flg = -1 !ゲーム中（黒の手）※-1は黒、1は白 CALL plot_now(CEL,flg,CNT_WHT,CNT_BLK,CNT_HKW,NoUsed) !今の局面を表示する DO WHILE flg<>0 !※0は終了 !-----候補をあげる LET K = INT(RND*(NoUsed-kk)) !空きマスから任意に選ぶ PRINT K;NoUsed;kk !debug debug debug FOR LL=0 TO 63 LET i = INT(LL/8)+1 !行、列に変換する LET j = MOD(LL,8)+1 IF CEL(i,j)=0 THEN !左上からの連番で、該当の未使用マスを選ぶ IF K<1 THEN EXIT FOR LET K = K - 1 END IF NEXT LL !!! PRINT i;j !debug debug debug !-----その位置に打ってみる CALL check2(CEL,i,j,flg, ok) !はさんでいるか確認し、縦横斜めを反転させる IF ok>0 THEN !はさんだ位置に置いたら LET CEL(i,j) = flg !そこに石を埋める CALL reset_stone(CEL,flg,kk) LET nopflg = 0 ELSE LET CEL(i,j) = 2 !候補からはずす LET kk = kk + 1 !打つ手があるか確認する IF kk>=NoUsed THEN !打つ手がなければ、相手の攻撃へ CALL reset_stone(CEL,flg,kk) LET nopflg = nopflg + 1 END IF END IF !-----局面を表示する CALL plot_now(CEL,flg,CNT_WHT,CNT_BLK,CNT_HKW,NoUsed) !今の局面を表示する flg=0で終了 IF nopflg>1 THEN LET flg = 0 !互いに打つ手なし！ LOOP WAIT DELAY 10 GOTO 10 !次の試合へ END

Re: 続オセロゲーム	返事を書く
山中和義 2005/03/16 19:24:28
続き !候補をクリアする EXTERNAL SUB reset_stone(CEL(,),flg,kk) FOR i=1 TO 8 !候補をクリアする FOR j=1 TO 8 IF CEL(i,j)=2 THEN LET CEL(i,j)=0 NEXT j NEXT i LET kk = 0 LET flg = -flg !交代する END SUB !石を描画する EXTERNAL SUB plot_stone(i,j,c) CALL ij2xy(i,j, x,y) !マス目からＸＹ座標に変換する SET AREA COLOR colorindex(0,0,0) !黒の輪郭 DRAW disk WITH SCALE(21)SHIFT(x,y) SET AREA COLOR c !白または黒 DRAW disk WITH SCALE(20)SHIFT(x,y) END SUB !マス目番号からＸＹ座標を求める ※横,縦 i,j、x,y EXTERNAL SUB ij2xy(i,j, x,y) LET x = i50+25 LET y = 450-j50+25 END SUB !今の局面を表示する EXTERNAL SUB plot_now(CEL(,),stn,CNT_WHT,CNT_BLK,CNT_HKW,NoUsed) LET n1=0 !白・黒の数 LET n2=0 FOR i=1 TO 8 FOR j=1 TO 8 IF CEL(i,J)=1 THEN !白石なら CALL plot_stone(i,j,colorindex(1,1,1)) LET n1=n1+1 END IF IF CEL(i,J)=-1 THEN !黒石なら CALL plot_stone(i,j,colorindex(0,0,0)) LET n2=n2+1 END IF NEXT j NEXT i LET NoUsed = 64-n1-n2 !空きのマスを数える SET AREA COLOR colorindex(1,1,1) !表示領域を消す PLOT AREA:500,0;640,0;640,480;500,480 PLOT TEXT ,AT 500,300:"白："&STR$(n1) !石の数を表示する PLOT TEXT ,AT 500,275:"黒："&STR$(n2) PLOT TEXT ,AT 500,250:"白勝ち数："&STR$(CNT_WHT) !勝ち数を表示する PLOT TEXT ,AT 500,225:"黒勝ち数："&STR$(CNT_BLK) PLOT TEXT ,AT 500,200:"引き分数："&STR$(CNT_HKW) IF n1+n2<64 THEN !もし 64枚以下なら !もし 64枚以下でも IF n1=0 THEN !全部が黒なら PLOT TEXT ,AT 500,370:"おわり！黒勝!" LET stn = 0 LET CNT_BLK=CNT_BLK+1 ELSE IF n2=0 THEN PLOT TEXT ,AT 500,370:"おわり！白勝!" LET stn = 0 LET CNT_WHT=CNT_WHT+1 ELSE PLOT TEXT ,AT 560,370:"の番" IF stn=1 THEN !白なら CALL plot_stone(10,2,colorindex(1,1,1)) ELSE CALL plot_stone(10,2,0) END IF END IF END IF ELSE !もし64を超えたら、おわり IF n1<n2 THEN PLOT TEXT ,AT 500,370:"おわり！黒勝!" LET CNT_BLK=CNT_BLK+1 ELSE IF n1>n2 THEN PLOT TEXT ,AT 500,370:"おわり！白勝!" LET CNT_WHT=CNT_WHT+1 ELSE PLOT TEXT ,AT 500,370:"引き分け!" LET CNT_HKW=CNT_HKW+1 END IF END IF LET stn = 0 END IF END SUB

Re: 続オセロゲーム	返事を書く
山中和義 2005/03/16 19:25:12
続き !指定したマスの石を得る 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 FOR dx=-1 TO 1 !横方向 FOR dy=-1 TO 1 !縦方向 IF dx=0 AND dy=0 THEN !８方向なら ELSE LET N = 0 LET s=i+dx !ひとつ隣へ LET t=j+dy LET AA = get_cell(CEL,s,t) DO WHILE AA=-stn !マス外か石がないか同じ色の石まで !!! IF AA=-stn THEN LET N=N+1 !間に相手の石がある !!! END IF 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) !裏返す 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

Re: 続き	返事を書く
会社員 2005/03/21 18:10:58
結果：後手(白)有利ありがとうございました。黒勝(先手)　3125(46.20%) 白勝(後手)　3360(49.67%) 引き分け　279(4.12%) でした。又、思いのほか、引き分けが多く、チェスで有名なディープブルーのようなコンピュータ同士が対戦したら、現在なら、永遠に引分けを繰り返しそうです。 ------------------------------------------------------------------ それと　オセロにも　白も黒も置けない「駄目」はあって (プログラム変更して対戦させるまで完全に忘れていました) 私は、これを「ノーゲーム」扱いで処理していましたが、正式には「置けなくなった時点」での数の多い少ないで勝敗を決めるようですね。

Re: 結果：後手(白)有利	返事を書く
shino 2005/03/25 21:44:02
おもしろいですね。私もいくつかアルゴリズムを作ってやってみました。０：ランダム１：多くひっくり返せるものを優先２：１に加え、角・壁取り優先３：相手に角・壁を取らせないようにし、かつ積極的に角・壁を狙う(盤面の状況から判断します) 数字が大きいほど強いアルゴリズムです。結果は次の通りになりました。 10000回の試行(先手勝利数,後手勝利数) 対戦：一回目：二回目 0対0：(4629,5371)：(4478,5522) 1対1：(4897,5103)：(4866,5134) 2対2：(4391,5609)：(4460,5540) 3対3：(4919,5081)：(4882,5118) アルゴリズムによって差がありますが、後手有利というのは変わらないようです。結果のばらつきは、そのアルゴリズムにおける最後の一手がどれだけの重要度を占めるかということでしょうか？（特に３は序～中盤戦用のアルゴリズムです）一回目と二回目に差があるものは、それだけ強さに幅がある(運任せ)ということなのでしょうね。

Re: おもしろいですね。	返事を書く
会社員 2005/03/27 21:42:41
思考力(＝アルゴリズム）があると、必ずしも、後手(白）有利にならないのだろうと勝手に思っていたのですが、意外な結果です。 shino さんとても面白い結果　ありがとうございました。