-
Notifications
You must be signed in to change notification settings - Fork 0
/
search.go
188 lines (151 loc) · 6.03 KB
/
search.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
package take13
import (
"math/rand"
l03 "github.com/muzudho/kifuwarabe-wcsc31/lesson03"
l08 "github.com/muzudho/kifuwarabe-wcsc31/take8"
)
const RESIGN_VALUE = -32768
const MAX_VALUE = 32767
var nodesNum int
var depthEnd int = 1 // 3 はまだ遅い。 2 だと駒を取り返さない。
type CuttingType int
const (
CuttingNone = CuttingType(0)
CuttingKingCapture = CuttingType(1)
)
// Search - 探索部
func Search(pPosSys *PositionSystem) l03.Move {
nodesNum = 0
curDepth := 0
//fmt.Printf("Search: depth=%d/%d nodesNum=%d\n", curDepth, depthEnd, nodesNum)
bestMove, bestVal := search2(pPosSys, curDepth)
// 評価値出力(^~^)
App.Out.Print("info depth %d nodes %d score cp %d currmove %s pv %s\n",
curDepth, nodesNum, bestVal, bestMove.ToCodeOfM(), bestMove.ToCodeOfM())
// ゲーム向けの軽い乱数
return bestMove
}
// search2 - 探索部
func search2(pPosSys *PositionSystem, curDepth int) (l03.Move, int16) {
//fmt.Printf("Search2: depth=%d/%d nodesNum=%d\n", curDepth, depthEnd, nodesNum)
// 指し手生成
// 探索中に削除される指し手も入ってるかも
// TODO 空き王手チェックは(^~^)?
moveList := GenMoveList(pPosSys, pPosSys.PPosition[POS_LAYER_MAIN])
moveListLen := len(moveList)
//fmt.Printf("%d/%d moveListLen=%d\n", curDepth, depthEnd, moveListLen)
if moveListLen == 0 {
return l03.RESIGN_MOVE, RESIGN_VALUE
}
// 同じ価値のベストムーブがいっぱいあるかも(^~^)
var bestMoveList []l03.Move
var bestMove = l03.RESIGN_MOVE
// 最初に最低値を入れておけば、更新されるだろ(^~^)
var bestVal int16 = RESIGN_VALUE
// 相手の評価値
var opponentWorstVal int16 = MAX_VALUE
var younger_sibling_move = l03.RESIGN_MOVE
// 探索終了
var cutting = CuttingNone
// その手を指してみるぜ(^~^)
for i, move := range moveList {
// App.Out.Debug("move=%s\n", move.ToCode())
from, _, _ := move.Destructure()
// デバッグに使うために、盤をコピーしておきます
pPosCopy := NewPosition()
copyBoard(pPosSys.PPosition[0], pPosCopy)
// DoMove と UndoMove を繰り返していると、ずれてくる(^~^)
if pPosSys.PPosition[POS_LAYER_MAIN].IsEmptySq(from) {
// 強制終了した局面(^~^)
App.Out.Debug(SprintBoard(
pPosSys.PPosition[POS_LAYER_MAIN],
pPosSys.phase,
pPosSys.StartMovesNum,
pPosSys.OffsetMovesIndex,
pPosSys.createMovesText()))
// あの駒、どこにいんの(^~^)?
App.Out.Debug(l08.SprintLocation(pPosSys.PPosition[POS_LAYER_MAIN]))
panic(App.LogNotEcho.Fatal("Move.Source(%d) has empty square. i=%d/%d. younger_sibling_move=%s",
from, i, moveListLen, younger_sibling_move.ToCodeOfM()))
}
pPosSys.DoMove(pPosSys.PPosition[POS_LAYER_MAIN], move)
nodesNum += 1
// TODO ここで自玉に王手がかかるようなら、被空き王手(^~^)
// 取った駒は棋譜の1手前に記録されています
captured := pPosSys.CapturedList[pPosSys.OffsetMovesIndex-1]
// 玉を取るのは最善手
if l03.What(captured) == l03.PIECE_TYPE_K {
bestMove = move
bestVal = pPosSys.PPosition[POS_LAYER_MAIN].MaterialValue
cutting = CuttingKingCapture
} else {
if curDepth < depthEnd {
// 再帰
_, opponentVal := search2(pPosSys, curDepth+1)
// 再帰直後(^~^)
// App.Out.Debug(pPosSys.Sprint(POS_LAYER_MAIN))
if opponentVal < opponentWorstVal {
// より低い価値が見つかったら更新
bestMoveList = nil
bestMoveList = append(bestMoveList, move)
opponentWorstVal = opponentVal
} else if opponentVal == opponentWorstVal {
// 最低値が並んだら配列の要素として追加
bestMoveList = append(bestMoveList, move)
}
} else {
// 葉ノードでは、相手の手ではなく、自分の局面に点数を付けます
// 自玉と相手玉のどちらが有利な場所にいるか比較
control_val := EvalControlVal(pPosSys)
materialVal := pPosSys.PPosition[POS_LAYER_MAIN].MaterialValue
leafVal := materialVal + int16(control_val)
//fmt.Printf("move=%s leafVal=%6d materialVal=%6d(%s) control_val=%6d\n", move.ToCode(), leafVal, materialVal, captured.ToCode(), control_val)
if bestVal < leafVal {
// より高い価値が見つかったら更新
bestMoveList = nil
bestMoveList = append(bestMoveList, move)
bestVal = leafVal
} else if bestVal == leafVal {
// 最高値が並んだら配列の要素として追加
bestMoveList = append(bestMoveList, move)
}
}
}
pPosSys.UndoMove(pPosSys.PPosition[POS_LAYER_MAIN])
// 盤と、コピー盤を比較します
diffBoard(pPosSys.PPosition[0], pPosCopy, pPosSys.PPosition[2], pPosSys.PPosition[3])
// 異なる箇所を数えます
errorNum := errorBoard(pPosSys.PPosition[0], pPosCopy, pPosSys.PPosition[2], pPosSys.PPosition[3])
if errorNum != 0 {
// 違いのあった局面(^~^)
App.Out.Debug(pPosSys.SprintDiff(0, 1))
// あの駒、どこにいんの(^~^)?
App.Out.Debug(l08.SprintLocation(pPosSys.PPosition[0]))
App.Out.Debug(l08.SprintLocation(pPosCopy))
panic(App.LogNotEcho.Fatal("error: count=%d younger_sibling_move=%s move=%s", errorNum, younger_sibling_move.ToCodeOfM(), move.ToCodeOfM()))
}
younger_sibling_move = move
if cutting != CuttingNone {
break
}
}
switch cutting {
case CuttingKingCapture:
// 玉取った
default:
if curDepth < depthEnd {
// 葉以外のノード
// 相手の評価値の逆が、自分の評価値
bestVal = -opponentWorstVal
}
bestmoveListLen := len(bestMoveList)
//fmt.Printf("%d/%d bestmoveListLen=%d\n", curDepth, depthEnd, bestmoveListLen)
if bestmoveListLen > 0 {
// 0件を避ける(^~^)
bestMove = bestMoveList[rand.Intn(bestmoveListLen)]
}
// 評価値出力(^~^)
// App.Out.Print("info depth 0 nodes %d score cp %d currmove %s pv %s\n", nodesNum, bestVal, bestMove.ToCode(), bestMove.ToCode())
}
return bestMove, bestVal
}