くだものしょうぶ (3) コンピュータの思考ついて
どうぶつしょうぎの時と、少し変えたので、もう一度説明します。余り強さは変らない気がしますが、対戦させても面白いかな・・・。
どうぶつしょうぎの時に使っていた適当にランダムに打って、勝った回数が多い指し手に評価点を高く付けて評価していく方法ですが、この方法がモンテカルロ木探索に近いので、これを使って思考プログラムを作ってみることにしました。ただし、論文を流し読みしただけなので、なんちゃってモンテカルロ木探索になっていると思います。ていうか、木を作っていないです(Luaのテーブルを使っている癖に(^^;)。
この改良で、一手の思考に最大30秒くらいかかるようになってしまいました。エミュレータでの話しなので実機だともっと速いかな。この改良をもって「正月休みに子供と動物将棋を遊ぶ企画」を終わりにしたいと思います。
基本的な考え方
- 今の局面からランダムに15手打ってみて、勝負がつけばそれについての結果点を評価点に加減算していき、これを数百回繰り返し、一番評価点の高い指し手を選ぶ。
これが基本的な考え方です。どうぶつしょうぎのときの考え方と同じです。これに下記の判断を追加しました。
- ランダムに数百回打っている途中で、評価点がある閾値よりも小さくなった手に関しては、指し手評価の対象から外していき、残った指し手から、より良い指し手を見つけられるようにする。
モンテカルロ木探索とはこういうことだと、勝手に解釈しました・・・。
評価点の付け方
評価の方法を具体的に、下記のようにしました。
- コンピュータ同士で今の盤面から15手先までを、全部で400回を指す。
- 15手打つ前に勝負がつけば、以下の基準で評価点に結果点の加減を行う。
- 15手打っても勝負がつかない場合は、駒点が多い方を勝ちとする。駒点は「すいか」が1点、他は2点とした合計点とする。
- 駒点が同点の場合は、引き分けとする。
指し手の評価点は、結果点と追加点の合計となります。結果点の計算は下記のようにしました。
- 1勝負毎に、最初の指し手を覚えておいて、その指し手を打った結果15手以内に勝てば、評価点に結果点(15-勝ちまでの手数)を加える。
- 15手以内で負ければ、評価点から結果点(15-勝ちまでの手数)を引く。すなわち減算される。
- 15手指して引き分けの場合は、結果点は0点とする。
400回繰り返される1勝負毎に、評価点が積算されていきます(含む減算)。
また、追加点という考えを入れました。これは駒点によって、選ぶ指し手に変化を持たせたかったからです。下記のような点数としました。
- 駒点が相手より大きい場合、敵みかんの移動できるマスが減った数×0.35を評価点に加える。
- 駒点が相手より大きい場合、王手ならば、自分の駒点×0.1を評価点に加える。
- 駒点が相手より小さい場合、敵みかんの移動できるマスが減った数×0.2を評価点に加える。
- 駒点が相手より小さい場合、敵みかんの移動できるマスが増えた数×0.2を評価点から減算する。
この追加点を加味すると、駒点が大きい場合攻勢に出る打ち方になると思います。
モンテカルロ木探索する
モンテカルロ木探索は、下記のようにしました。
- 100回(100通り)指す毎に、評価点が-10以下の指し手を、指し手の検索対象から除いていく。
- 指し手のすべてが-10以下になるときは、4手を選んで解析を続ける。
これだけのルールしか作らなかったので、400回検索するうち、3回しか枝切りは行われません。この回数なので、指し手候補が多い場合は、おかしな手を選択する場合が多いです。スクリプトなので、興味のある方は適当に値をいじってみてください。
プログラム
プログラムソースを以下に書きます。compthink()という関数になっています。ソースを簡単に説明していきます。
本当の駒は位置関連のテーブルが、引数 msg, mbe, mafに、入ってきています。下記は関数内で展開するための配列宣言です。
function compthink( msg, mbe, maf ) local tjun local sg = { bn={}, tjun, mchi={} } sg.bn[1] = { 0,0,0,0 } sg.bn[2] = { 0,0,0,0 } sg.bn[3] = { 0,0,0,0 } sg.mchi[1] = { 0,0,0,0,0,0 } sg.mchi[2] = { 0,0,0,0,0,0 } local x,y local koma local be={ koma, x, y } local af={ koma, x, y } local winner
kirisute配列は、モンテカルロ木探索で切り落とされた枝が格納される配列です。本来ならば、切り落とした時点で、指し手の選択肢の木(ここでは配列)から削除されるべきなのですが、今回は手を抜いています。なので、切り落としが増えると検索速度は遅くなってしまいます。他はもろもろ中で使う変数です。
local kirisute={} --選択肢が5以上の時に-10以上の指し手は検討対象から外すので、その外す手を入れる配列 local kirisutecnt = 0 local kirisutei, kirisuteflg, kirisutecntb local cmpData={} local cmpTe={} local cnt = 0 local ca = 0 local i local imaData, uflg, hyoData local n1, n2 local addv = 0 local ohte local syobuari = 0 local isyobu
ここから、400回の繰り返し乱数打ちを開始します。先ず、今の盤面と持ち駒など、現状の条件を内部配列にコピーします。
msgDisp( "かんがえちゅう" ) --今の盤面から400通りの勝負をコンピュータ同士で行う for j=1,400 do --今の盤面のコピー for x=1,3 do for y=1,4 do sg.bn[x][y] = msg.bn[x][y] end end --今の持ち駒のコピー for i=1,6 do sg.mchi[1][i] = msg.mchi[1][i] sg.mchi[2][i] = msg.mchi[2][i] end sg.tjun = msg.tjun be.x = mbe.x be.y = mbe.y be.koma = mbe.koma af.x = maf.x af.y = maf.y af.koma = maf.koma
ここから15手の乱数打ちを始めます。
ca には結果点算出用の手数が入ります。addv には追加点が入ります。syobuari は引き分けを判断するフラグです。compthinkTeChoice()により指し手をランダムに選びます。1手目に関しては、検索対象外となった手で無いかチェックを行います。
ca = 0 addv = 0 syobuari = 0 for isyobu=1,15 do --15手先までコンピュータ同士でシミュレーションする -- 手を選ぶ if( isyobu==1 )then --最初の一手はkirisute配列に無い手を選択させる while(true)do compthinkTeChoice( sg, be, af ) if( be.y==-1 )then imaData = (be.koma+50)*100 + af.x*10 + af.y else imaData = be.x*1000 + be.y*100 + af.x*10 + af.y end --kirisute配列に無い手かどうかのチェック kirisuteflg = 0 for kirisutei=1,kirisutecnt do if( imaData==kirisute[kirisutei] )then kirisuteflg = 1 end end if( kirisuteflg==0 )then break end end else compthinkTeChoice( sg, be, af ) end
最初の1手目(ca=0)のとき、敵みかんが動けるマスを数えてn1に保持します。そして、駒を1手動かします。
if( ca==0 )then --評価用にこれから指すデータを保存する if( be.y==-1 )then imaData = (be.koma+50)*100 + af.x*10 + af.y else imaData = be.x*1000 + be.y*100 + af.x*10 + af.y end --駒を進める前の敵みかんの動けるマス数 n1 = compthinkLionMasu( sg.bn, 3-sg.tjun ) end --評価値caのカウントアップ ca = ca + 1 if( be.y==-1 )then --持ち駒を打った komaUtsu( sg, be, af ) sg.tjun = 3 - sg.tjun --手順を入れ替える else --盤上の駒を動かした komaMove( sg, be, af ) sg.tjun = 3 - sg.tjun --手順を入れ替える end
次に、1手打った後の敵みかんが進めるマスの数を数えて、n2に保持します。そして、1手目なので追加点を計算します。自分の駒点が高い場合は、(相手みかんの動けるマスの減少数)*0.35を追加点に加算します。そして、王手であるときは、自駒点*0.1を追加点に加算します。
逆に、相手の駒点が高い場合は、(相手みかんの動けるマスの増減数)*0.2を追加点に加算します。この値は負の値もあります。
そして、勝負がついたかどうか調べて、勝負がついていなければ、ループして相手がランダムに次の手を選んで打ちます。勝負がつかなければ15手まで繰り返します。引き分け(千日手)のチェックは省きました。
if( ca==1 )then --駒を進めた後の敵みかんの動けるマス数 n2, ohte = compthinkLionMasu( sg.bn, sg.tjun ) if( compthinkGetKomasu( sg, sg.tjun )<7 )then --相手の駒点が少ないときは、攻撃優先 if( n1-n2>0 )then addv = (n1 - n2)*0.35 end --王手になっていれば評価アップさせる if( ohte==1 )then addv = addv + compthinkGetKomasu( sg, 3-sg.tjun )*0.1 end else --相手の駒点が多いときは守り優先 addv = (n1 - n2)*0.2 end end --勝負がついたか調べます winner = chkSyobuAri( sg.bn ) --千日手をチェックします --if( chkSenNichiTe( KifuN-1, sg.bn )==1 )then winner = 3 end if( winner~=0 )then syobuari = 1 break end end
ここで、15手指してループを抜けてきます。勝負がついていなければ、駒点により勝敗を決めます。7点で引き分けなので、8点以上あれば勝ちです。
--勝負がついていなければ、駒点の多い方を勝ちとする if( syobuari==0 )then local p = compthinkGetKomasu( sg, 1 ) --評価する。駒点が8以上で勝ち、7点だと引き分け。 if( p>7 )then winner = 1 elseif( p<7 )then winner = 2 else winner = 3 end end
ここから、評価点の計算に入ります。負けたときは結果点が減算されます。そして追加点はそのまま加算されます。勝ったときは結果点が加算され、追加点も加算されます。引き分けのときは、追加点のみ加算されます。
そして、指し手がcmpTeに保存され、評価点がcmpDataに保存されます。同じ指し手の評価点がcmpData[]に積算されていきます。
--結果点と追加点と勝敗を元に足しこむ値を計算します if( winner~=msg.tjun )then --負けたとき hyoData = -(15-ca) + addv elseif( winner==msg.tjun )then --勝ったとき hyoData = (15-ca) + addv else --引き分けのとき hyoData = addv end --評価点に足しこみます uflg = 0 for i=1,cnt do if( cmpTe[i]==imaData )then cmpData[i] = cmpData[i] + hyoData uflg = 1 break end end if( uflg==0 )then cnt = cnt + 1 cmpTe[cnt] = imaData cmpData[cnt] = hyoData end
これ以降で、モンテカルロ木検索の枝切りを行います。100回目、200回目、300回目で評価点積算値が -10以下の指し手について、切捨て配列に記録していきます。条件として、5つ以上の指し手が選ばれていて、且つ、切捨てられていない指し手が4つ以上あるとき、枝切りを行います。
そして、400回までループを繰り返します。
今見ると、プログラムが冗長ですね。元々各回数ごとにデバッグ用のルーチンが入っていたので、こんな冗長にソースになってしまいました・・・。
if( j==100 )then --1回目のモンテカルロ木枝切り local zi kirisutecntb = kirisutecnt for zi=1,cnt do if( (cnt-kirisutecntb)>=5 and cmpData[zi]<=-10 and (cnt-kirisutecnt)>3 )then kirisutecnt = kirisutecnt + 1 kirisute[kirisutecnt] = cmpTe[zi] end end elseif( j==200 )then --2回目のモンテカルロ木枝切り local zi kirisutecntb = kirisutecnt for zi=1,cnt do if( (cnt-kirisutecntb)>=5 and cmpData[zi]<=-10 and (cnt-kirisutecnt)>3 )then kirisutecnt = kirisutecnt + 1 kirisute[kirisutecnt] = cmpTe[zi] end end elseif( j==300 )then --3回目のモンテカルロ木枝切り local zi kirisutecntb = kirisutecnt for zi=1,cnt do if( (cnt-kirisutecntb)>=5 and cmpData[zi]<=-10 and (cnt-kirisutecnt)>3 )then kirisutecnt = kirisutecnt + 1 kirisute[kirisutecnt] = cmpTe[zi] end end end end
400回ランダムに指した後、ループを抜けてきます。ここ以降で、評価点の最も大きい指し手を選びます。最大値を選ぶ途中で、切り捨てた打ち手が選ばれないようにチェックしています。本来の検索木を作っている場合は不要な処理のはずです。
そして、評価点によって、適当な言葉を表示しています。
--最大の評価データ値を選びます local max = -10000 local chocnt = 1 for i=1,cnt do if( max<cmpData[i] )then --kirisute配列に無い指し手かどうかを確かめます kirisuteflg = 0 for kirisutei=1,kirisutecnt do if( cmpTe[i]==kirisute[kirisutei] )then kirisuteflg = 1 break end end if( kirisuteflg==0 )then max = cmpData[i] chocnt = i end end end if( cmpData[chocnt]<-100 )then msgDisp( "あぁ、まけた" ) elseif( cmpData[chocnt]<0 )then msgDisp( "まずいなぁ" ) elseif( cmpData[chocnt]>100 )then msgDisp( "よし、かてるぞ" ) else msgDisp( "なかなか、やるなぁ" ) end
これで、指し手選びは終了です。以下では、コンピュータが選んだ指し手を本来の将棋用のテーブルに入れています。そして、思考ルーチンから抜けます。
--次に指す手を作ります local tst = tostring( cmpTe[chocnt] ) if( cmpTe[chocnt]<6000 )then mbe.x = tonumber(string.sub( tst, 1, 1 )) mbe.y = tonumber(string.sub( tst, 2, 2 )) maf.x = tonumber(string.sub( tst, 3, 3 )) maf.y = tonumber(string.sub( tst, 4, 4 )) mbe.koma = msg.bn[mbe.x][mbe.y] maf.koma = 0 else mbe.koma = tonumber(string.sub( tst, 1, 2 )) - 50 for j=1,6 do if( msg.mchi[msg.tjun][j]==mbe.koma )then mbe.x = j break end end mbe.y = -1 maf.koma = 0 maf.x = tonumber(string.sub( tst, 3, 3 )) maf.y = tonumber(string.sub( tst, 4, 4 )) end end
以上です。
