-
Notifications
You must be signed in to change notification settings - Fork 1
/
minimax.go
89 lines (78 loc) · 2.19 KB
/
minimax.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
package search
import (
"context"
"github.com/herohde/morlock/pkg/board"
"github.com/herohde/morlock/pkg/eval"
"github.com/seekerror/stdlib/pkg/util/contextx"
)
// Minimax implements naive minimax search. Useful for comparison and validation.
// Pseudo-code:
//
// function minimax(node, depth, maximizingPlayer) is
//
// if depth = 0 or node is a terminal node then
// return the heuristic value of node
// if maximizingPlayer then
// value := −∞
// for each child of node do
// value := max(value, minimax(child, depth − 1, FALSE))
// return value
// else (* minimizing player *)
// value := +∞
// for each child of node do
// value := min(value, minimax(child, depth − 1, TRUE))
// return value
//
// See: https://en.wikipedia.org/wiki/Minimax.
type Minimax struct {
Eval Evaluator
}
func (m Minimax) Search(ctx context.Context, sctx *Context, b *board.Board, depth int) (uint64, eval.Score, []board.Move, error) {
run := &runMinimax{eval: m.Eval, b: b}
score, moves := run.search(ctx, sctx, depth)
if contextx.IsCancelled(ctx) {
return 0, eval.Score{}, nil, ErrHalted
}
return run.nodes, score, moves, nil
}
type runMinimax struct {
eval Evaluator
b *board.Board
nodes uint64
}
// search returns the positive score for the color.
func (m *runMinimax) search(ctx context.Context, sctx *Context, depth int) (eval.Score, []board.Move) {
m.nodes++
if contextx.IsCancelled(ctx) {
return eval.ZeroScore, nil
}
if m.b.Result().Outcome == board.Draw {
return eval.ZeroScore, nil
}
if depth == 0 {
return eval.HeuristicScore(m.eval.Evaluate(ctx, sctx, m.b)), nil
}
hasLegalMove := false
score := eval.NegInfScore
var pv []board.Move
moves := m.b.Position().PseudoLegalMoves(m.b.Turn())
for _, move := range moves {
if m.b.PushMove(move) {
s, rem := m.search(ctx, sctx, depth-1)
m.b.PopMove()
hasLegalMove = true
s = eval.IncrementMateDistance(s).Negate()
if score.Less(s) {
score = s
pv = append([]board.Move{move}, rem...)
}
}
}
if !hasLegalMove {
if result := m.b.AdjudicateNoLegalMoves(); result.Reason == board.Checkmate {
return eval.NegInfScore, nil
}
return eval.ZeroScore, nil
}
return score, pv
}