使用minimax可以使用多少个线程来进行井字游戏？
我们以5×5井字游戏为例。 让我们说这是我的AI。 然后，
- 我做了25次动作（当然，基本上是每个单元格，如果这是一个合法的举动），
- 为每个移动创建一个线程（总共25个线程（最多）），
- 在每次移动时调用minimax函数，
- 然后，当所有结果都来自每个线程时，
- 比较得分并选择最佳得分的移动。
这是我的问题：
-
使用25个线程是否有效？ 使用25个线程意味着什么？
-
它快25倍（很可能不是）？ 它取决于什么？ 当然，在计算机上，但我怎么知道根据计算机资源可以使用多少线程？
- 如果我使用太multithreading会发生什么（我猜不是……）？
我的想法好吗 ？ 谢谢。
对于典型的计算绑定应用程序，一个好的经验法则是使用与硬件核心（或超线程）一样多的线程。 使用比核心更多的线程不会使您的应用程序更快。 相反，它将导致您的应用程序使用比必要更多的内存。 每个线程通常具有0.5到1Mbyte的堆栈……具体取决于您的硬件和Java版本。 如果您创建了太multithreading，额外的内存使用将导致显着的性能损失; 即更multithreading=>更慢的程序！
另一件需要考虑的事情是，在典型的JVM上创建Java线程的成本很高。 因此，除非一个线程做了足够的工作（在其生命周期中），否则您可能会花费更多时间来创建线程，而不是通过在计算中使用多个核心来获得线程。
最后，您可能会发现工作不会均匀地分布在所有线程上，具体取决于您的minmax算法……以及游戏状态。
如果我试图实现这一点，我首先将它实现为单线程应用程序，然后：
- 对它进行基准测试以确定在串行运行时计算更多时间所需的时间，
- 描述它摆脱任何瓶颈
- 重新评估，以确定它是否足够快。
当且仅当它需要更快时，我会检查代码并（如果需要）添加一些监视以查看如何将计算分解为足够大的块以并行执行。
最后，我将使用这些结果来设计和实现multithreading版本。
我还会看一些替代方案……比如使用Java 7 fork / join而不是线程。
要回答您的直接问题：
使用25个线程是否有效？
可能不是。 只有拥有那么多内核才会有效（不太可能！）。 即使这样，如果你通过并行运行获得更multithreading而不是由于与线程相关的开销而损失，那么你只能通过使用大量线程获得良好的加速。 （换句话说，它取决于你使用这些线程的效率。）
使用25个线程意味着什么？
我假设你的意思是你已经创建并启动了25个Threads，无论是显式还是使用一些现有的线程池实现。
但最重要的是，如果你有（比方说）4个核心，那么这25个线程中最多只有4个可以同时执行。 其他线程将等待……
它快25倍（很可能不是）？ 它取决于什么？ 当然，在计算机上，但我怎么知道根据计算机资源可以使用多少线程？
限制性能的主要因素是核心数量。 往上看。
如果我使用太multithreading会发生什么（我猜不是……）？
线程太多意味着您使用更多内存，这会使您的应用程序因内存带宽竞争，物理内存页面竞争，额外垃圾回收而运行速度变慢。 这些因素依赖于应用和平台，难以量化; 即预测或衡量。
根据应用程序的性质（即精确地实现算法的方式），过多的线程可能导致额外的锁争用和线程上下文切换。 这也会使你的应用程序变慢。
如果没有看到您的实际代码，就无法预测会发生什么。 但是核心的数量为您提供了可能加速的理论上限。 如果你有4个内核，那么multithreading的速度不会超过4倍。
因此，给出的线程答案是可以的，但在我看来，他们忽略了minimax搜索的alpha-beta修剪function。
如果从当前位置为每个“下一步移动”启动一个线程，那么让这些线程相互通信是正确的，并且很难写。 但是，如果他们不能互相交谈，那么你就不会得到来自alpha-beta修剪的深度提升，直到进一步下降。
这将违背结果的效率。
对于改善计算时间的一般情况，最佳情况往往是每个核心1个线程，如果它们都是相似的时间（例如矩阵乘法），或者具有“一组”任务，则可以将任务简单地分配给线程，每当完成当前任务时，每个线程抓住下一个未启动的线程。 （这有一些锁定任务，但如果它们与分辨率成本相比较小则非常有效）。
因此，对于4核系统和~25个自然任务，您可以希望在3.5-4x范围内加速。 （你会做4个并行~5次，然后完成混乱）。 但是，在极小极大情况下，你已经失去了alpha-beta修剪方面，据我所知，估计会将“有效宽度”从N减少到大约sqrt（N）。 对于~25的情况，这意味着有效的分支因子为5.这意味着使用4个核心并且跳过第一级的修剪可能实际上伤害了你。
那么，离开我们的地方呢？
- 放弃去multithreading。 要么，
- 基于可用内核的线程。 速度提高4倍，同时速度也高达sqrt（25）= 5倍。 要么，
- 去multithreading，但在你的线程中传播beta。 这需要一些锁定代码，但希望不会太昂贵。 你将降低alpha-beta修剪的效率，因为你将搜索你不会在严格的左 – 右通道中搜索的子树，但是任何恰好搜索冗余区域的线程仍然比一个无所事事的核心。 因此，多余的搜索应该通过额外的有用工作来抵消。 （但是这对于编写一个简单的任务< - >线程映射来说要困难得多）。 这里真正的问题可能是需要/找到真正同时修复alpha-beta修剪和multithreading的人。 它不会让我感觉像代码我会相信很多人正确地写。 （例如，我在我的时间里编写了许多multithreading程序和几个minimax搜索，但我不知道如果你需要在线程之间传播beta或alpha或两者以便从顶级节点进行搜索） 。
正如我所有的朋友所说，使用尽可能多的线程，因为你的机器有容量。
但是通过添加它们你也应该改进算法。
例如，在5×5 tic tac toe中，两者都将得到12或13个动作。 因此，nCr（组合方程式）基数为25C12 = 5,200,300。 所以现在你已经减少线程的数量，现在进行最佳选择，你有最好的方法找到最佳解决方案只有12（赢得位置）和12失去最差的条件所有其他都是绘制条件。 所以现在你可以做的就是从线程中检查这12个条件，并在计算中留出额外的组合，你需要创建12个！ * 12没有与25相比非常低的线程！
因此，您的线程数量将减少，您可以进一步考虑减少线程数量。
当您的动作越来越多时，您可以使用alpha-beta修剪，以便您也可以改进算法。
如果您正在使用线程，那么为了防止内存浪费，只需将它们用于mini-max的第一次调用，然后组合线程的结果以获得输出。 如果你使用25个线程或者某个数字这么大，这是一个浪费，因为可用内核的数量少于那么多，所以你可以做的是在不同的状态下一次只安排相当于可用内核的线程，并将所有结果组合在一起结束。
这是伪代码： –
int miniMax(State,Player,depth) { // normal minimax code } State ParaMiniMax(State,Player) { int totalThreads = Runtime.getRuntime().availableProcessors()); NextStates = getNextStates(State); while(NextStates.size()>0) { k = totalThreads; while(k>0 && NextStates.size>0) { //Schedule thread with nextState. with run calling miniMax with other player //Store (score,state) in Result List k--; NextStates.removeTop(); } wait(); // waits for threads to complete } if(player==max) { return(maxScore(Result).State); } else return(minScore(Result).State); } 您应该只使用与机器具有的核心数相等的线程数。 将任务调度到这些线程上是另一回事。
考虑问题的对称性。 实际上只有非常有限数量的“独特”初始移动 – 其余的是相同的但是用于reflection或旋转（因此具有相同的战略价值）。 5×5板的独特举措是：
xxx.. .xx.. ..x.. ..... .....
或者只是6个初始动作。 Bam – 你只是将复杂性降低了4倍而没有线程。
正如其他人所说，除了单个线程花费时间“等待” – 输入，内存访问和其他结果之外，线程数量超过内核通常无助于加速。 可能是六个线程是一个好的起点。
只是为了让你相信对称性，我用相同的数字标记相同的位置 – 如果你同意的话
12321 24542 35653 24542 12321
当您旋转90度的任意倍数或反映对角线或左右，上下时，这是相同的。
PS我意识到这并没有真正回答你提出的问题，但我相信它直接解决了你的基本问题 – “我如何有效地解决5×5 tic-tac-toe”。 因此，如果你选择不同的答案，我不会感到沮丧，但我希望你能把我的建议铭记于心。