将棋ソフト改良中
この三連休は土曜日は、ことだま結社向け原稿。
日曜日は、外出
月曜は、部屋の掃除&模様替えをやってたので、
将棋ソフト改良にはあまり使えませんでした。
Futility Pruningは、解説を読むとalpha方面のカットしか言及されてないようですが、
どうせなら、静止探索値-マージン>=betaもカットすることにしてみました。
このほうが、たくさん刈れますし(^^;
文章で書くと、悪そうな手はカットする。だけじゃなくて、ベータカットが起きそうな手は、
次の深さの探索で、ベータカットが起きたことにする。って感じかな?
これってprobCutみたいなもんかも。
//------------------- // Futility Pruning //------------------- // Futility Pruning at Pre-Frontier Nodes) if( depth+2==depthMax ) { v=negaMaxQui( SorE,-MUGEN,+MUGEN,depth,depth+2 ); if( (v+MARGIN2 <= alpha) || (v-MARGIN2 >= beta) ) { futility2++;return v; } } // Futility Pruning at Frontier Nodes else if( depth+1==depthMax ) { v=negaMaxQui( SorE,-MUGEN,+MUGEN,depth,depth+2 ); if( (v+MARGIN1 <= alpha) || (v-MARGIN1 >= beta) ) { futility++;return v; } } // Limited Razoring at Pre-Pre-Frontier Nodes else if( depth+3==depthMax ) { v=negaMaxQui( SorE,-MUGEN,+MUGEN,depth,depth+2 ); if( (v+MARGIN3 <= alpha) || (v-MARGIN3 >= beta) ) { futility3++;depthMax--; } }
Null-move forward pruningもやってます。
//----------------------------- // Null-move forward pruning //----------------------------- if( (depth>0) && (doNull==0) ) { push();nullMove(SorE); v = -AlphaBeta(enemy(SorE),-beta-1,-beta,depth+1,depthMax-PASSR, 1,1 ); nullUndo(SorE);pop(); if( v>=beta ) { nullMoveCount++;return v; } }
PASSRはとりあえず3にしてます。
動かしてみると、
[34手目]後手 ▼持駒v歩2 9 8 7 6 5 4 3 2 1 ---------------------------+ v香v桂 ・ ・v金v玉 ・v桂v香|一 ・ ・ ・v銀 ・ ・v金v銀 ・|二 v歩 ・v歩v歩 ・v歩 ・ ・v歩|三 ・v飛 ・ ・ ・v角 ・ ・ ・|四 ・ ・ ・ ・v歩 ・ 歩 ・ ・|五 ・ ・ 歩 ・ ・ ・ 飛 ・ ・|六 歩 歩 ・ 歩 歩 歩 ・ ・ 歩|七 ・ 角 金 ・ 王 銀 金 ・ ・|八 香 桂 銀 ・ ・ ・ ・ 桂 香|九 ---------------------------+ △持駒 歩2 詰め探索:(0)不詰み generate: 49moves 01 0.02sec -125 ▼74飛 02 0.03sec -298 ▼74飛△69王 02 0.05sec -231 ▼31王△69王 03 0.17sec -217 ▼31王△56歩▼54飛△55歩▼同角△同角 03 0.22sec -131 ▼86歩打△66角▼74飛 04 0.33sec -272 ▼86歩打△66角▼82飛△88銀▼87歩成△同銀 04 0.39sec -217 ▼31王△56歩▼54飛△55歩▼同角△同角▼同飛 05 1.73sec -163 ▼31王△56歩▼54飛△57銀▼33歩打△55歩▼同角△同角 05 3.19sec -67 ▼35角△56歩▼34飛△37歩打▼56歩△同飛 06 6.39sec -67 ▼35角△56歩▼34飛△37歩打▼56歩△同飛 07 13.23sec -2067 ▼35角△同飛▼86歩打△同歩▼同飛△54角打▼28歩打△同金 07 14.53sec -2066 ▼31王△75歩▼42金 07 17.47sec -2065 ▼71銀△75歩▼31王 07 21.75sec -79 ▼33歩打△77角▼74飛△69王▼76飛 BEST:▼33歩打△77角▼74飛△69王▼76飛 SearchNode:46831 QuiNode:7178822 EvalCall:8112409 Futility:8697/3441/2221 NullMove:4649 oneMove:185
みたいな感じで、FutilityPruningで、残1〜3で8697/3441/2221のカットが発生している。
NullMoveも強力で、4649のカットが発生している。
oneMoveは、探索中に手が1手しか無い場合は、それ以降は探索してもムダなので、そこまででカットする
(orderingで最善手と次の手の評価がかなり開いていた場合は1手しかないと見なす。というのもやっている)