Nice speedup for Berserk with a simple eval hash

Discussion of anything and everything relating to chess playing software and machines.

Moderators: hgm, Rebel, chrisw

Dann Corbit
Posts: 12615
Joined: Wed Mar 08, 2006 8:57 pm
Location: Redmond, WA USA

Nice speedup for Berserk with a simple eval hash

Post by Dann Corbit »

3040242 nodes 150947 nps // no eval hash
3040242 nodes 208980 nps // eval hash added
Sorry about the formatting, but you cannot format as code and also make your changes bold.
At least, I do not know how to do it.
// Berserk is a UCI compliant chess engine written in C
// Copyright (C) 2024 Jay Honnold

// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.

// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with this program. If not, see <https://www.gnu.org/licenses/>.

#include "eval.h"

#include <stdio.h>

#include "attacks.h"
#include "bits.h"
#include "board.h"
#include "move.h"
#include "nn/accumulator.h"
#include "nn/evaluate.h"
#include "uci.h"
#include "util.h"

const int PHASE_VALUES[6] = {0, 3, 3, 5, 10, 0};
const int MAX_PHASE = 64;

void SetContempt(int* dest, int stm) {
int contempt = CONTEMPT;

dest[stm] = contempt;
dest[stm ^ 1] = -contempt;
}

#define USE_EVAL_HASH 1

#ifdef USE_EVAL_HASH
typedef struct eval_hash {
int value;
unsigned long long key;
} eval_hash;


static const size_t EVAL_HASH_MASK = 0x3FFFFFF;
static eval_hash eht[0x3FFFFFF + 1];
#endif
// Main evalution method
Score Evaluate(Board* board, ThreadData* thread) {
#ifdef USE_EVAL_HASH
// added evaluation hash table
uint64_t hash = board->zobrist;
eval_hash *e = &eht[hash & EVAL_HASH_MASK];
if (e->key == hash)
{
return e->value;
}
#endif

if (IsMaterialDraw(board))
{
#ifdef USE_EVAL_HASH
e->key = hash;
e->value = 0;
#endif

return 0;
}
Accumulator* acc = board->accumulators;
for (int c = WHITE; c <= BLACK; c++) {
if (!acc->correct[c]) {
if (CanEfficientlyUpdate(acc, c))
ApplyLazyUpdates(acc, board, c);
else
RefreshAccumulator(acc, board, c);
}
}

int score = board->stm == WHITE ? Propagate(acc, WHITE) : Propagate(acc, BLACK);

// scaled based on phase [1, 1.5]
score = (128 + board->phase) * score / 128;
score += board->phase * thread->contempt[board->stm] / 64;
int v = Min(EVAL_UNKNOWN - 1, Max(-EVAL_UNKNOWN + 1, score));
#ifdef USE_EVAL_HASH
e->key = hash;
e->value = v;
#endif

return v;
}
// removed method evaluatetrace for this post, since no changes were made to it.
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.
Dann Corbit
Posts: 12615
Joined: Wed Mar 08, 2006 8:57 pm
Location: Redmond, WA USA

Re: Nice speedup for Berserk with a simple eval hash

Post by Dann Corbit »

I modified the makefile to build on Windows using gcc by default instead of clang (clang actually makes a better binary, but I can rarely get it to work on windows).
The binary in the source folder is avx2 built on threadripper.
build with:
make pgo ARCH=native

The eh in the name stands for 'eval hash'.

My modifications are here:
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.
Dann Corbit
Posts: 12615
Joined: Wed Mar 08, 2006 8:57 pm
Location: Redmond, WA USA

Re: Nice speedup for Berserk with a simple eval hash

Post by Dann Corbit »

I could not contact Jay Honnold, but he might be interested.
He has instructions to use discord to contact him, but I don't use discord.
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.
Dann Corbit
Posts: 12615
Joined: Wed Mar 08, 2006 8:57 pm
Location: Redmond, WA USA

Re: Nice speedup for Berserk with a simple eval hash

Post by Dann Corbit »

Much ado about nothing.
I had to static link to use the binary stand-alone on windows.
After that, my speed improvement went up in smoke.
There may also be interference from a tournament I have running.
It uses 30 of 32 cores, and maybe the bench uses more than 2 threads
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.
User avatar
Steve Maughan
Posts: 1231
Joined: Wed Mar 08, 2006 8:28 pm
Location: Florida, USA

Re: Nice speedup for Berserk with a simple eval hash

Post by Steve Maughan »

Hi Dann,

Isn't an evaluation hash for a NNUE engine moot? For every position you need to update the neural network, and in doing so you evaluate the position. What am I missing?

