Unit tests for engine code?

Discussion of chess software programming and technical issues.

Moderator: Ras

User avatar
hgm
Posts: 28354
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: Unit tests for engine code?

Post by hgm »

Indeed, no code for storing was included, as no format was defined for that.

The point is that the scores for the d-1 leaves can be completely independent from that at d. In chess there is a large correlation between the evaluation of a node and its children. But in general there is no need for that. This is one of the parameters that define the tree that you failed to specify.

To generate a benign tree you would generate one at maximum depth, and the do 'iterative shallowing' to design the same tree with the same PV for depth d-1, d-2, etc. For generating a poisoned tree you would pick a completely different PV for the lower depths (but the same for all of those).
dangi12012
Posts: 1062
Joined: Tue Apr 28, 2020 10:03 pm
Full name: Daniel Infuehr

Re: Unit tests for engine code?

Post by dangi12012 »

Sounds easy enough now.
I will post some code here once I solve this.

Indeed even in chess the eval() of a node can only be correct if it is a known mating line.

And eval() of nodes will almost be exactly the ones of child nodes. And this is what I am looking for. evals() looking better and better... Until at a deeper depth they get worse again.

A challenge for AlphaBeta (wrong ordering) as well as MCTS.
Domain independent comparison of search algos as well as search regression tests.
Looking forward to it.

This is also exactly how Alphazero beat SF back in the day. A deep position with a few pawn sacrifices (looking very bad) and suddenly 12 moves later white was in trouble etc..
Worlds-fastest-Bitboard-Chess-Movegenerator
Daniel Inführ - Software Developer
abulmo2
Posts: 469
Joined: Fri Dec 16, 2016 11:04 am
Location: France
Full name: Richard Delorme

Re: Unit tests for engine code?

Post by abulmo2 »

dangi12012 wrote: Sun Sep 18, 2022 7:19 pm ...
I wonder if you are not trying to reinvent the SSS* algorithm https://www.chessprogramming.org/SSS*_and_Dual*.
The original algorithm build a tree with LIVE nodes (without a known value) and SOLVED nodes (with a known backpropagated value). It was a slow and complex algorithm compared to alphabeta, but later A. Plaat proved that you can visit the same nodes and in the same order with alphabeta + a transposition table https://arxiv.org/abs/1404.1517.

How do you deal with transpositions when you build your tree? In chess the same position can be found using different paths. If you do not take care of that you can spent a lot of time searching the same position again and again.
Richard Delorme
dangi12012
Posts: 1062
Joined: Tue Apr 28, 2020 10:03 pm
Full name: Daniel Infuehr

Re: Unit tests for engine code?

Post by dangi12012 »

abulmo2 wrote: Sun Sep 18, 2022 9:41 pmHow do you deal with transpositions when you build your tree? In chess the same position can be found using different paths. If you do not take care of that you can spent a lot of time searching the same position again and again.
If not for 3fold repetition MCTS is statistical so it does not even care about evaluation a "already evaluated" position twice. In fact the main strengh would come from trivial parallelisation as well as persisting the whole tree. Results are propagated up the tree so repeating positions does not change anything in terms of outcome.

I want to compare MCTS to Alphabeta to naive MinMax the same way I did it with all the sliding piece algos. I wont consider other algos for now.
Also there are nuances to be solved for UCB1 vs Policy NN.

For a mocked tree there cannot be a Policy NN except to learn the speed of training. (policy NN would learn the domain but with mocking there isnt one to exploit)

Transpositions lookups are indirect with AB (hash and lookup into array)
Transpositions lookups are direct with MCTS (the relationship between positions is stored in the tree)

Memory impact will be quite different.
Threading of YBWC vs parallel MCTS will be interestring etc.
Worlds-fastest-Bitboard-Chess-Movegenerator
Daniel Inführ - Software Developer
User avatar
hgm
Posts: 28354
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: Unit tests for engine code?

Post by hgm »

I don't see much difference with regard to transpositions in MCTS and AB. The hash table in AB is a way to store the tree, and surely the storage scheme of an MCTS tree would involve hashing to detect transpositions.
smatovic
Posts: 3239
Joined: Wed Mar 10, 2010 10:18 pm
Location: Hamburg, Germany
Full name: Srdja Matovic

Re: Unit tests for engine code?

Post by smatovic »

dangi12012
Posts: 1062
Joined: Tue Apr 28, 2020 10:03 pm
Full name: Daniel Infuehr

Re: Unit tests for engine code?

Post by dangi12012 »

MCTS does not care that the same position already occured. Its statistical aggregation towards the root.

There is no need to do so in MCTS except for 3 fold repetition.
A node gets selected and simulated. So it will get visited thousands of times. If it's duplicated and there is a cycle the simulation results get aggregated back with the same end result either way.

If for some reason you need to solve cycles it's also trivial on expansion. There you just set the correct node* inside vector<node*> children by checking the hash against all reversible parents - on recursion you make sure to skip upward jumping children.
Worlds-fastest-Bitboard-Chess-Movegenerator
Daniel Inführ - Software Developer
JoAnnP38
Posts: 253
Joined: Mon Aug 26, 2019 4:34 pm
Location: Clearwater, Florida USA
Full name: JoAnn Peeler

Re: Unit tests for engine code?

Post by JoAnnP38 »

dangi12012 wrote: Fri Sep 16, 2022 9:31 pm I wanted to ask if someone here does tests.
Do you use a Test framework like gtest, or just write a function that is called which calls all the functions to be tested?
I just started a new engine project. The last engine I wrote was back in the 1980s and now that I'm retired, I have a lot more time to dedicate to this passion. I've learned over the years that writing unit tests using a framework like NUnit or MsTest can save you a lot of headaches -- especially if you are writing tests the same time you are writing new code. In fact, it's one of the few ways that Pair Programming has been explained to me that makes a little sense. Both developers are working closely together developing / designing code and then while one developer codes the other writes the unit tests. Periodically they switch places. I suppose it could work, but most developers I've worked with are not the best unit test developers. No more big bang integrations for me!