自分のことだけ考えるマクロと相手のことも考えるマクロを対戦させて遊ぶ。ミニマックス法とかの話

今回もかなり役に立たない、書いてる僕だけが楽しい話になります。

例えば、しりとりをして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手先読みによって勝率がどれくらい上がるかをっ測ろうかとも思いましたが、もう充分長い記事になったのでこの辺にしておきます。



SASで作った迷路をSASで解いてやったぞ!誰もそんなこと求めてないのは知ってるけどね!な話

ブログ「僕の頁 <SASと臨床試験と雑談と>」のSASNAMIさんも最近RWIに手をだされて、のっけから素晴らしい記事を書かれてます。

Report Writing Interface (RWI)を試してみる
http://sasboku.blog.fc2.com/blog-entry-54.html

そして、そのSASNAMIさんに火をつけた張本人である忘備録のa.matsuさんはというと、以下のような記事を書いて、もう何か色々イっちゃってます。

RWIで迷路を作る
http://sas-boubi.blogspot.jp/2015/08/rwi.html


迷路作成プログラムできましたか、matsuさんが迷路をSASで生成するというのなら
それならば僕はその迷路を解くプログラムを書きましょう!

というわけで、どうやって解くかなのです。迷路解法アルゴリズムは色々あるみたいなのですが
今回はセルオートマトンというものを使って解いてみましょう。

迷路生成部分と、それをRWIで描画する部分は忘備録の丸コピでいかせていただきます。
※ちょっとだけ迷路のサイズを小さくしているのは、解法過程をGIFアニメにするのにデフォルトの設定でちょうど1枚に入りきる、いいサイズにしたかったからです。アルゴリズム的にはどんな巨大な迷路でも解けます。


%let n    = 31;
%let init = 1234;

data DT1;
  *** 全マス目分の配列を定義 ;
  array AR(&n, &n) ;

  *** 最初から壁にする部分を2に設定 ;
  do y=1 to &n;
      do x=1 to &n;
         if x in (1,&n) or y in (1,&n) or mod(x*y,2)=1 then AR(x,y)=2;
         else AR(x,y)=1;
      end;
  end;

  *** 乱数を生成して壁の位置を決める ;
  *** 壁の位置 1:上、2:下、3:右、4:左 ;
  call streaminit(&init);
  do y=3 to &n-2 by 2;
  do x=3 to &n-2 by 2;

     *** 1段目は上下左右の壁の乱数を生成 ;
     if y=3 then do;
         * 左のマスが壁だったら上下右のみの壁の乱数を生成 ;
         if AR(x-1,y)=2 then  RAND = ceil(rand('uniform')*3);
         else RAND = ceil(rand('uniform')*4);
     end;

     *** 2段目以降は下左右の壁の乱数を生成 ;
     if y^=3 then do;
         * 左のマスが壁だったら下右のみの壁の乱数を生成 ;
         if AR(x-1,y)=2 then  RAND = ceil(rand('uniform')*2)+1;
         else RAND = ceil(rand('uniform')*3)+1;
     end;

     if RAND=1 then AR(x,y-1)=2; * 上 ;
     if RAND=2 then AR(x,y+1)=2; * 下 ;
     if RAND=3 then AR(x+1,y)=2; * 右 ;
     if RAND=4 then AR(x-1,y)=2; * 左 ;
  end;
  end;
run;

描画描画部分については、マクロ化しています。

%macro rwi(data=);
/*描画マクロ*/
data _NULL_;
  length VAR1 $5.;
  set &data;
  array AR(&n, &n);
  dcl odsout ob();
  ob.table_start();

  do y=1 to &n;
      ob.row_start();

      do x=1 to &n;

         *** 壁と床を描画 ;
          VAR1="";
          if (x=2 and y=2) or (x=&n-1 and y=&n-1) then VAR1="☆";
          ob.format_cell(data:VAR1,  style_attr: "background=" || choosec(AR(x,y),"white","black") ||
                                                                  " height=0.4cm  width=0.3cm");
      end;

      ob.row_end();
  end;

  ob.table_end();
