モンテカルロ木探索で一人不完全情報ゲーム「計算」を賢くする[4]


2015年 09月 28日

前回、「計算」のプレイに必要なデータと基本となるメソッドを紹介した。
今回は、これらを組み合わせて、「計算」を最後までプレイするメソッドを仕上げる。

現状の盤面から始めて、ひたすら何も考えずランダムにプレイするメソッド simpleplayout を用意した。

double    simpleplayout() {
  for(;;) {
    opentefuda();                // 手札をめくる

    ArrayList    list  = getAllMoves();  // 札の移動を考える
    if( list.size() == 0 )
    break;

    Move    mv = selectRandomly(list);
    mv.exec();
  }

  return    restcount==0 ? 1.0 : 0.0;
}

プレイを続けられる限り永久ループを繰り返し、続けられなくなって抜けたところで、残り枚数を調べ、成功率をdouble(1.0または0.0)で返す。
返り値として、残り枚数やtrue/falseにせず成功率sにしているのは、モンテカルロ木探索で利用することを考えてのことであるが、理由については読み進めば自然に分かると思う。

ループ中では、手札を表にできれば行う。
次に、可能なカードの動きを集め、可能な動きがないとき、ループを終える。
可能な Move があるときは、そのうちの1つの Moveオブジェクトを実行する。

手札のオープンは、まず手札のオープン状態を調べ、オープンしない、できない場合は単に終了する。
そうでないとき、残り手札の中から1枚選び、手札のトップと、手札配列を更新する。

void opentefuda() {
  if( tefudatop != 0 || tefudalen <= 0 )
    return;

  // 手札から一枚選ぶ
  int  r = rnd.nextInt(tefudalen);
  tefudatop = tefuda[r];
  tefuda[r] = tefuda[--tefudalen];
}

可能なカードを動きを全部集めるのが getAllMovesメソッド。
Moveの空リストを作り、屑札台札移動可能な場合をリストに加える。
表の手札がなければそこまで。
次に、手札台札で可能な場合をリストに加える。手札台札移動は常に可能なので、直接Moveオブジェクトを作っている。

ArrayList<move> getAllMoves() {
  ArrayList<move> list = new ArrayList<move>();

  for( int k=0; k<KUZUNUM; ++k ) {    // 屑札移動を集める
    for( int d=0; d<DAINUM; ++d ) {
      Move nx = nextKuzufudaDaifuda( k, d );
      if( nx != null )
        list.add(nx);
    }
  }

  if( tefudatop == 0 )                // 手札終了チェック
    return    list;

  for( int d=0; d<DAINUM; ++d ) {        // 手札台札を集める
    Move nx = nextTefudaDaifuda(d);
    if( nx != null )
    list.add(nx);
  }

  for( int k=0; k<KUZUNUM; ++k ) {
    // 手札屑札を集める
    Move nx = new Move( MoveType.手札屑札, tefudatop, k, 0 );
    list.add(nx);
  }

  return    list;
  }

カードの移動Move リストの中から1つだけ選ぶとき、0個、1個と2個以上に分け、2個以上の場合だけ乱数で選んでいる。

Move selectRandomly( ArrayList<move> list ) {
  int    sz = list.size();
  if( sz == 0 )
    return    null;
  if( sz == 1 )
    return    list.get(0);

  int  r = rnd.nextInt(list.size());
  return    list.get(r);
}

以上で道具は揃うのだが、初期状態にする initializeが必要である。
読めば分かると思うが、最後に台札の初期化を行っている。 LEADLEVELが台札に最初に何枚乗っていたかを示す。1のとき「計算」になり、0のとき「コンピュータ」になる。2以上にすれば、最初から台札に何枚も重なった状態から始めることができる。
メソッドinitdaifuda(d)は、台札の山をdで指定し、一定間隔開いた数字の札を載せる。札を載せることで、その分手札の山が減るので、その対応もしている。なお、initdaifuda(d)は省略する。

void initialize() {
        MAXCOUNT = MAXNUM * DAINUM;

        tefudalen = 0;
        for( int i=0; i<DAINUM; ++i )
            for( int j=1; j<=MAXNUM; ++j ) {
                tefuda[tefudalen++] = j;
            }
        tefudatop = 0;

        kuzu    = new int[KUZUNUM][MAXCOUNT];
        kuzulen = new int[KUZUNUM];

        for( int i=0; i<DAINUM; ++i ) {
            daifudatop[i] = 0;
            daifudanext[i] = daifudagap[i];
        }

        restcount = MAXCOUNT;

        for( int i=0; i<LEADLEVEL; ++i ) {
            for( int d=0; d<DAINUM; ++d ) {
                initdaifuda(d);
            }
        }
}

ここまで準備ができたら、動かすことができる。
1回だけプレイするのが、 メソッドonegameであり、とても簡単。

double    onegame() {
  initialize();
  return    simpleplayout();
}

これを延々と呼びだして、成功回数を計算するメソッドgames()を用意した。

void games() {
  int    success = 0;

  for( int i=0; i&lt;GAMECOUNT; ++i ) {

    if( onegame() &gt; 0.5 )
      ++success;
  }

  System.out.printf("\n\tGame end,\t%d/%d %8.5f\n",
  success, GAMECOUNT, (double)success/GAMECOUNT );
}

ここまでで、実際にプレイアウトすることができる。若干示していないメソッドなどあるが、勝手に加えて動くようにしよう。

さて、これで、どのくらいの成功率になるだろうか?
それは、次回のお楽しみにしよう。