CODEWITHSUNDEEP
multithreadingalpha-beta-pruningnegamax
user1880342
user1880342

Reputation: 128

Multithreaded evaluation using Negamax + alpha-beta pruning with transposition tables

I just implemented a nice-working evaluation function for checkers. Current implementation uses threads and separate transposition tables for each.

I spawn a thread for every move that is available in the root node (initial board position) and then analyze it using negamax with alpha-beta pruning. I always do it for the CPU player to find a best move. I don't analyze moves available to the user.

Now I have two considerations:

  1. Can I safely share a single transposition table between all these threads (threads will be synchronized of course)?

  2. Every time I start a new analysis, should I clear the table(s) or they are safe to use?

Any thoughts?

Upvotes: 0

Views: 425

Answers (1)

Ariel
Ariel

Reputation: 1

1: You SHOULD share a single transposition table across all threads, since the main idea is that the same position is reached via different paths, not only by child nodes of a single thread.

2: It depends. You may not need to clear the whole table at each analysis, but you will have to determine a limit for it. All possible positions are just too much to store in memory or disk.

Another consideration would be to clear the positions that can no longer been achieved in the current game (i.e. positions with more pieces).

Even if you clear the whole table when starting a new analysis, depending on your search depth, you might still reach the limit that you've previously defined.

So the transposition table is nothing more than cache, and you must define and apply an eviction policy. It might be a combination of different factors and you should also check the common cache eviction policies like "Least recently used (LRU)" https://en.wikipedia.org/wiki/Cache_replacement_policies#Least_recently_used_(LRU)

Upvotes: 0

Related Questions