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
| require "./board"
require "./piece"
require "./utils"
module Fork
LOSE = -90000i32
INFINITY = 100000i32
LOOKUP_SIZE = 1048576
struct Result
getter move : Move?
getter score : Int32
def initialize(@move : Move?, @score : Int32)
end
def swap
@score = -@score
end
end
class Search
getter depth : Int32
getter board : Fork::Board
getter already_searched : Hash(UInt64, Int32) = Hash(UInt64, Int32).new(LOOKUP_SIZE)
getter move_table : Array(Array(Fork::Move | Nil)) =
Array(Array(Fork::Move | Nil)).new(32) { Array(Fork::Move | Nil).new(32) { nil } }
getter best_moves_yet : Array(Fork::Move | Nil) = [] of (Fork::Move | Nil)
def initialize(@board : Fork::Board, @depth = 5)
end
def run
1.upto(@depth) do |cur_depth|
@already_searched = Hash(UInt64, Int32).new(LOOKUP_SIZE)
@best_moves_yet = @move_table[0].first(cur_depth - 1)
search(max_depth: cur_depth)
end
@move_table[0].first(@depth)
end
def search(board : Board = @board, alpha : Int32 = -INFINITY, beta : Int32 = INFINITY, ply : Int32 = 0, max_depth : Int = @depth) : Int32
side = board.side
return Eval.eval(board, side) if ply == max_depth
best = LOSE
moves = Moves.generate(board)
best_move_from_prev = @best_moves_yet[ply]?
if !best_move_from_prev.nil?
if index = moves.index(best_move_from_prev)
moves[index] = moves[0]
moves[0] = best_move_from_prev
end
end
moves.each do |m|
copy = board.dup
legal = copy.make_move(m)
next unless legal
next if @already_searched[copy.hash]?.try { |searched_ply| searched_ply <= ply }
res = -search(copy, -beta, -alpha, ply + 1, max_depth)
@already_searched[copy.hash] = ply
if best < res
best = res
end
if res > alpha
alpha = res
@move_table[ply][ply] = m
(ply + 1).upto(max_depth) do |i|
@move_table[ply][i] = @move_table[ply + 1][i]
end
end
break if alpha >= beta
end
if best == LOSE
if board.checked?(side)
return LOSE
else
return 0i32
end
end
best
end
end
end
|