UCT / MCTS & transposition table

Anything about the game of Ataxx
Post Reply
flok
Posts: 18
Joined: Sat Jan 02, 2016 9:04 pm
Contact:

UCT / MCTS & transposition table

Post by flok » Tue Apr 19, 2022 8:15 pm

Hi,

Has anyone ever tried adding a transposition table to an UCT/MCTS implementation?

I tried without much success. It works, but it plays worse than the non-tt version.

What I do is: for each position I have a node. This node stores pointers to children (of course as it is a tree) and to all the parents (can be multiple due to transpositions).
Now the score function is:

Code: Select all

double UCTj = double(score) / visit_count + sqrt(2) * sqrt(log(parent_visit_count) / visit_count);
Here I use the sum of all the visit-counts of all parents. Is that how it should work? Or am I walking an uncultivated area?
www.ataxx.org / www.vanheusden.com

Rémi Coulom
Posts: 158
Joined: Tue Feb 12, 2008 8:31 pm
Contact:

Re: UCT / MCTS & transposition table

Post by Rémi Coulom » Fri Apr 22, 2022 8:00 pm

Hi,

Using a transposition table is a good idea, and is rather common. It should make the program stronger.

You should not have to keep pointers to parents. If I understand what you do correctly, you may get very different "parent_visit_count" for every child of a node. This does not seem good.

Also note that UCT is not very efficient formula. Using a policy with the AlphaGo formula will be much better.

Rémi

flok
Posts: 18
Joined: Sat Jan 02, 2016 9:04 pm
Contact:

Re: UCT / MCTS & transposition table

Post by flok » Fri Apr 22, 2022 8:20 pm

Rémi Coulom wrote:
Fri Apr 22, 2022 8:00 pm
Using a transposition table is a good idea, and is rather common. It should make the program stronger.

You should not have to keep pointers to parents. If I understand what you do correctly, you may get very different "parent_visit_count" for every child of a node. This does not seem good.
Ok. But which parent should I use?
Also note that UCT is not very efficient formula. Using a policy with the AlphaGo formula will be much better.
ok!
www.ataxx.org / www.vanheusden.com

Rémi Coulom
Posts: 158
Joined: Tue Feb 12, 2008 8:31 pm
Contact:

Re: UCT / MCTS & transposition table

Post by Rémi Coulom » Fri Apr 22, 2022 9:15 pm

flok wrote:
Fri Apr 22, 2022 8:20 pm
Ok. But which parent should I use?
The parent from which you are selecting a move.

ghostway
Posts: 1
Joined: Fri Jun 03, 2022 11:13 am

Re: UCT / MCTS & transposition table

Post by ghostway » Fri Jun 03, 2022 11:16 am

flok wrote:
Tue Apr 19, 2022 8:15 pm
Hi,

Has anyone ever tried adding a transposition table to an UCT/MCTS implementation?

I tried without much success. It works, but it plays worse than the non-tt version.

What I do is: for each position I have a node. This node stores pointers to children (of course as it is a tree) and to all the parents (can be multiple due to transpositions).
Now the score function is:

Code: Select all

double UCTj = double(score) / visit_count + sqrt(2) * sqrt(log(parent_visit_count) / visit_count);
Here I use the sum of all the visit-counts of all parents. Is that how it should work? Or am I walking an uncultivated area?
Hello! Transposition tables in uct search have quite a few possible meanings. There's an nn cache, which saves the nn outputs for a particular position, and mcgs (ofc there are more just those are the ways I'm familiar with). See the mcgs paper https://www.google.com/url?sa=t&source= ... tww1WL9RM9

Post Reply