How many threads are okay to use for tic-tac-toe using minimax?

Question

Let's take a 5x5 tic-tac-toe as an example. Let's say it's my AI's turn. Then,

• I make 25 moves (at each cell basically, of course, if it's a legal move),
• create a thread for each move (25 threads total (at most)),
• call a minimax function on each made move,
• then when all results come from each thread,
• compare the scores and choose the move with the best score.

Here are my questions:

• Is it efficient to use 25 threads? What does using 25 threads mean?

• Is it 25 times faster (most likely not)? What it depends on? On the computer, of course, but how can I know how many threads are okay to use based on the computer's resources?

• What happens if I use too many threads (nothing I guess...)?

Is my idea good? Thanks.

Answer 1

For a typical compute-bound application, a good rule of thumb is to use as many threads as you have hardware cores (or hyperthreads). Using more threads than cores won't make your application go faster. Instead, it will cause your application to use more memory than is necessary. Each thread typically has a 0.5 to 1Mbyte stack ... depending on your hardware and the Java version. If you create too many threads, the extra memory usage will result in a significant performance hit; i.e. more threads => slower program!

Another thing to consider is that Java threads are expensive to create on a typical JVM. So unless a thread does enough work (in its lifetime) there is a risk that you spend more time creating threads than you gain by using multiple cores in the computation.

Finally, you may find that the work does not spread evenly over all threads, depending on your minmax algorithm ... and the game state.

---

If I was trying to implement this, I'd start by implementing it as a single threaded application, and then:

• benchmark it to figure out how long it takes to calculate a more when run serially,
• profile it to get rid of any bottlenecks
• re-benchmark to see if it is fast enough already.

If and only if it needs to go faster, I would then examine the code and (if necessary) add some monitoring to see how to break the computation down into large enough chunks to be executed in parallel.

Finally, I'd use those results to design and implement a multi-threaded version.

I'd also look at alternatives ... like using Java 7 fork/join instead of threads.

---

To answer your direct questions:

Is it efficient to use 25 threads?

Probably not. It would only be efficient if you had that many cores (unlikely!). And even then you are only going to get a good speedup from using lots of threads if you gain more by running things in parallel than you lose due to thread-related overheads. (In other words, it depends how effectively you use those threads.)

What does using 25 threads mean?

I assume that you mean that you have created and started 25 Threads, either explicitly or using some existing thread pool implementation.

But the bottom line is that if you have (say) 4 cores, then at most 4 of those 25 threads can be executing at one time. The other threads will be waiting ...

Is it 25 times faster (most likely not)? What it depends on? On the computer, of course, but how can I know how many threads are okay to use based on the computer's resources?

The primary factor that limits performance is the number of cores. See above.

What happens if I use too many threads (nothing I guess...)?

Too many threads means you use more memory and that makes your application run slower because of memory bandwidth competition, competition for physical memory pages, extra garbage collection. These factors are application and platform dependent, and hard to quantify; i.e. predict or measure.

Depending on the nature of your application (i.e. precisely how you implement the algorithms) too many threads could result in extra lock contention and thread context switching. That will also make your application slower.

It is a impossible to predict what would happen without seeing your actual code. But the number of cores gives you a theoretical upper bound on how much speedup is possible. If you have 4 cores, then you cannot get more than a 4-fold speedup with multi-threading.