草庐IT

python - Minimax 解释 "for dummies"

coder 2023-08-17 原文

我对算法很陌生，我试图理解 minimax，我阅读了很多文章，但我仍然不知道如何将它实现到 python 中的井字游戏中。 你能试着用一些伪代码或一些 python 代码尽可能简单地向我解释它吗？

我只需要了解它是如何工作的。我读了很多关于它的资料，我了解基本知识，但我仍然不明白它是如何还手的。

如果可以，请不要给我链接教程和示例，例如 (http://en.literateprograms.org/Tic_Tac_Toe_(Python)) ，我知道它们很好，但我只需要一个白痴解释。

感谢您的宝贵时间:)

最佳答案

“minimax”的想法是，在两人游戏中，一个玩家试图最大化某种形式的分数，而另一个玩家试图最小化它。例如，在 Tic-Tac-Toe 中，X 的获胜可能记为 +1，O 的获胜记为 -1。 X 将是最大玩家，试图最大化最终得分，而 O 将是最小玩家，试图最小化最终得分。

X 被称为最大玩家，因为当它是 X 的着法时，X 需要选择一个使该着法后的结果最大化的着法。当 O 玩家时，O 需要选择一个移动，使该移动后的结果最小化。这些规则递归应用，例如如果只有三个棋盘位置可供下，X 的最佳下法是迫使 O 选择值(value)尽可能高的最小值着法。

换句话说，棋盘位置 B 的博弈论极小极大值 V 定义为

 V(B) = 1   if X has won in this position
 V(B) = -1  if O has won in this position
 V(B) = 0   if neither player has won and no more moves are possible (draw)

否则

 V(B) = max(V(B1), ..., V(Bn)) where board positions B1..Bn are
        the positions available for X, and it is X's move
 V(B) = min(V(B1), ..., V(Bn)) where board positions B1..Bn are
        the positions available for O, and it is O's move

X 的最优策略总是从 B 移动到 Bi，使得 V(Bi) 最大，即对应于博弈论值 V(B)，对于 O，类似地，选择最小的后继位置。

然而，这在国际象棋等游戏中通常无法计算，因为为了计算博弈论值，需要枚举整个博弈树直到最终位置，而这棵树通常非常大。因此，一种标准方法是创造一个“评估函数”，将棋盘位置映射到希望与博弈论值相关的分数。例如。在国际象棋程序中，评估函数往往会为 Material 优势、开放列等给出正分数。极小极大算法会最小化评估函数分数，而不是棋盘位置的实际(不可计算的)博弈论值。

minimax 的一个重要的标准优化是“alpha-beta 剪枝”。它给出的结果与极小极大搜索相同，但速度更快。 Minimax 也可以根据“negamax”进行转换，其中得分的符号在每个搜索级别都反转。它只是实现 minimax 的另一种方法，但以统一的方式处理玩家。其他博弈树搜索方法包括迭代加深、证明数搜索等。

关于python - Minimax 解释 "for dummies"，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10626766/

ampMinimaxsection着法最小化pythonalgorithm

