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).
Unit tests for engine code?
Moderator: Ras
-
- Posts: 28354
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
-
- Posts: 1062
- Joined: Tue Apr 28, 2020 10:03 pm
- Full name: Daniel Infuehr
Re: Unit tests for engine code?
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..
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
Daniel Inführ - Software Developer
-
- Posts: 469
- Joined: Fri Dec 16, 2016 11:04 am
- Location: France
- Full name: Richard Delorme
Re: Unit tests for engine code?
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
-
- Posts: 1062
- Joined: Tue Apr 28, 2020 10:03 pm
- Full name: Daniel Infuehr
Re: Unit tests for engine code?
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
Daniel Inführ - Software Developer
-
- Posts: 28354
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Unit tests for engine code?
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.
-
- Posts: 3239
- Joined: Wed Mar 10, 2010 10:18 pm
- Location: Hamburg, Germany
- Full name: Srdja Matovic
Re: Unit tests for engine code?
Solving transpositions in MCTS-UCT via Directed Acyclic Graph (DAG)/MCGS?
https://talkchess.com/forum3/viewtopic. ... 36#p890036
https://talkchess.com/forum3/viewtopic. ... 14#p929319
https://talkchess.com/forum3/viewtopic. ... 52#p898652
--
Srdja
https://talkchess.com/forum3/viewtopic. ... 36#p890036
https://talkchess.com/forum3/viewtopic. ... 14#p929319
https://talkchess.com/forum3/viewtopic. ... 52#p898652
--
Srdja
-
- Posts: 1062
- Joined: Tue Apr 28, 2020 10:03 pm
- Full name: Daniel Infuehr
Re: Unit tests for engine code?
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.
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
Daniel Inführ - Software Developer
-
- Posts: 253
- Joined: Mon Aug 26, 2019 4:34 pm
- Location: Clearwater, Florida USA
- Full name: JoAnn Peeler
Re: Unit tests for engine code?
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!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?