2009-11-26

■　Bonanzaで使われているinsertion sortとは何か？

Bonanzaで使われているsort(並べ替え)は、
1) insertion sort
2) shell sort
3) quick sort
の3種類である。

3)はCのqsort関数を呼び出しているだけなので解説は不要だろう。また、3)は定跡データベースのメンテナンスにのみ使われており、実際の探索で使われているのは1),2)のみだ。

また、2)には1)が必要である。そこで、今回は1)について解説する。

■　Bonanzaのnext.c

Bonanzaのnext.cは、次の指し手を生成するcoroutineである。ここでinsertion sortが使われている。

指し手生成をcoroutineにしないでいきなり全部の手を生成したり、全部の手に対して点数をつけてquick sortしたりすると劇的なパフォーマンスの低下を招くのでそれは絶対に避けたほうが良いと思う。

さて、next.cで使われているソートはinsertion sortであり、この配列には数手しか入っていない(どんな手が入っているのかは今回解説しない)ので、insertion sortならば非常に高速である。

  psortv[n] = INT_MIN; // 末尾に番兵を置く
  for ( i = n-2; i >= 0; i-- )
  {
    // このsortv,moveがtmp変数だとみなせば、
    // ふつうの挿入ソート。ループ変数が逆方向に動くだけ。
    sortv = psortv[i];  move = pmove[i];
    for ( j = i+1; psortv[j] > sortv; j++ )
    {
      // 降順なので前にひとつずらしていく。
      psortv[j-1] = psortv[j];  pmove[j-1] = pmove[j];
    }
    psortv[j-1] = sortv;  pmove[j-1] = move;
  }

上のコードは「広く知られているinsertion sortのコードは駄目すぎる」(→ http://d.hatena.ne.jp/yaneurao/20091126 )にあるような、「広く知られているinsertion sortのコード」 + 番兵 + 降順ソートに書き換えたバージョンだ。

早い話が、上の処理を抜けたあとは、一番大きな点数をつけた指し手はpmove[0]に入っており、そのときの点数がpsortv[0]になる。

Bonanzaで使われているinsertion sortはたいてい上のパターンで書かれているので、上のパターンを知っていれば、「ああ、ここではpsortvの値が降順になるようにpmove[0]..[n-1]をソートしているんだな」と見た瞬間に理解できる。「for(int i=0; i < n ; ++i)」などと同じく、これは形で覚えるといいだろう。

「広く知られているinsertion sortのコードは駄目すぎる」の指摘にあるようにこのコードは最後にinsertが発生しないときもwrite backが発生するのでパフォーマンス的に見れば改善の余地があるコードであることも付記しておく。