run;
%mend;

そして、ここからが解法部分のコードになります。

%macro automaton;
/*GIFアニメの開始設定*/
options  ANIMATION=START  ANIMDURATION=0.5   PRINTERPATH=GIF ;
ods printer file="/home/sasyamasasyama0/sasuser.v94/meiro.gif"; ;

/*初期局面の描画*/
%rwi(data=DT1)

/*世代データセットの作成*/
data _DT1(genmax=2);
set DT1;
run;

/*ループ脱出条件*/
%let stop = ;

%do %until(&stop=1);
data _DT1;
array AR(&n, &n);
set _DT1;

do i=2 to &n-1;
do j=2 to &n-1;
if ^(i=2 and j=2) & ^(i=&n-1 and j=&n-1) then do;
if sum(AR{i-1, j}=2 , AR{i+1, j}=2 , AR{i, j-1}=2 , AR{i, j+1}=2)=3 then AR{i, j}=2;
end;
end;
end;
run;

/*ハッシュオブジェクトのequalsメソッドで1世代前のデータセットと差があるかを0 1で判定する*/
data _null_;
if 0 then set _DT1;
declare hash hq1(dataset:'_DT1');
hq1.defineKey(all:'yes');
hq1.defineDone();
declare hash hq2(dataset:'_DT1(gennum=-1)');
hq2.defineKey(all:'yes');
hq2.defineDone();
hq1.equals(hash: 'hq2', result: FL);
call symputx('stop',FL);
run;

/*描画*/
%rwi(data=_DT1)

%end;

/*アニメ終了*/
ods printer close ;
options  ANIMATION=STOP ;
%mend automaton;

/*マクロ実行*/
%automaton

結果は









静止画で初期局面と最終局面を見てみると




となって正解のルートだけが残ります。
本当はこの正解の結果を初期局面にもっていって、そのルートにだけ色つけようかと思いましたが
ちょっと面倒になったのでここまでで。

で、実は解法の肝は
if sum(AR{i-1, j}=2 , AR{i+1, j}=2 , AR{i, j-1}=2 , AR{i, j+1}=2)=3 then AR{i, j}=2;
の一行だけなんです。

要するに、あるセルがあって、そのセルの周囲3方向が壁である場合、そのセルは行き止まりであって正解の通路ではないことが確定するといえますよね?
じゃあ、そういうセルは壁にしてしまおうという発想です。それを何回も何回も繰り返します。
そうやって、行き止まりを次々壁に塗り替えていくことで、周囲3方向が壁ではないセルだけが残ります。つまり、正解のルートが浮かびかがってくるわけです。

ただ、このアルゴリズムは迷路に、複数の空白セルが広場のようになっていたり、本ルート以外の意味のないループ道があった場合、それを削ることができないものになっています。
迷路の世界も奥が深いんですね。

SAS的には何回もデータステップを繰り返して、同名のデータセットを上書きしまくってます。
ただし、(genmax=2) の設定により、更新の1つ前のデータセットをDT1(gennum=-1) と書くことで
取得できるようになっています。

更新しても、更新前と内容が変わらない イコール 正解の通路だけが残っているということなので
そうなったらループを抜けます。

今回は更新前後の比較にハッシュオブジェクトのequalsメソッドを使っています。これは僕が単にハッシュ好きということもありますが、今回はどこに差があったかはどうてもよくて、同じか否かだけを01でみたいので、compareプロシジャよりやりやすいと考えたからです

【参考】
ハッシュオブジェクトの世界⑦ コンペア革命 equalsメソッド

で、GIFファイルの作成部分については忘備録の記事をそのまま使わせていただきました。

SASでアニメーションを作る方法(SAS9.4以降)

う~ん、結局、人の褌で…みたいになってしまいましたが、まあ勘弁してください。

若干、GIIFだとセルの大きさが乱れたりしてますが、何ででしょうかね。PDFじゃないから??
まあ、遊びの出力なので大目にみてくださいな。