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

use cache::Cache;
use gen::legal_moves;
use mv_list::{MoveCounter, MoveVec};
use num_cpus;
use position::Position;
use std::sync::mpsc::channel;
use threadpool::ThreadPool;

pub fn perft(
  position: &mut Position,
  depth: usize,
  multi_threading_enabled: bool,
  cache_bytes_per_thread: usize,
) -> usize {
  if depth == 0 {
    return 1;
  }

  if depth <= 3 {
    return perft_inner(position, depth);
  }

  if !multi_threading_enabled {
    if cache_bytes_per_thread > 0 {
      let mut cache = Cache::new(cache_bytes_per_thread).unwrap();
      return perft_with_cache_inner(position, depth, &mut cache);
    } else {
      return perft_inner(position, depth);
    }
  }

  let pool = ThreadPool::new(num_cpus::get());
  let (tx, rx) = channel();

  let mut moves = MoveVec::new();
  legal_moves(&position, &mut moves);
  let moves_len = moves.len();

  for &mv in moves.iter() {
    let tx = tx.clone();
    let mut position_local = position.clone();

    pool.execute(move || {
      position_local.make(mv);

      let count: usize;
      if cache_bytes_per_thread > 0 {
        let mut cache = Cache::new(cache_bytes_per_thread).unwrap();
        count = perft_with_cache_inner(&mut position_local, depth - 1, &mut cache);
      } else {
        count = perft_inner(&mut position_local, depth - 1);
      }

      tx.send(count).unwrap();
    });
  }

  return rx.iter().take(moves_len).sum();
}

pub fn perft_inner(position: &mut Position, depth: usize) -> usize {
  if depth == 1 {
    let mut counter = MoveCounter::new();
    legal_moves(&position, &mut counter);
    return counter.moves as usize;
  }

  let mut moves = MoveVec::new();
  legal_moves(&position, &mut moves);

  let state = position.state().clone();
  let key = position.hash_key();
  let mut count = 0;
  for &mv in moves.iter() {
    let capture = position.make(mv);

    count += perft_inner(position, depth - 1);

    position.unmake(mv, capture, &state, key);
  }

  count
}

fn perft_with_cache_inner(position: &mut Position, depth: usize, cache: &mut Cache) -> usize {
  let key = position.hash_key();

  let ret = cache.probe(key, depth);
  if ret.is_some() {
    return ret.unwrap();
  }

  let mut count = 0;
  if depth == 1 {
    let mut counter = MoveCounter::new();
    legal_moves(&position, &mut counter);
    count = counter.moves as usize;
  } else {
    let mut moves = MoveVec::new();
    legal_moves(&position, &mut moves);

    let state = position.state().clone();
    let key = position.hash_key();
    for &mv in moves.iter() {
      let capture = position.make(mv);

      count += perft_with_cache_inner(position, depth - 1, cache);

      position.unmake(mv, capture, &state, key);
    }
  }

  cache.save(key, count, depth as i16);

  count
}

#[cfg(test)]
mod test {
  use super::*;
  use position::{Position, STARTING_POSITION_FEN};
  use test;

  #[test]
  fn perft_test_3() {
    let mut position = Position::from_fen(STARTING_POSITION_FEN).unwrap();

    assert_eq!(perft(&mut position, 3, false, 0), 8902);
  }

  #[test]
  fn perft_test_4() {
    let mut position = Position::from_fen(STARTING_POSITION_FEN).unwrap();

    assert_eq!(perft(&mut position, 4, false, 0), 197281);
  }

  #[test]
  fn perft_with_cache_test_3() {
    let mut position = Position::from_fen(STARTING_POSITION_FEN).unwrap();

    assert_eq!(perft(&mut position, 3, false, 1024 * 1024), 8902);
  }

  #[test]
  fn perft_with_cache_test_4() {
    let mut position = Position::from_fen(STARTING_POSITION_FEN).unwrap();

    assert_eq!(perft(&mut position, 4, false, 1024 * 1024), 197281);
  }

  #[bench]
  fn perft_bench_starting_position(b: &mut test::Bencher) {
    let mut position = Position::from_fen(STARTING_POSITION_FEN).unwrap();

    b.iter(|| -> usize { perft(&mut position, 2, false, 0) });
  }
}