マルチコアマシン環境における並列最良探索アルゴリズム

Best-First Heuristic Search for Multicore Machinesという論文をまとめたスライドです。

Ethan Burns, Sofia Lemons, Wheeler Ruml and Rong Zhou. (2010). Best-First Heuristic Search for Multicore Machines. Journal of Artificial Intelligence Research 39(2010) 689-743

内容は並列最良探索です。A*探索などの基本的な探索アルゴリズムを知っていることを前提としています。
よければどうぞ。

Zobrist Hashing

Zobrist Hashingは将棋やチェスなどで用いられる、状態をハッシュ値に落とし込む方法です。

というのも将棋やチェスのような状態のハッシュ値を計算する場合、n進数や辞書順によるハッシュ関数では状態空間に対してハッシュ値を不偏的に散らすことはなかなか難しいです。そこでZobrist Hashingは乱数とXORを使って不偏性を作り出します。


WikipediaのZobrist Hashingの擬似コードを引用します。

   constant indices
       white_pawn := 1
       white_rook := 2
       # etc.
       black_king := 12
   
   function init_zobrist():
       # fill a table of random numbers/bitstrings
       table := a 2-d array of size 64×12
       for i from 1 to 64:  # loop over the board, represented as a linear array
           for j from 1 to 12:      # loop over the pieces
               table[i][j] = random_bitstring()
   
   function hash(board):
       h := 0
       for i from 1 to 64:      # loop over the board positions
           if board[i] != empty:
               j := the piece at board[i], as listed in the constant indices, above
               h := h XOR table[i][j]
       return h

