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


2015年 11月 09日

さて、ひと通り完結するまで、あと少しであるので、完成させ、ちょっと走らせて様子を見てみよう。

実際に新しいノードを付け加える処理を以下に示す。

// 手札をめくってでた札(数)に対する、新しいノードを1つだけ作る。
Node    makeOpenBranch( Node parent, Move mv ) {
  int     i = mv.fudanum;
  Node    nd = parent.children[i];
  if( nd==null ) {
    nd = parent.children[i] = new Node( parent, mv );
    ++parent.childcnt;
  }

  return    nd;
}

やってきることは、親と子ノードの関係を調整しているだけであるので、細かい説明は省略する。

もう1つ出てくるのが、Nodeクラスのメンバーメソッド addSuccess( double sr ) である。

void    addSuccess( double sr ) {
    ++playcount;
    successsum += sr;
    success = successsum / playcount;
    recountSuccess();
  }

これは、プレイアウトした結果得られた成功率(1.0または0.0)を木に反映させる。

注目しているノードに関しての処理だけでは不十分で、木を上にたどりながら、プレイアウト回数および成功率を木のルートに至るまで書き換えていかなければならない。
そのために、recountSuccess()を用意した。

成功率の書き換えを次で行っている。

// 成功率を再帰的に書き換える
void  recountSuccess() {

  for( Node pr=this; pr!=null; pr=pr.parent) {
    if( pr.childcnt == 0 )
      continue;
    pr.playcount = 0;
    for( Node nd : pr.children )
      if( nd != null )
        pr.playcount += nd.playcount;

    if( pr.childmovetype ) {        // 成功率最大を選ぶ
      double    max = -1;
      for( int i=0; i<pr.children.length; ++i ) {
        Node    ch = pr.children[i];
        if( ch==null)
          continue;
        if( ch.success > max ) {
          pr.success = max = ch.success;
        }
      }
      pr.success = max;
    } else {        // 手札をめくる場合 // 成功率は平均となる
      double    ave = 0.0;
      for( Node ch : pr.children ) {
        if( ch==null )
          continue;
        ave += ch.success * ch.playcount / pr.playcount;
      }
      pr.success = ave;
    }
  }
}

最初のforループを周回する度に、木を1段ずつ上がっていく。

最初のところで、プレイアウト総数の計算を行っている。

次に成功率を求めているのだが、札を移動する場合と、手札をめくる場合に場合分けされている。
札移動の場合には、子のノードの中から、一番高い成功率を親ノードの成功率としている。
手札オープンの場合には、どの手を選ぶかの選択権はなく、神の指示に従うしかないので、子ノード全体の成功率の平均を求めて、親ノードの成功率としている。

さて、これで一応必要なものは準備できたので、実行してみよう。

プレイアウト数を1000回、閾値を5で実行してみた。

Game end, rest=32       0/1  0.00000
Hand:     _ : 
Table:  8(9)  6(8)  9(Q)  J(2) 
[1]  Q9TTKKA5J85JKQ829QA7KA254TJT6937
[2]  
[3]  
[4]  

なぜか[1]の屑札の山だけにたくさんあって、他の屑札の山には何もない。
なぜ?

最初の方も見てみよう。

Hand:     Q : K9JT56789TJQKA23456789TJQKA23456789TJQKA2345678

---- game ----  step  1  success= 0.00000
Hand:     9 : K9JT56789TJQKA23456788TJQKA23456789TJQKA234567
Table:  A(2)  2(4)  3(6)  4(8) 
[1]  Q
[2]  
[3]  
[4]  

---- game ----  step  2  success= 0.00059
Hand:     4 : K9JT56789TJQKA23456788TJQKA23756789TJQKA23456
Table:  A(2)  2(4)  3(6)  4(8) 
[1]  Q9
[2]  
[3]  
[4]  

---- game ----  step  3  success= 0.00059
Hand:     T : K9JT56789TJQKA234567886JQKA23756789TJQKA2345
Table:  A(2)  4(6)  3(6)  4(8) 
[1]  Q9
[2]  
[3]  
[4]  

---- game ----  step  4  success= 0.00053
Hand:     T : K9JT56789TJQKA234567886JQKA237567895JQKA234
Table:  A(2)  4(6)  3(6)  4(8) 
[1]  Q9T
[2]  
[3]  
[4]  

最初から、ずっと屑札[1]にしか札が積まれていない。
最後の台札の状態

Table:  8(9)  6(8)  9(Q)  J(2)

を見ると、少しは台札に重ねられているが、手札屑札移動は、手札→屑札[1] に限定されているようだ。

なぜ?
これでは絶対に成功しない。
何か間違えたかな。
…ということで、この原因を次回までに考えよう。