-
Notifications
You must be signed in to change notification settings - Fork 1
/
zobrist.go
114 lines (91 loc) · 2.92 KB
/
zobrist.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
package board
import "math/rand"
// ZobristHash is a position hash based on piece-squares. It is intended for
// 3-fold repetition draw detection and hashes "identical" positions under
// that rule to the same hash value.
//
// See also: https://research.cs.wisc.edu/techreports/1970/TR88.pdf.
type ZobristHash uint64
// ZobristTable is a pseudo-randomized table for computing a position hash.
type ZobristTable struct {
pieces [NumColors][NumPieces][NumSquares]ZobristHash
castling [NumCastling]ZobristHash
enpassant [NumSquares]ZobristHash
turn [NumColors]ZobristHash
}
func NewZobristTable(seed int64) *ZobristTable {
ret := &ZobristTable{}
r := rand.New(rand.NewSource(seed))
for c := ZeroColor; c < NumColors; c++ {
for p := ZeroPiece; p < NumPieces; p++ {
for sq := ZeroSquare; sq < NumSquares; sq++ {
ret.pieces[c][p][sq] = ZobristHash(r.Uint64())
}
}
ret.turn[c] = ZobristHash(r.Uint64())
}
for i := ZeroCastling; i < NumCastling; i++ {
ret.castling[i] = ZobristHash(r.Uint64())
}
for sq := ZeroSquare; sq < NumSquares; sq++ {
if sq.Rank() == Rank3 || sq.Rank() == Rank6 {
ret.enpassant[sq] = ZobristHash(r.Uint64())
}
}
return ret
}
// Hash computes the zobrist hash for the given position.
func (z *ZobristTable) Hash(pos *Position, turn Color) ZobristHash {
var hash ZobristHash
for sq := ZeroSquare; sq < NumSquares; sq++ {
if c, p, ok := pos.Square(sq); ok {
hash ^= z.pieces[c][p][sq]
}
}
hash ^= z.castling[pos.Castling()]
if ep, ok := pos.EnPassant(); ok {
hash ^= z.enpassant[ep]
}
hash ^= z.turn[turn]
return hash
}
// Move computes a hash for the position after the (legal) move incrementally. Cheaper than
// computing it for the new position directly.
func (z *ZobristTable) Move(h ZobristHash, pos *Position, m Move) ZobristHash {
hash := h
turn, _, _ := pos.Square(m.From)
// (1) Undo existing metastatus
hash ^= z.castling[pos.Castling()]
if ep, ok := pos.EnPassant(); ok {
hash ^= z.enpassant[ep]
}
hash ^= z.turn[turn]
// (2) Update hash based on moved pieces and new status
hash ^= z.pieces[turn][m.Piece][m.From]
switch m.Type {
case Capture:
hash ^= z.pieces[turn.Opponent()][m.Capture][m.To]
hash ^= z.pieces[turn][m.Piece][m.To]
case Promotion:
hash ^= z.pieces[turn][m.Promotion][m.To]
case CapturePromotion:
hash ^= z.pieces[turn.Opponent()][m.Capture][m.To]
hash ^= z.pieces[turn][m.Promotion][m.To]
case EnPassant:
hash ^= z.pieces[turn][m.Piece][m.To]
epc, _ := m.EnPassantCapture()
hash ^= z.pieces[turn.Opponent()][Pawn][epc]
case KingSideCastle, QueenSideCastle:
hash ^= z.pieces[turn][m.Piece][m.To]
from, to, _ := m.CastlingRookMove()
hash ^= z.pieces[turn][Rook][from]
hash ^= z.pieces[turn][Rook][to]
default:
hash ^= z.pieces[turn][m.Piece][m.To]
}
hash ^= z.castling[pos.Castling()&m.CastlingRightsLost()]
ept, _ := m.EnPassantTarget()
hash ^= z.enpassant[ept]
hash ^= z.turn[turn.Opponent()]
return hash
}