使用minimax可以使用多少个线程进行井字游戏？

Question

我们以5x5井字游戏为例.让我们说这是我的AI.然后,

• 我做了25次动作(当然,基本上是每个单元格,如果这是一个合法的举动),
• 为每个移动创建一个线程(总共25个线程(最多)),
• 在每次移动时调用minimax函数,
• 然后,当所有结果都来自每个线程时,
• 比较得分并选择最佳得分的移动.

这是我的问题:

• 使用25个线程是否有效？使用25个线程意味着什么？

• 它快25倍(很可能不是)？它取决于什么？当然,在计算机上,但我如何根据计算机的资源知道可以使用多少线程？

• 如果我使用太多线程会发生什么(我猜不是......)？

我的想法好吗？谢谢.

Answer 1

对于典型的计算绑定应用程序,一个好的经验法则是使用与硬件核心(或超线程)一样多的线程.使用比核心更多的线程不会使您的应用程序更快.相反,它将导致您的应用程序使用比必要更多的内存.每个线程通常具有0.5到1M字节的堆栈......具体取决于您的硬件和Java版本.如果您创建了太多线程,额外的内存使用将导致显着的性能损失; 即更多线程=>更慢的程序!

另一件需要考虑的事情是,在典型的JVM上创建Java线程的成本很高.因此,除非一个线程做了足够的工作(在其生命周期内),否则您可能会花费更多时间来创建线程,而不是通过在计算中使用多个核心来获得.

最后,您可能会发现工作不会均匀地分布在所有线程上,具体取决于您的minmax算法......以及游戏状态.

如果我试图实现这一点,我首先将它实现为单线程应用程序,然后:

• 对它进行基准测试以确定在串行运行时计算更多时间所需的时间,
• 描述它摆脱任何瓶颈
• 重新评估,以确定它是否足够快.

当且仅当它需要更快时,我会检查代码并(如果需要)添加一些监视以查看如何将计算分解为足够大的块以并行执行.

最后,我将使用这些结果来设计和实现多线程版本.

我还会看一些替代方案......比如使用Java 7 fork/join而不是线程.

要回答您的直接问题:

使用25个线程是否有效？

可能不是.只有拥有那么多内核才会有效(不太可能!).即使这样,如果你通过并行运行获得更多线程而不是因为与线程相关的开销而损失,那么你只能通过使用大量线程获得良好的加速.(换句话说,它取决于你使用这些线程的效率.)

使用25个线程意味着什么？

我假设你的意思是你已经创建并启动了25个线程,无论是显式还是使用一些现有的线程池实现.

但底线是,如果你有(说)4个核心,那么最多的25个线程的4可以在同一时间内执行.其他线程将等待......

它快25倍(很可能不是)？它取决于什么？当然,在计算机上,但我如何根据计算机的资源知道可以使用多少线程？

限制性能的主要因素是核心数量.往上看.

如果我使用太多线程会发生什么(我猜不是......)？

线程太多意味着您使用更多内存,这会使您的应用程序因内存带宽竞争,物理内存页面竞争,额外垃圾回收而运行速度变慢.这些因素依赖于应用和平台,难以量化; 即预测或衡量.

根据应用程序的性质(即精确地如何实现算法),太多线程可能导致额外的锁争用和线程上下文切换.这也会使你的应用程序变慢.

如果没有看到您的实际代码,就无法预测会发生什么.但核心数量可以为您提供可能的加速比的理论上限.如果你有4个核心,那么使用多线程你不可能获得超过4倍的加速.