(Wikipediaより: http://en.wikipedia.org/wiki/Zobrist_hashing)


・init_zobrist
まず下準備として、予めパズルの各マスに対してランダムビットstringを定義する。
例えば将棋なら、
７六に歩がある状態を 0100 0111 のように定義する。
７七に角がある状態を 1001 1100...
のように全てのマスの、全てのありうる状態に対するキーの値をテーブルに保存する。（以後テーブル値とする。）


・hash(board)
全てのマスの状態に対して定義されたテーブル値をビット毎のXORでかけていく。


さて、このZobrist Hashingの特徴を見ていきましょう。

・まず、Zobrist HashingはPerfect Hashingである保証は全くありません。盤が違う状態でも同じハッシュ値になり得ます。簡単な例だと
0000 XOR 0011 = 0011
0100 XOR 0111 = 0011
ですので。

・そこから一歩進んで、このハッシュ関数は同じフレームワークの中でビット長を変えることでハッシュの重複度を変化させることが出来ます。つまり、ビットを長くするほど違う盤の状態が同じハッシュ値を持つ割合(確率)を小さくさせることが出来ます。これは当然計算速度とメモリ量のトレードオフになります。

・n進数や辞書順によるハッシュ関数と比較して、盤の状態に対して偏りのないハッシュ値が得られることが多い。Bitwise XORなのでハッシュ値のビットストリングの各桁は、全てのマスの状態の関数なので、全てのマスのテーブル値を参照した結果の値といえる。ただしここで注意しなければならないのは、必ず偏りがないハッシュになるとは限らないということです。それは状態空間の性質にもよりますし、乱数の揺れにも依存します。



天才的な発想ですよね。どの位実用されているのかはよく知らないのですが、こういうアイディアの出せる人間になりたいものですね。




C++で簡単なサンプルを実装をしたものが以下のコードです。

/*
 * zobrist.cc
 *
 * Short sample to test Zobrist hashing.
 * Zobrist hashing is a hash function construction for abstract board games.
 *
 *
 *  Created on: Jun 10, 2014
 *      Author: Yuu Jinnai
 */

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define INDICES 16
#define SIZE 32

void initZobrist(int* table);
void initRandomBoard(int* board);
int hash(int* board);

int* table;

int main() {

 srand(time(NULL));
 table = new int[SIZE*INDICES];
 initZobrist(table);

 int* board = new int[SIZE];
 for (int i = 0; i < 10; ++i) {
  initRandomBoard(board);
  printf("hash(board) = %d\n\n", hash(board));
 }

}

void initZobrist(int* table) {
 for (int i = 0; i < SIZE; ++i) {
  for (int j = 0; j < INDICES; ++j) {
   table[i+SIZE*j] = rand();
   printf("table[%d][%d] = %d\n", i, j, table[i+SIZE*j]);
  }
 }
}

void initRandomBoard(int* board) {
 for (int i = 0; i < SIZE; ++i) {
   board[i] = rand() % INDICES;
   printf("%d ", board[i]);
 }
 printf("\n");
}

int hash(int* board) {
 int h = 0;
 for (int i = 0; i < SIZE; ++i) {
  h = (h ^ table[i+SIZE*board[i]]);
 }
 return h;
}






 

データ構造とアルゴリズム

データ構造とアルゴリズムの本は五万とありますね。アプリケーションレベルに近いほど多様性を増していくというのは書籍の数にも表れますね。

しかし考えてみると、データ構造やアルゴリズムというのは離散数学なので、例えばマージソートの説明の仕方にそんな五万通りもあるようには思えません。

逆に、アルゴリズムを学ぶメリットというのはアルゴリズムが汎用的であり、一度根幹を学べば同じフレームワークを似た問題で何度も使えるというところにあると思います。

つまるところ、汎用的で再利用可能であることが特にアルゴリズムを学ぶべき理由であると思います。そうすると、javaアルゴリズムだとかC++アルゴリズム事典だとかいう本はややアドホックにすぎるように思えます。

でもこういうアドホックな本が出回るのは自然なことで、アルゴリズムが抽象的すぎて学習しずらいということは大いにあるでしょう。目的からの距離が遠いですから。

データ構造とアルゴリズムで一番評判の高い本はIntroduction to Algorithmsでしょう。


しかしこの鈍器に等しい厚さの数学書を一人で全て理解しきることが出来る人はそんなにいないでしょう。

そこで、なんとも素晴らしいことに、MITOPENCOURSEWAREでこの本の講義が開かれております。

Introduction to Algorithms MIT OPEN COURSEWARE

You TubeのVideo Lectureに比べて充実しているのは、Video Lectureだけでなく講義ノート、宿題や試験とその解答まで公開されていることです。MITの学生と殆ど変わらない学習環境になるんじゃないでしょうか。


もっと薄い和書だとデータ構造とアルゴリズム(杉原厚吉)とかがコンパクトにまとまっています。しかし薄いということは内容が凝縮されていることであって必ずしも簡単だとは限らないと思います。いずれにせよ上の洋書があまりにもきついという人はこちらから初めてもよいように思います。

自動作曲所感

自動作曲ってどこまで可能なんでしょう。

今ある自動作曲というのもかなりのクオリティの「楽譜」を作ることができるようです。試したことのない方はこちらより試せます。

Orpheus

WolframTones

これらの、現状の自動作曲とは素晴らしい音楽をボタン一つで作製するというものではなく、簡単な音楽を簡単に作れるようにするというものです。

さて、とりあえず現状どんな用途がありますでしょうか。

上記のように簡単な音楽は本当にボタン一つで作れてしまいます。例えば面白いフリーゲームを作りたいけどBGMが作れないという時にはかなり便利だと思います。今まではフリー素材を使うしかなかったのに対して一応？オリジナルの曲を用意できます。

そういう意味で非常に意味のあるアプリケーションでしょう。一部の人しかできなかったことをオープンにするというのは気持ちのいいものです。

また、元々作曲をしているという人にも有用なもののようです。適当に作曲させて面白いフレーズが出てきたら自分の曲に使うことができます。

産業的なインパクトは結構大きくなっていくんじゃないでしょうか。だけれども「自動作曲」の名を冠するには大きな懸隔があるように思えます。

…というのはクラシカルな音楽が好きな人間だけでしょうが、それでも言わせて下さい。

いまの自動作曲が単独でアートを作ることはないでしょう。アートというと表現するということですが自動作曲のアルゴリズムにそういうものはありません。(そもそもアルゴリズム単独でアートというのが可能なのか。)「元気な」とか「ロック」とかの指定は出来ますが。

CGにおける河口洋一郎先生のような方も出て来るかもしれません。しかしそれにはツールを設計するところまで含めてのプロセスになるでしょう。

また、作曲というのは音程とリズムだけではありません。そういう曲ももちろんいくらでもありますしそれらも音楽ですが、曲想や音色と切り離して音程・リズムがあるというのはちょっとしっくり来ません。現状このあたりは暫定的にツールが用意したパターンを引き出しているだけですが、これらもアルゴリズムで計算できないものでしょうか。

今の人工知能一般の限界として、人間が評価するものは人間の方がうまく作れるんでしょうね。将棋とかなら勝ち負けという与えられたルールがありますが、音楽において良い音楽というのを定式化するのは非常に難しいです。そもそも良い音楽を作るのが目的じゃないという人もいるでしょうし、うーん。

結局、クオリティを求める音楽は自動作曲をツールとして使っても人間が作ることになります。それでも万々歳ですがコンピュータの人としてはもう少し威張りたいものですね。


でもやっぱり、世界に一番インパクトを与えるアーティスト？というのは初音ミクになるでしょう。その初音ミクの楽曲に豊かさをもたらす技術というのはやはり偉大だと思います。

とりあえず１０年後、どうなるか。