例えば、しりとりをして15往復した時点で使用した言葉の文字数合計で勝負をするゲームがあるとします。
ただし通常のしりとりと違って、末尾に「ん」がついたら負けというのは無しにします。
さて、これをSASプログラムでやる場合、どういうロジックで言葉を選べばいいでしょうか？
単純に考えれば、出しうる言葉の中で一番長いやつを選んでいけばよさそうですね。
それじゃあ、やってみましょう。
プログラムは無駄に長いので読み飛ばしてください。
まず、以下のマクロを実行します。このマクロ%deep0は入力ワードを受け取って
そのお尻の1文字をとり、そこから始まる言葉で一番文字数が多いものを返すマクロです。
選択肢が複数ある場合は乱数で決めます。
%macro deep0(sente=Y);
/*先は読まずにとにかく一番長い言葉を選ぶマクロ*/
%let time = %eval(&time+1);
/*詰まされていないか判定*/
proc sql noprint;
select count(*) into :obs
from dic
where atama = first(reverse("&in_word"));
quit;
%if &tumi ne Y %then %do;
%if &obs > 0 %then %do;
data minmax;
length text1 $32.;
set dic ;
where atama = first(reverse("&in_word"));
text1 = text;
score1 = len;
siri = first(compress((reverse(text1))));
drop text atama siri len;
run;
data time&time._hyouka;
set minmax;
call streaminit(&seed);
ransu = rand('uniform');
run;
proc sort data = time&time._hyouka;
by descending score1 ransu;
run;
data _null_ ;
set time&time._hyouka;
if _N_=1 then do;
call symputx( 'in_word' ,text1,'g');
%if &sente = Y %then %do;
call symputx( 'p1_score' ,score1+&p1_score ,'g');
%end;
%else %do;
call symputx( 'p2_score' ,score1+&p2_score ,'g');
%end;
end;
run;
%put 選択したワード &in_word ;
%put 現在の先手得点 &p1_score ;
%put 現在の後手得点 &p2_score ;
data temp;
length time 8. ban $4. word $32.;
ban = ifc(mod(&time,2) = 1 ,'先','後');
time = &time;
word = "&in_word";
p1_score = &p1_score;
p2_score = &p2_score;
output;
run;
proc append base = kekka data=temp;
run;
data dic;
set dic;
where text ne "&in_word";
run;
%end;
%else %do;
%let tumi=Y;
%if &sente = Y %then %do;
%let p1_score = -9999;
%end;
%else %do;
%let p2_score = -9999;
%end;
%put 選択したワード ワード切れ負け ;
%put 現在の先手得点 &p1_score ;
%put 現在の後手得点 &p2_score ;
data temp;
length time 8. ban $4. word $32.;
ban = ifc(mod(&time,2) = 1 ,'先','後');
time = &time;
word = "切れ負け";
p1_score = &p1_score;
p2_score = &p2_score;
output;
run;
proc append base = kekka data=temp;
run;
%end;
%end;
%mend deep0;
そしたら、以下の対戦マクロに設定をいれて、実行します。
今回は、ワードのもとをSAS関数の名前にします。なのでアルファベットでしりとりです。
※SASのバージョンによってSASHELPライブラリの関数テーブルに入っているデータが違うので
実行環境によって結果が違います。
ちなみに一度使った言葉は使用できず、もし選択できる言葉がなくなった場合はその時点で負けです。
そのルールで、先ほどの%deep0同士を対戦させてみましょう。
最初に与える言葉は最近忘備録で取り上げられていたSCAN関数にしてみます。
%macro battle;
/*-----------------------
対戦設定&実行マクロ
-------------------------*/
%global time tumi p1_score p2_score in_word;
%let in_word = SCAN; /*最初の言葉*/
%let p1_score=0; /*先手のハンデ*/
%let p2_score=0; /*後手のハンデ*/
%let endturn = 15; /*何周で終わるか*/
%let seed=777; /*同じ評価値の場合、どの言葉を選ぶかの乱数シード*/
/*前回までの結果をリセット*/
proc datasets lib=work kill memtype=data;
run;
%let tumi = ;/*ワード切れによる負け判定フラグ*/
/*使用辞書*/
data dic;
set sashelp.vfunc;
where fncname ne '';
text=upcase(fncname);
atama=first(text);
siri=first(compress(reverse(text)));
len=length(fncname);
if input(siri,?? best.) in (0:9) then delete;/*数字で終わる関数は除外*/
keep atama text len siri;
run;
%let time = 0;/*何手目*/
/*ここで対戦させるマクロを指定*/
%do %while(&time < &endturn * 2 and &tumi = );
%deep0(sente=Y)
%deep0(sente=N)
%end;
%mend battle;
/*実行*/
%battle
結果(データセットkekka)をみてみると、選択された言葉と、その時点の先手後手の点数が入ってます。
まず1手目、先手はNLMYDESC関数を選び、9文字なのでスコアは9です。そして2手目、後手はCから始まる関数ということでCOMPANION_NEXT関数という14文字のものを選んでスコア14です。
最終的にどうなったかをみると
30手の終了時点で、先手が178点、後手が188点で後手の勝ちということになります。
ちなみに先手後手それぞれが各手番で、なぜその言葉を選んだかの思考ログの中身は
手番ごとにデータセットに入ってます
例えば、一手目先手がNLMYDESC関数を選んだのか、データセットTIME1_HYOKAをみてみると
Nから始まる関数は41個（画像は途中まで）ありますが、その中で一番長いのは9文字で、あとはたまたま乱数が一番小さい先頭レコードがNLMYDESC関数だったから選ばれたということがわかります。
さて、今回は先手が微差で負けてしまいました。開始する言葉を変えたり、乱数を変えれば結果は変わるでしょう。しかしここで、そういった条件は変えずに、アルゴリズムを改良して先手を勝ちに導くことはできないでしょうか？
あなたなら、どのようなロジックで常に最高得点で返してくる敵を倒しますか？
今回は、1手相手の手を先読みしてミニマックス法で評価値をだしてそれによって指してを決定するということを考えてみましょう。
ミニマックス法とは、想定される最大の損害が最小になるように決断する方法と説明されます。
わかりにくいので、実装用に方向を揃えたネガマックス法で説明すると、要するに自分も相手もお互いにとっての最高得点の手を選択するとして、自分の得と相手の得の差が最大の手を選べば勝てんじゃね？っていう割と当たり前の発想です。
わかりにくいので、実装用に方向を揃えたネガマックス法で説明すると、要するに自分も相手もお互いにとっての最高得点の手を選択するとして、自分の得と相手の得の差が最大の手を選べば勝てんじゃね？っていう割と当たり前の発想です。
例えば自分が10点の手を指しても、その次に相手が11点の手をさせる手が予想できるなら、それよりも自分が9点の手であっても、その次に相手が8点しか返せない手を優先させるべきでしょって感じです。
実際につくってみましょう
以下のような感じになりました。
マクロ名は%deep1です。
%macro deep1(sente=Y);
/*1手先を読むマクロ*/
%let time = %eval(&time+1);
/*詰まされていないか判定*/
proc sql noprint;
select count(*) into :obs
from dic
where atama = first(reverse("&in_word"));
quit;
%if &tumi ne Y %then %do;
%if &obs > 0 %then %do;
data minmax;
length text1 text2 $32.;
set dic ;
where atama = first(reverse("&in_word"));
if _N_ = 1 then do;
declare hash h1(dataset:'dic',multidata:'Y');
h1.definekey('atama');
h1.definedata('text','len','siri');
h1.definedone();
end;
text1 = text;
score1 = len;
siri = first(compress((reverse(text1))));
rc = h1.find(key:siri);
if rc ^= 0 then do;
text2="";
score2=9999;
output;
end;
if rc = 0 then do;
text2=text;
score2 = -1 * len;
output;
do while(rc=0);
rc=h1.find_next(key:siri);
if rc = 0 then do;
text2=text;
score2 = -1 * len;
if text1 ne text2 then output;
end;
end;
end;
drop rc text atama siri len;
run;
data minmax2;
set minmax;
myscore = 0;
yourscore=0;
array ascore{*} score:;
do i = 1 to dim(ascore);
if mod(i,2) = 1 then do;
myscore + ascore{i};
if myscore >= 9999 then ascore{i} = 9999;
end;
if mod(i,2) = 0 then do;
yourscore + -1*ascore{i};
if yourscore <= -9999 then ascore{i} = -9999;
end;
if i + &time > &endturn * 2 +1 then ascore(i) = .;
end;
call streaminit(&seed);
ransu = rand('uniform');
total = sum(of score:);
drop i;
run;
proc sort data = minmax2;
by text1 descending score1 score2;
run;
data time&time._hyouka;
set minmax2;
by text1 descending score1 score2;
if first.text1;
run;
proc sort data = time&time._hyouka;
by descending total ransu;
run;
data _null_ ;
set time&time._hyouka;
by descending total ransu;
if _N_=1 then do;
call symputx( 'in_word' ,text1,'g');
%if &sente = Y %then %do;
call symputx( 'p1_score' ,score1+&p1_score ,'g');
%end;
%else %do;
call symputx( 'p2_score' ,score1+&p2_score ,'g');
%end;
end;
run;
%put 選択したワード &in_word ;
%put 現在の先手得点 &p1_score ;
%put 現在の後手得点 &p2_score ;
data temp;
length time 8. ban $4. word $32.;
ban = ifc(mod(&time,2) = 1 ,'先','後');
time = &time;
word = "&in_word";
p1_score = &p1_score;
p2_score = &p2_score;
output;
run;
proc append base = kekka data=temp;
run;
data dic;
set dic;
where text ne "&in_word";
run;
%end;
%else %do;
%let tumi=Y;
%if &sente = Y %then %do;
%let p1_score = -9999;
%end;
%else %do;
%let p2_score = -9999;
%end;
%put 選択したワード ワード切れ負け ;
%put 現在の先手得点 &p1_score ;
%put 現在の後手得点 &p2_score ;
data temp;
length time 8. ban $4. word $32.;
ban = ifc(mod(&time,2) = 1 ,'先','後');
time = &time;
word = "切れ負け";
p1_score = &p1_score;
p2_score = &p2_score;
output;
run;
proc append base = kekka data=temp;
run;
%end;
%end;
%mend deep1;
そして先述の%battle内の、先の%deep0マクロを%deep1(sente=Y)として、実行すると
結果は
最終的に%deep1の先手150点と%deep0の後手107点で、1手先読みするマクロが勝利しました。
例えば、初手を見てみるとNから始まる言葉の最大は9文字のものがあるはずですが、敢えて8文字のNHOLIDAYを選択しています。なぜかは先ほどと同じくデータセットTIME1_HYOKAを開いてみると
先ほど%deep0で先手をやった際に選択していたNHOLIDESC関数は優先順位として9番目の位置になっています。何故かというと、確かに選択すると自分に9点入るのですが、その次の相手のターンでCから始まる関数にCOMPANION_NEXTという14文字のものがあるため
9 - 14でトータル-5点で、自分が不利になると評価したからです。
これを見ると1手目でNHOLIDAYかNHOLIDLENを選べば、評価値は0で、少なくとも不利にならないということがわかるわけです。
さて、まあ今回の例の場合、ワードもとにしているデータが小さいことから、割と一本道の変化が多く、開始する言葉によっては先読みしてても負けるケースは多々あります。
開始語をランダムに変えて、何回も勝負させて、1手先読みによって勝率がどれくらい上がるかをっ測ろうかとも思いましたが、もう充分長い記事になったのでこの辺にしておきます。
0 件のコメント:
コメントを投稿