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
|
use crate::moves::Move;
use super::Grossmeister;
/// https://www.chessprogramming.org/Node_Types
#[derive(Debug, PartialEq, Clone, Copy)]
pub enum NodeType {
/// Principal variation node - exact score
PV,
/// Fail-high
Cut,
/// Fail-low
All,
}
#[derive(Debug, PartialEq, Clone, Copy)]
pub struct TranspositionTableItem {
/// Zobrist hash of this position
pub hash: u64,
pub mov: Option<Move>,
pub depth: u8,
pub score: f32,
pub node_type: NodeType,
}
pub const TTABLE_SIZE: u64 = 2u64.pow(23);
#[derive(Debug, Clone)]
struct TranspositionTable {
table: Vec<Option<TranspositionTableItem>>,
}
impl Default for TranspositionTable {
fn default() -> Self {
Self {
table: vec![None; TTABLE_SIZE as usize],
}
}
}
impl TranspositionTable {
fn set(&mut self, hash: u64, item: TranspositionTableItem) {
self.table[(hash % TTABLE_SIZE) as usize] = Some(item);
}
/// This operation is safe from collisions since it compares the *full* hash
/// TODO: only compare the other half of the hash
fn get(&self, hash: u64) -> Option<&TranspositionTableItem> {
self.table[(hash % TTABLE_SIZE) as usize]
.as_ref()
.and_then(|item| if item.hash == hash { Some(item) } else { None })
}
fn len(&self) -> usize {
self.table.iter().filter(|item| item.is_some()).count()
}
}
#[derive(Debug, Default, Clone)]
pub struct MasterTable {
/// Always contains the most recent transposition
always_replace: TranspositionTable,
/// Stores highest-depth entries
depth_preferred: TranspositionTable,
/// Used to collect Principal Variation. Not used in search
pv: TranspositionTable,
}
impl Grossmeister {
pub fn transposition(&self) -> Option<&TranspositionTableItem> {
self.transposition_table
.depth_preferred
.get(self.board.hash)
.or(self.transposition_table.always_replace.get(self.board.hash))
}
pub fn store_transposition(&mut self, transposition: TranspositionTableItem) {
self.transposition_table
.always_replace
.set(self.board.hash, transposition);
if match self
.transposition_table
.depth_preferred
.get(self.board.hash)
{
Some(existing_transposition) => transposition.depth >= existing_transposition.depth,
None => true,
} {
self.transposition_table
.depth_preferred
.set(self.board.hash, transposition)
}
// Store PV/Cut nodes in PV table
// Note: Cut nodes are probably only relevant in close-to-mate situations
if match transposition.node_type {
NodeType::PV => true, // Always replace PV nodes
NodeType::Cut => match self.transposition_table.pv.get(self.board.hash) {
Some(existing_transposition) => existing_transposition.node_type != NodeType::PV,
None => true,
},
_ => false,
} {
self.transposition_table
.pv
.set(self.board.hash, transposition)
}
}
/// Extract current node information from PV table
pub fn pv(&self) -> Option<&TranspositionTableItem> {
self.transposition_table.pv.get(self.board.hash)
}
pub fn table_full(&self) -> u64 {
let total_entries = self.transposition_table.always_replace.len()
+ self.transposition_table.depth_preferred.len();
let total_size = TTABLE_SIZE * 2;
(1000.0 * (total_entries as f64 / total_size as f64)) as u64
}
}
|