有关python - Minimax 解释 "for dummies"的更多相关文章

  1. python - 如何使用 Ruby 或 Python 创建一系列高音调和低音调的蜂鸣声？ - 2

    关闭。这个问题是opinion-based.它目前不接受答案。想要改进这个问题？更新问题，以便editingthispost可以用事实和引用来回答它.关闭4年前。Improvethisquestion我想在固定时间创建一系列低音和高音调的哔哔声。例如:在150毫秒时发出高音调的蜂鸣声在151毫秒时发出低音调的蜂鸣声200毫秒时发出低音调的蜂鸣声250毫秒的高音调蜂鸣声有没有办法在Ruby或Python中做到这一点？我真的不在乎输出编码是什么(.wav、.mp3、.ogg等等)，但我确实想创建一个输出文件。

  2. ruby-on-rails - rails : "missing partial" when calling 'render' in RSpec test - 2

    我正在尝试测试是否存在表单。我是Rails新手。我的new.html.erb_spec.rb文件的内容是:require'spec_helper'describe"messages/new.html.erb"doit"shouldrendertheform"dorender'/messages/new.html.erb'reponse.shouldhave_form_putting_to(@message)with_submit_buttonendendView本身，new.html.erb，有代码:当我运行rspec时，它失败了:1)messages/new.html.erbshou

  3. ruby-on-rails - 由于 "wkhtmltopdf"，PDFKIT 显然无法正常工作 - 2

    我在从html页面生成PDF时遇到问题。我正在使用PDFkit。在安装它的过程中，我注意到我需要wkhtmltopdf。所以我也安装了它。我做了PDFkit的文档所说的一切......现在我在尝试加载PDF时遇到了这个错误。这里是错误:commandfailed:"/usr/local/bin/wkhtmltopdf""--margin-right""0.75in""--page-size""Letter""--margin-top""0.75in""--margin-bottom""0.75in""--encoding""UTF-8""--margin-left""0.75in""-

  4. ruby - 检查 "command"的输出应该包含 NilClass 的意外崩溃 - 2

    为了将Cucumber用于命令行脚本，我按照提供的说明安装了arubagem。它在我的Gemfile中，我可以验证是否安装了正确的版本并且我已经包含了require'aruba/cucumber'在'features/env.rb'中为了确保它能正常工作，我写了以下场景:@announceScenario:Testingcucumber/arubaGivenablankslateThentheoutputfrom"ls-la"shouldcontain"drw"假设事情应该失败。它确实失败了，但失败的原因是错误的:@announceScenario:Testingcucumber/ar

  5. ruby-on-rails - 迷你测试错误 : "NameError: uninitialized constant" - 2

    我遵循MichaelHartl的“RubyonRails教程:学习Web开发”，并创建了检查用户名和电子邮件长度有效性的测试(名称最多50个字符，电子邮件最多255个字符)。test/helpers/application_helper_test.rb的内容是:require'test_helper'classApplicationHelperTest在运行bundleexecraketest时，所有测试都通过了，但我看到以下消息在最后被标记为错误:ERROR["test_full_title_helper",ApplicationHelperTest,1.820016791]test

  6. ruby-on-rails - 相关表上的范围为 "WHERE ... LIKE" - 2

    我正在尝试从Postgresql表(table1)中获取数据，该表由另一个相关表(property)的字段(table2)过滤。在纯SQL中，我会这样编写查询:SELECT*FROMtable1JOINtable2USING(table2_id)WHEREtable2.propertyLIKE'query%'这工作正常:scope:my_scope,->(query){includes(:table2).where("table2.property":query)}但我真正需要的是使用LIKE运算符进行过滤，而不是严格相等。然而，这是行不通的:scope:my_scope,->(que

  7. 使用 ACL 调用 upload_file 时出现 Ruby S3 "Access Denied"错误 - 2

    我正在尝试编写一个将文件上传到AWS并公开该文件的Ruby脚本。我做了以下事情:s3=Aws::S3::Resource.new(credentials:Aws::Credentials.new(KEY,SECRET),region:'us-west-2')obj=s3.bucket('stg-db').object('key')obj.upload_file(filename)这似乎工作正常，除了该文件不是公开可用的，而且我无法获得它的公共(public)URL。但是当我登录到S3时，我可以正常查看我的文件。为了使其公开可用，我将最后一行更改为obj.upload_file(file

  8. ruby - 有人可以帮助解释类创建的 post_initialize 回调吗 (Sandi Metz) - 2

    我正在阅读SandiMetz的POODR，并且遇到了一个我不太了解的编码原则。这是代码:classBicycleattr_reader:size,:chain,:tire_sizedefinitialize(args={})@size=args[:size]||1@chain=args[:chain]||2@tire_size=args[:tire_size]||3post_initialize(args)endendclassMountainBike此代码将为其各自的属性输出1,2,3,4,5。我不明白的是查找方法。当一辆山地自行车被实例化时，因为它没有自己的initialize方法

  9. ruby - 安装 Ruby 时遇到问题(无法下载资源 "readline--patch") - 2

    当我尝试安装Ruby时遇到此错误。我试过查看this和this但无济于事➜~brewinstallrubyWarning:YouareusingOSX10.12.Wedonotprovidesupportforthispre-releaseversion.Youmayencounterbuildfailuresorotherbreakages.Pleasecreatepull-requestsinsteadoffilingissues.==>Installingdependenciesforruby:readline,libyaml,makedepend==>Installingrub

  10. ruby - RVM "ERROR: Unable to checkout branch ."单用户 - 2

    我在新的Debian6VirtualBoxVM上安装RVM时遇到问题。我已经安装了所有需要的包并使用下载了安装脚本(curl-shttps://rvm.beginrescueend.com/install/rvm)>rvm，但以单个用户身份运行时bashrvm我收到以下错误消息:ERROR:Unabletocheckoutbranch.安装在这里停止，并且(据我所知)没有安装RVM的任何文件。如果我以root身份运行脚本(对于多用户安装)，我会收到另一条消息:Successfullycheckedoutbranch''安装程序继续并指示成功，但未添加.rvm目录，甚至在修改我的.bas

随机推荐