GA将?開発日記~王の理とは~

ネタ勢最強を目指して絶賛開発中。

評価値の展開による局面評価の高速化

 だれでもやってる当然の事かもしれませんが、軽くググってみても出て来なかったんで書いてみます。

 まず、現在のGA将!!!!!!の駒割・絶対位置評価関連の評価項目は下記の通りです。

  1. 駒割(盤上の駒)
  2. 駒割(持ち駒)
  3. 筋・段個別の絶対位置評価
  4. 絶対位置評価

 んで、今の実装で駒を移動させる場合の評価値差分計算のコードは下記の様になります。

 (this->scoreが差分計算した先手にとっての評価値を格納する変数です。また、下記コードは先手の駒が成らずに移動する場合を想定しています。)

if(相手の駒を取る場合) {
    this->score += 盤上の取られる駒の価値;                     // 上記1の評価値
    this->score += 盤上の取られる駒の元いた位置に応じた評価値; // 上記3,4の評価値
    this->score += 取る駒の持ち駒としての価値;                 // 上記2の評価値
}// if(...)

// 移動による絶対位置評価値の更新
this->score -= 移動する駒の移動元の位置に応じた評価値; // 上記3,4の評価値
this->score += 移動する駒の移動先の位置に応じた評価値; // 同上

 んで、これだと局面遷移のたびにあっちこっちの配列を参照するので、速度的に結構問題あるコードです。

 そこで、探索開始前に、上記1,3,4の評価値を足し合わせて別の配列に格納しておけば(展開すれば)、配列参照の回数を減らせれます。

 展開部分を擬似コードで書くとこんな感じ。

// 展開後の評価値。添字は順に盤上の駒の位置・駒種。
double deployedScore[ 81 ][ 14 ];

// 対局開始前の処理。
for( size_t i = 0; i < 81; i++ ) {

    for( size_t j = 0; j < 14; j++ ) {

        this->deployedScore[ i ][ j ]  = j番目の駒の価値;
        this->deployedScore[ i ][ j ] += j番目の駒の(i%9+1)筋にいる場合の価値;
        this->deployedScore[ i ][ j ] += j番目の駒の(i/9+1)段にいる場合の価値;
        this->deployedScore[ i ][ j ] += j番目の駒のマスiにいる場合の価値; 

    }// for(..j..)

}// for(..i..)

 んで、こうすればdeployedScore[ i ][ j ]を読めばi番目のマスにいる駒jの評価値(上記1,3,4の合計)が一発で求まります。

 他にも、持ち駒の評価値やら、二駒相対位置関係の評価値と二駒絶対値関係の評価値やら、そういうパラメータにも応用可能です。

 という訳で、次期バージョンのGA将では上記の方式を実装予定。5〜10%程度の高速化は可能だと皮算用しています。

 他にも高速化のアイデアは色々あるので、全部まとめて50%前後高速化…出来るとイイなぁ。