使用minimax，可以在井字游戏中使用多少个线程？ [英] How many threads are okay to use for tic-tac-toe using minimax?
问题描述
让我们以5x5井字游戏为例。
假设这是我的AI。
然后
- 我进行25次移动（基本上，在每个单元格中，如果这是合法的
移动， ）， - 为每个动作创建一个线程（总共25个线程（最多）），
- 在每个动作中调用一个minimax函数，
- 然后，当所有结果都来自每个线程时，
- 比较得分并选择得分最高的举动。
这是我的问题：
-
使用效率高吗？ 25个线程？使用25个线程是什么意思？
-
是否快25倍（很可能不是）？它取决于什么？当然，在计算机上，但是我如何根据计算机的资源知道多少个线程可以使用？
- 如果我使用太多线程（我猜没有...），会发生什么？
我的想法好吗？谢谢。
对于典型的 compute-bound 应用程序，应使用一条好的经验法则具有硬件核心（或超线程）的线程数。使用比核心多的线程不会使您的应用程序运行得更快。而是，这将导致您的应用程序使用不必要的内存。每个线程通常具有0.5到1 MB的堆栈...取决于您的硬件和Java版本。如果创建的线程太多，那么额外的内存使用将导致性能严重下降；也就是说，更多的线程=>较慢的程序！
要考虑的另一件事是，在典型的JVM上创建Java线程非常昂贵。因此，除非线程在其生命周期内完成了足够的工作，否则存在创建线程花费的时间多于在计算中使用多个内核所获得的时间的风险。
最后，您可能会发现工作并没有平均分配到所有线程上，具体取决于您的minmax算法...以及游戏状态。
如果我尝试实现此目标，那么我将从将其实现为单线程应用程序开始，然后：
- 对其进行基准测试，以计算出串行运行时计算出的更多时间所需的时间，
- 分析它以消除任何瓶颈
- 重新进行基准测试
如果且仅当它需要更快时，我才检查代码和（
最后，我将使用这些结果进行设计和计算，以了解如何将计算分解为足够大的块以并行执行。
实施ta是多线程版本。我还将研究替代方案，例如使用Java 7 fork / join而不是线程。
回答您的直接问题：
使用25个线程？
可能不是。只有拥有那么多核心（不太可能！），它才会高效。即使这样，如果您通过并行运行事物获得的收益要多于由于线程相关的开销而导致的损失，那么您将只能通过使用大量线程来获得良好的加速。 （换句话说，这取决于您使用这些线程的效率。）
使用25个线程意味着什么？
我假设 you 意味着您已经创建或启动了25个线程，无论是显式的还是使用某些现有线程池的实现。 p>
但最重要的是，如果您拥有（例如）4个内核，那么这25个线程中最多 个可以一次执行。其他线程将在等待...
是否快25倍（很可能不是）？它取决于什么？当然，在计算机上，但是我怎么知道根据计算机的资源可以使用多少个线程呢？
限制性能的因素是核心数量。
如果我使用太多线程（我猜没有...）会发生什么？
线程太多意味着您使用了更多的内存，并且由于内存带宽竞争，争用物理内存页面，额外的垃圾回收，使您的应用程序运行速度变慢。这些因素取决于应用程序和平台，并且难以量化；
根据应用程序的性质（即精确地实现算法的方式），过多的线程可能会导致额外的锁争用和线程上下文切换。这也会使您的应用程序变慢。
如果不查看实际代码就无法预测会发生什么。但是内核数量为您提供了理论上的加速上限。如果您有4个核心，那么使用多线程的速度将不会超过4倍。
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.
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.
这篇关于使用minimax，可以在井字游戏中使用多少个线程？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
