jjzjj

c++ - 改进极小极大算法

coder 2024-02-09 原文

目前我正在使用 C++ 开发黑白棋/黑白棋游戏。我已经“完成”了它，只是当我将它设置为产生半具有挑战性的 AI 的深度时，我用于计算机播放器的 Minimax 算法非常慢。

我的游戏的基本设置是棋盘由二维数组表示，棋盘上的每个单元格都在数组中分配一个值(xMarker，oMarker，或下划线)。

这是目前为止的 minimax 算法:

signed int Computer::simulate(Board b, int depth, int tempMarker) {

if (depth > MAX_DEPTH || b.gameOver()) {
    int oppMarker = (marker == xMarker) ? oMarker : xMarker;
    return b.countForMarker(marker) - b.countForMarker(oppMarker);
}

//if we're simulating  our turn, we want to find the highest value (so we set our start at -64)
//if we're simulating the opponent's turn, we want to find the lowest value (so we set our start at 64)
signed int start = (tempMarker == marker) ? -64 : 64;

for (int x = 0; x < b.size; x++) {
    for (int y = 0; y < b.size; y++) {

        if (b.markerArray[x][y] == underscore) {

            Board *c = b.duplicate();

            if(c->checkForFlips(Point(x,y), tempMarker, true) > 0) {

                int newMarker = (tempMarker == xMarker) ? oMarker : xMarker;
                int r = simulate(*c, depth+1, newMarker);

                //'marker' is the marker assigned to our player (the computer), if it's our turn, we want the highest value
                if (tempMarker == marker) {
                    if(r > start) start = r;
                } else {
                //if it's the opponent's turn, we want the lowest value
                    if(r < start) start = r;
                }

            }

            delete c;

        }

    }
}

return start;

}

函数 checkForFlips() 返回在给定单元格播放所产生的翻转次数。 MAX_DEPTH 目前设置为 6，而且速度很慢(每次播放大约需要 10-15 秒)

到目前为止我想到的唯一想法是每次都存储树，然后从我离开的地方继续，但我不确定如何去实现它或者它是否会太有效了。任何想法或建议将不胜感激!

最佳答案

计算 minimax 很慢。 第一个可能的优化是 alpha-beta 剪枝: http://en.wikipedia.org/wiki/Alpha-beta_pruning

关于c++ - 改进极小极大算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/6887838/

amp极大sectioncodestartc++algorithm

有关c++ - 改进极小极大算法的更多相关文章

  1. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

    我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

  2. 区块链之加解密算法&数字证书 - 2

    目录一.加解密算法数字签名对称加密DES(DataEncryptionStandard)3DES(TripleDES)AES(AdvancedEncryptionStandard)RSA加密法DSA(DigitalSignatureAlgorithm)ECC(EllipticCurvesCryptography)非对称加密签名与加密过程非对称加密的应用对称加密与非对称加密的结合二.数字证书图解一.加解密算法加密简单而言就是通过一种算法将明文信息转换成密文信息，信息的的接收方能够通过密钥对密文信息进行解密获得明文信息的过程。根据加解密的密钥是否相同，算法可以分为对称加密、非对称加密、对称加密和非

  3. ruby - 使用 `+=` 和 `send` 方法 - 2

    如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案 恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:

  4. ruby - 如何计算 Liquid 中的变量 +1 - 2

    我对如何计算通过{%assignvar=0%}赋值的变量加一完全感到困惑。这应该是最简单的任务。到目前为止，这是我尝试过的:{%assignamount=0%}{%forvariantinproduct.variants%}{%assignamount=amount+1%}{%endfor%}Amount:{{amount}}结果总是0。也许我忽略了一些明显的东西。也许有更好的方法。我想要存档的只是获取运行的迭代次数。 最佳答案 因为{{incrementamount}}将输出您的变量值并且不会影响{%assign%}定义的变量，我

  5. arrays - Ruby 数组 += vs 推送 - 2

    我有一个数组数组，想将元素附加到子数组。+=做我想做的，但我想了解为什么push不做。我期望的行为(并与+=一起工作):b=Array.new(3,[])b[0]+=["apple"]b[1]+=["orange"]b[2]+=["frog"]b=>[["苹果"],["橙子"],["Frog"]]通过推送，我将推送的元素附加到每个子数组(为什么？):a=Array.new(3,[])a[0].push("apple")a[1].push("orange")a[2].push("frog")a=>[[“苹果”、“橙子”、“Frog”]、[“苹果”、“橙子”、“Frog”]、[“苹果”、“

  6. += 的 Ruby 方法 - 2

    有没有办法让Ruby能够做这样的事情？classPlane@moved=0@x=0defx+=(v)#thisiserror@x+=v@moved+=1enddefto_s"moved#{@moved}times,currentxis#{@x}"endendplane=Plane.newplane.x+=5plane.x+=10putsplane.to_s#moved2times,currentxis15 最佳答案 您不能在Ruby中覆盖复合赋值运算符。任务在内部处理。您应该覆盖+，而不是+=。plane.a+=b与plane.a=

  7. ruby - Sinatra + Heroku + Datamapper 使用 dm-sqlite-adapter 部署问题 - 2

    出于某种原因，heroku尝试要求dm-sqlite-adapter，即使它应该在这里使用Postgres。请注意，这发生在我打开任何URL时-而不是在gitpush本身期间。我构建了一个默认的Facebook应用程序。gem文件:source:gemcuttergem"foreman"gem"sinatra"gem"mogli"gem"json"gem"httparty"gem"thin"gem"data_mapper"gem"heroku"group:productiondogem"pg"gem"dm-postgres-adapter"endgroup:development,:t

  8. ruby - Ruby 中字符串运算符 + 和 << 的区别 - 2

    我是Ruby和这个网站的新手。下面两个函数是不同的，一个在函数外修改变量，一个不修改。defm1(x)x我想确保我理解正确-当调用m1时，对str的引用被复制并传递给将其视为x的函数。运算符当调用m2时，对str的引用被复制并传递给将其视为x的函数。运算符+创建一个新字符串，赋值x=x+"4"只是将x重定向到新字符串，而原始str变量保持不变。对吧？谢谢 最佳答案 String#+::str+other_str→new_strConcatenation—ReturnsanewStringcontainingother_strconc

  9. ruby-on-rails - 我可以用鸭子类型(duck typing)改进这种方法吗？ - 2

    希望我没有误解“ducktyping”的含义，但从我读到的内容来看，这意味着我应该根据对象如何响应方法而不是它是什么类型/类来编写代码。代码如下:defconvert_hash(hash)ifhash.keys.all?{|k|k.is_a?(Integer)}returnhashelsifhash.keys.all?{|k|k.is_a?(Property)}new_hash={}hash.each_pair{|k,v|new_hash[k.id]=v}returnnew_hashelseraise"CustomattributekeysshouldbeID'sorPropertyo

  10. ruby - rails 3.2.2(或 3.2.1)+ Postgresql 9.1.3 + Ubuntu 11.10 连接错误 - 2

    我正在使用PostgreSQL9.1.3(x86_64-pc-linux-gnu上的PostgreSQL9.1.3，由gcc-4.6.real(Ubuntu/Linaro4.6.1-9ubuntu3)4.6.1，64位编译)和在ubuntu11.10上运行3.2.2或3.2.1。现在，我可以使用以下命令连接PostgreSQLsupostgres输入密码我可以看到postgres=#我将以下详细信息放在我的config/database.yml中并执行“railsdb”，它工作正常。开发:adapter:postgresqlencoding:utf8reconnect:falsedat

随机推荐