~25% speedup in selfplay due to: incremental zobrist hashing, smarter road checking, re-using the input computed for the NN

1 files changed, 61 insertions, 1 deletions

diff --git a/include/actions.c b/include/actions.c
index 541b388..981214f 100644
--- a/include/actions.c
+++ b/include/actions.c
@@ -17,6 +17,7 @@
 
 #include "actions.h"
 #include "tak.h"
+#include "zobrist.h"
 
 #include <stdio.h>
 #include <stdlib.h>
@@ -135,7 +136,7 @@ action_t *actions_generate_at(tak_state_p state, uint32_t *num_actions,
       // Only try moves after CPS and if the colour is correct
       if (count) {
         if (state->ply >= 2 &&
-            ((state->colours[loc] & 1) == state->current_colour)) {
+            (TOP_COLOUR_AT(state, loc) == state->current_colour)) {
 
           // Pre-compute end-stops and crushes
           uint8_t end_stops[4], crushes[4] = {0, 0, 0, 0};
@@ -245,7 +246,18 @@ action_t *actions_generate_at(tak_state_p state, uint32_t *num_actions,
 
 void action_take(tak_state_p state, const action_t action) {
   const int8_t loc = A_GET_LOC(action);
+
+  // Incremental hash: record the affected cells and their current (pre-move)
+  // contributions, apply the move, then fold in the change.
+  uint8_t affected[7];
+  uint64_t old_contrib[7];
+  int n_aff;
+
   if (A_GET_TYPE(action) == A_PLACE) {
+    affected[0] = (uint8_t)loc;
+    n_aff = 1;
+    old_contrib[0] = zobrist_cell(state, affected[0]);
+
     const uint8_t black = (state->current_colour == C_BLACK);
     switch (A_GET_DATA0(action)) {
     case STONE_FLAT: {
@@ -293,6 +305,15 @@ void action_take(tak_state_p state, const action_t action) {
     for (uint8_t _gaps = gaps; _gaps; steps++)
       _gaps &= _gaps - 1;
 
+    // Record the affected cells (source + every drop square) and their
+    // current contributions
+    affected[0] = (uint8_t)loc;
+    for (int8_t k = 1; k <= steps; k++)
+      affected[k] = (uint8_t)(loc + k * delta);
+    n_aff = steps + 1;
+    for (int i = 0; i < n_aff; i++)
+      old_contrib[i] = zobrist_cell(state, affected[i]);
+
     // Move top stone type to destination
     state->celldat[loc + steps * delta] &= CLR_STONE; // necessary for crushing
     state->celldat[loc + steps * delta] |= STONE_AT(state, loc);
@@ -327,6 +348,14 @@ void action_take(tak_state_p state, const action_t action) {
   }
   // Next ply
   inline_next_ply(state);
+
+  // Fold the move into the incremental hash: remove each affected cell's old
+  // contribution, add its new one, and flip the ply-parity term.
+  for (int i = 0; i < n_aff; i++) {
+    state->hash ^= old_contrib[i];
+    state->hash ^= zobrist_cell(state, affected[i]);
+  }
+  state->hash ^= PLY_PARITY_MAGIC;
 }
 
 void action_undo(tak_state_p state, const action_t action) {
@@ -334,7 +363,18 @@ void action_undo(tak_state_p state, const action_t action) {
   inline_prev_ply(state);
 
   const int8_t loc = A_GET_LOC(action);
+
+  // Incremental hash: record the affected cells and their current
+  // (pre-undo) contributions, reverse the move, then fold in the change.
+  uint8_t affected[7];
+  uint64_t old_contrib[7];
+  int n_aff;
+
   if (A_GET_TYPE(action) == A_PLACE) {
+    affected[0] = (uint8_t)loc;
+    n_aff = 1;
+    old_contrib[0] = zobrist_cell(state, affected[0]);
+
     const uint8_t black = (state->current_colour == C_BLACK);
     state->celldat[loc] = 0;
     state->colours[loc] = 0;
@@ -358,6 +398,18 @@ void action_undo(tak_state_p state, const action_t action) {
                   dir = A_GET_DATA1(action) >> 4;
     const int8_t delta = move_deltas[dir];
 
+    // Record the affected cells (source + every drop square) and their
+    // current contributions
+    int8_t n_steps = 1;
+    for (uint8_t _gaps = gaps; _gaps; n_steps++)
+      _gaps &= _gaps - 1;
+    affected[0] = (uint8_t)loc;
+    for (int8_t k = 1; k <= n_steps; k++)
+      affected[k] = (uint8_t)(loc + k * delta);
+    n_aff = n_steps + 1;
+    for (int i = 0; i < n_aff; i++)
+      old_contrib[i] = zobrist_cell(state, affected[i]);
+
     int8_t steps = 1;
     uint8_t gap_bit = 1, total = 1;
     for (int8_t d = 1; d < num; d++, total++, gap_bit <<= 1) {
@@ -389,6 +441,14 @@ void action_undo(tak_state_p state, const action_t action) {
           STONE_FLAT; // should be optimised out
     }
   }
+
+  // Fold the undo into the incremental hash: remove each affected cell's
+  // current contribution, add its restored one, and flip the ply-parity term.
+  for (int i = 0; i < n_aff; i++) {
+    state->hash ^= old_contrib[i];
+    state->hash ^= zobrist_cell(state, affected[i]);
+  }
+  state->hash ^= PLY_PARITY_MAGIC;
 }
 
 void action_to_ptn(const action_t action, char *out_ptn) {