トップ 差分 一覧 ソース 検索 ヘルプ RSS ログイン

Neothec3

Neothec3 - (may be) a strong reversi playing routine

Neothec040930.lzh(1318)

Key features.

 Statistical Fast Evaluation Function

Based on the famouse paper "Statistical Feature Combination for the Evaluation of Game Positions", Neothec3 has a statistics oriented evaluation function. It uses only patterns, not contains neither mobility nor parity, and so on. The evaluation function estimates the final score which both player plays optimal moves. The function is linear combination of weight of those patterns.

Patterns used in Neothec3:

  • hori 2-4
  • vert 2-4
  • diag 5-8
  • triangle
  • cor2x5
  • edge+2x

same as Turtle, almost same as LOGISTELLO.

Learning algorithm

The learning algorithm is my own algorithm, "Normalized difference algorithm". In this algorithm, fitness of the trained pattern set is much higher than the one trained in normal way. But the high quality traning method needs much more time than normal way.

 Pre-caliculation oriented Board

Almost all of the functions of the board is implemented with Dynamic-Programming technique. It use a lot of memory space but faster than normal implementation.

 Search algorithm suitable for fast evalution

Opening Book

Neothec3 doesn't have any opening book. I know it should be implemented, but using opening book is prohibited in the contest. It whould be implemented after the contest.

WLD(Win/Loss/Draw) search

Not implemented and there are no plans for it. Because the result of the WLDSearch introduce more winning chance but it may lost some discs.

Solve search

It is integreted to the middle search with iteractive deepening.

Middle search

Middle search is based on AlphaBeta with NegaMax algorithm. Because some well known features(such as MTD(f), TranspositionTable, History Heuristic and so on) are not suitable for the evalution function, I've done some trial&errors.

Forward cut algorithm is called CPC -Continous Probability Cut- which is a variation of ProbCut intended by LOGISTELLO.

Algorithms

I made some new idea during the development of Neothec3. Not all of them are not implemented in Neothec3, but some of these may be useful for other situation.

 LHH -Layered History Heuristc-

 ProbScout

 CPC -Continous Probability Cut-

//CPC
if(((beta-alpha)>1)&&(depth%2==0)){
	for(int d=0;d<=depth*2/5;d++){
		int bound = beta + (int)(PCTable[board.count-5][depth]*1.5);
		if(alphabeta(board,nextplayer,d,bound-1,bound,moved)<bound)
			break;
		if(d==depth*2/5)return beta;
	}

	for(int d=0;d<=depth*2/5;d++){
		int bound = alpha - (int)(PCTable[board.count-5][depth]*1.5);
		if(alphabeta(board,nextplayer,d,bound,bound+1,moved)>bound)
			break;
		if(d==depth*2/5)return alpha;
	}
}

Neothec3 - 強い(かもしれない)リバーシの思考ルーチン

特徴

 統計に基づく高速な評価関数

かの有名な論文"Statistical Feature Combination for the Evaluation of Game Positions"に基づき,Neothec3には統計志向の評価関数が用いられています。評価にはパターンのみを利用し,着手可能数や偶数理論などに基づくものは利用していません。評価関数はそのご両プレーヤーが最善の手を打ったと仮定した場合の最終結果を予測します。また,評価関数はパターンの評価重みの線形結合から成ります。

Neothec3で利用しているパターン:

  • 縦の列 2-4
  • 横の列 2-4
  • 斜めの列 5-8
  • 隅の3角形
  • 隅の2x5
  • 端の列+2x

Turtleと同じで, LOGISTELLOともほぼ同じものです。

学習アルゴリズム

学習アルゴリズムは"Normalized difference algorithm(正規化誤差アルゴリズム)"と名づけられた独自のアルゴリズムです。このアルゴリズムで学習したパターンセットは,通常の方法で学習したものより広範囲の状況に適応可能なものとなります。

 事前計算志向の盤表現

盤のほとんどの処理はダイナミック・プログラミングによって実現されています。この方法は従来の方法と比べて多くのメモリを必要としますが,高速です。

 高速な評価関数に対応した探索アルゴリズム

定石

Neothec3には定石はありません。実装したほうがいいのは分かっていますが,このコンテストでは禁止されています。コンテスト後に実装するかもしれません。

勝敗読み探索

実装されておらず,また実装する予定もありません。勝敗読みの結果は勝率を上げるかもしれませんが,石を失う可能性が高いからです。

終盤読み切り

反復深化法によって,中盤読みに統合されています。

中盤探索

中盤探索はαβ法にNegaMaxアルゴリズムを用いたものになっています。いくつかの有名な手法(MTD(f)や置換表やHistoryHeuristicなど)は高速な評価関数に対応していません。このため,いろいろと試行錯誤を行いました。

前向き枝刈りの方法はCPCと呼ばれる独自のアルゴリズムです。LOGISTELLOで採用されているProbCutに似たものです。

アルゴリズム

Neothec3を開発する過程でいくつかのアルゴリズムを考案しました。これら全てがNeothec3に搭載されているわけではありませんが,それらも異なった状況では有用かもしれません。

 LHH -Layered History Heuristc(階層化されたHistoryHeuristc)-

 ProbScout

 CPC -Continous Probability Cut(連続的ProbCut)-