— Steve
http://www.chessprogramming.net - Maverick Chess Engine
Dann Corbit
Posts: 12615
Joined: Wed Mar 08, 2006 8:57 pm
Location: Redmond, WA USA

Re: Nice speedup for Berserk with a simple eval hash

Post by Dann Corbit »

Steve Maughan wrote: Thu May 23, 2024 12:34 pm Hi Dann,

Isn't an evaluation hash for a NNUE engine moot? For every position you need to update the neural network, and in doing so you evaluate the position. What am I missing?

— Steve
If eval() is called for a position already calculated, the value is in the eval hash table. Since evaluation of a neural network is expensive I would think you would save on calculation effort. The neural network does not care if it got the number by calculation or from the hash does it?
I have seen that LC0 uses an evaluation hash, which is what made me think it would work.
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.
mar
Posts: 2579
Joined: Fri Nov 26, 2010 2:00 pm
Location: Czech Republic
Full name: Martin Sedlak

Re: Nice speedup for Berserk with a simple eval hash

Post by mar »

looking at Berserk's transposition.h:

Code: Select all

typedef struct __attribute__((packed)) {
  uint16_t hash;
  uint8_t depth;
  uint8_t agePvBound;
  uint32_t evalAndMove;
  int16_t score;
} TTEntry;
shows that it stores eval in the TT, so the entire TT is in fact "eval cache"

also your eval cache code might break due to data races in smp:

Code: Select all

eval_hash *e = &eht[hash & EVAL_HASH_MASK];
if (e->key == hash)
{ // <<<< potential data race here, another thread may modify e->value before we return
return e->value;
}
User avatar
Steve Maughan
Posts: 1231
Joined: Wed Mar 08, 2006 8:28 pm
Location: Florida, USA

Re: Nice speedup for Berserk with a simple eval hash

Post by Steve Maughan »

Dann Corbit wrote: Thu May 23, 2024 5:23 pm If eval() is called for a position already calculated, the value is in the eval hash table. Since evaluation of a neural network is expensive I would think you would save on calculation effort. The neural network does not care if it got the number by calculation or from the hash does it?
I have seen that LC0 uses an evaluation hash, which is what made me think it would work.
But with NNUE you *must* update the NN after every move. I guess you could only update the first layer and pull the evaluation from the hash.

— Steve
http://www.chessprogramming.net - Maverick Chess Engine
JacquesRW
Posts: 73
Joined: Sat Jul 30, 2022 12:12 pm
Full name: Jamie Whiting

Re: Nice speedup for Berserk with a simple eval hash

Post by JacquesRW »

Steve Maughan wrote: Thu May 23, 2024 7:23 pm
Dann Corbit wrote: Thu May 23, 2024 5:23 pm If eval() is called for a position already calculated, the value is in the eval hash table. Since evaluation of a neural network is expensive I would think you would save on calculation effort. The neural network does not care if it got the number by calculation or from the hash does it?
I have seen that LC0 uses an evaluation hash, which is what made me think it would work.
But with NNUE you *must* update the NN after every move. I guess you could only update the first layer and pull the evaluation from the hash.

— Steve
You're saving the rest of the inference by using a hash, i.e. going from the first hidden layer, which is updated incrementally, to the output.
As already pointed out, Beserk does it already: https://github.com/jhonnold/berserk/blo ... rch.c#L468

EDIT: Also there's no requirement to update the accumulators after every move, you can do the updates lazily, which Beserk also does IIRC.
Dann Corbit
Posts: 12615
Joined: Wed Mar 08, 2006 8:57 pm
Location: Redmond, WA USA

Re: Nice speedup for Berserk with a simple eval hash

Post by Dann Corbit »

mar wrote: Thu May 23, 2024 6:46 pm looking at Berserk's transposition.h:

Code: Select all

typedef struct __attribute__((packed)) {
  uint16_t hash;
  uint8_t depth;
  uint8_t agePvBound;
  uint32_t evalAndMove;
  int16_t score;
} TTEntry;
shows that it stores eval in the TT, so the entire TT is in fact "eval cache"

also your eval cache code might break due to data races in smp:

Code: Select all

eval_hash *e = &eht[hash & EVAL_HASH_MASK];
if (e->key == hash)
{ // <<<< potential data race here, another thread may modify e->value before we return
return e->value;
}
Hyatt and Mann did a study on lockless hash tables and concluded that collisions don't matter.
"A lock-less transposition table implementation for parallel search chess engines"
However, with modern hardware and hundreds of threads, it may no longer be true.
Especially with a small hash table like the one in this post (67 million slots).
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.