「リバーシのアルゴリズム」に関する補足

工学社「リバーシのアルゴリズム」に関する訂正や追加情報などを掲載します。

お詫びと訂正

「リバーシのアルゴリズム」にいくつかの誤りが見つかりましたので、この場で訂正するとともに、ご迷惑をおかけした読者の皆様にお詫び申し上げます。また、他にも誤りを発見された場合はメールでお知らせください。

最終更新日: 2006年3月26日

P.	誤	正	備考
22	index = y*9 + x + 1;	index = y*9 + x;	(x, y)が1-origin(1から数える)の場合の式です。0-originの場合はindex = (y+1)*9+(x+1)となります。
33	[Board.h (C++版)] std::vector<std::vector<Point> > UpdateLog;	std::vector<std::vector<Disc> > UpdateLog;	付属ソースコードは正しく修正されています。
48	for (int x=0; x<BOARD_SIZE; x++)	for (int x=1; x<=BOARD_SIZE; x++)	付属ソースコードは正しく修正されています。
48	for (int y=0; y<BOARD_SIZE; y++)	for (int y=1; y<=BOARD_SIZE; y++)	付属ソースコードは正しく修正されています。
49	for (int x=0; x<BOARD_SIZE; x++)	for (int x=1; x<=BOARD_SIZE; x++)	付属ソースコードは正しく修正されています。
49	for (int y=0; y<BOARD_SIZE; y++)	for (int y=1; y<=BOARD_SIZE; y++)	付属ソースコードは正しく修正されています。
53	Discs[EMPTY]--;	Discs[EMPTY]++;
79	[alpha-beta法の擬似コード] if (score => beta)	if (score >= beta)
82	[negamax法の擬似コード] if (score => beta)	if (score >= beta)
85	t > a && t < beta && 最初のノードでない && limit <= 2	t > a && t < beta && 最初のノードでない && limit > 2
85	(NegaScoutの擬似コードがfail-softでない)		詳細は下記「NegaScout: fail-softな探索」を参照してください。
87	登録する評価値が真の値なのか、下限値(alpha)なのか上限値(beta)なのか	登録する評価値が真の値なのか、下限値(beta以上)なのか上限値(alpha以下)なのか	置換表については、Thell3.0のアルゴリズム解説に詳しく記述しています。
89	[AIクラス(Java版)] public int normal_depth = 15;	public int normal_depth = 5;	付属ソースコードではAI.javaの8行目に当たります。併せて修正してください。
91	int eval, alpha = numeric_limits<int>::min();	int eval, alpha = -numeric_limits<int>::max();
92最終行	evaluate(board);	return evaluate(board);
95	[moveメソッド] int eval, eval_max = Integer.MIN_VALUE;	int eval, eval_max = -Integer.MAX_VALUE;
95	[moveメソッド] eval = -alphabeta(board, limit-1, -Integer.MAX_VALUE, -Integer.MIN_VALUE);	eval = -alphabeta(board, limit-1, -Integer.MAX_VALUE, Integer.MAX_VALUE);
95	[moveメソッド] if(eval > eval_max) p = (Point) movables.get(i);	if(eval > eval_max) { eval_max = eval; p = (Point) movables.get(i); }
96	for (current = 1; current < moves.size(); current++)	for (current = begin+1; current < moves.size(); current++)
109	中盤の評価関数には全滅での負け手に無限小の評価値	negamax/negascoutを探索に用いている場合は最小値としてnumeric_limits<int>::min()(C++)やInteger.MIN_VALUE(Java)を用いるのは避けるべきです。かわりに-numeric_limits<int>::max()(C++)やInteger.MAX_VALUE(Java)を用いるようにします。これは、多くのCPUが負数を表すのに2の補数表現を用いており、負の最小値の符号を反転すると(正の最大値+1)になって、結局オーバーフローして元の値(負の最小値)になってしまうため、正しい結果が得られなくなってしまうためです。
145	快速船は白9石勝ちと言われています。	快速船は引き分けと言われています。
(付属コード)	[AI.java: alphabetaメソッド] return evaluate(board);	return Eval.evaluate(board);
(付属コード)	[Board.cpp: flipDiscsメソッド及びundoメソッド] 開放度(Liberty)のインクリメントとデクリメントが逆になっていました。正しくは本文P.104にあるとおり、flipDiscsメソッドでデクリメントし、undoメソッドでインクリメントします。

NegaScout: fail-softな探索

P.85のNegaScoutの擬似コードはfail-softではありません。fail-softでないことによって探索の結果を間違うことはありませんが、NegaScoutの目的である探索効率の向上が難しいコードになってしまっています。より効率のよい、fail-softなコードにするには、以下のようにします。

int negascout(int limit, int alpha, int beta)
{
  if (limit == 0) return 評価値; // 深さ制限に達した
  
  // ここでパスの処理
  
  可能な手を全て生成(よさそうな順にソート);

  int a, b, t;
  int score_max = -∞;
  a = alpha;
  b = beta;
  
  foreach (それぞれの手) {
    手を打つ;
    t = -negascout(limit-1, -b, -a);

    if (t > a && t < beta && 最初のノードでない && limit > 2) {
      // null window searchによって「このノードはこれまでのノードよりも悪い」
      // ことの証明を試みたが、予想が外れたためきちんと再探索する必要がある
      t = -negascout(limit-1, -beta, -t);
    }
    手を戻す;
    
    if (t > score_max) {
      if (t >= beta) return t; // β刈り
      score_max = t;
      a = max(a, t);
    }
    
    b = a+1; // 新しい null windowを設定
  }
  
  return score_max;
}

本文に掲載したコードとの違いは、「子ノードの評価値がどれもαを超えなかった場合には、出現した評価値の最大(α以下の値)を返す」としている点です。(本文中のコードでは、そのような場合αを返しています。) このような性質をfail-softであるといいます。fail-softかどうかは単純なαβ探索のみを行う場合には関係ありませんが、置換表を組み合わせる探索や、null window searchによる事前探索を行うNegaScoutのようなアルゴリズムにおいては、fail-softの方が局面の評価値の存在範囲に関するより詳細な情報を返せるため、より多くの枝刈りが可能になって探索が高速化します。

なおNegaScoutは子ノードがよい順(評価値の高い順)に並んでいることを前提としていますので、必ず手の並べ替えを行う必要があります。

また、再探索が必要な条件のうち、「limit > 2」の不等号の向きが逆になっていましたので訂正します。

参考文献等

本書の執筆及びThellの開発にあたって参考にしたWebページや文献はこちらです。本書の内容を超えるトピックについて知りたい方は、それらの文献やThell 3.0のアルゴリズム解説が役立つでしょう。

本書のコードや付属のThell 2.3.2は弱すぎる！という方へ

Thell 3.0をどうぞ。

戻る