AlphaGo的蒙特卡洛搜索
强化学习 机器学习 游戏AI
AlphaGo的蒙特卡洛搜索
强化学习 机器学习 游戏AI

AlphaGo的蒙特卡洛搜索

AlphaGo蒙特卡洛树搜索
  这篇我们来详细讲讲AlphaGo的蒙特卡洛搜索。AlphaGo的智能体现在两个地方：一个是基于现有的深度学习和强化学习技术学习，通过自对弈和专家经验学习到的策略网络和值网络；另一个则是体现在实战阶段，AlphaGo并没有直接应用策略网络包含的知识进行对弈，而是将训练好的策略网络和值网络结合到蒙特卡洛搜索中，实现前瞻性的决策。我们先来捋顺一下AlphaGo中蒙特卡洛搜索的过程，然后解释下这种搜索的合理性。
  蒙特卡洛搜索依托的数据结构首先是一棵树，树的根节点是当前AlphaGo需要进行决策的棋盘的状态s。这里需要注意的是，AlphaGo在决策每个落子的时候都会重新运行搜索，相应的也会重新建一棵搜索树。
  我们考虑像这样的一棵搜索树都需要哪些量来确定呢？首先，根节点的孩子节点是什么呢？应该是棋盘的每一个可能的次状态，也就是说此时此刻每一个合法的落子都应该对应一个孩子节点。但是次状态太多，全部扩展的话，树的深度会受到限制。在蒙特卡洛搜索中，会根据指标选择一个动作作为对当前状态的扩展，扩展到新的状态后，再根据这个定量的指标选择一个新的动作，使用的定量指标如下

a_t = \arg\max_a(Q(s_t,a)+u(s_t,a)).

每个量的含义后面分析，目前我们只需要知道针对每个棋盘的状态s_t，a_t 是怎么来的就行。按照这种规则不断扩展搜索树，直到达到树的最大深度，或者到达终止状态了，当然，对于围棋来讲，前者的可能性更大。假设到达了第一个不满足约束条件的叶节点，蒙特卡洛搜索的一次模拟就结束了，然后，蒙特卡洛搜索会从根节点开始继续模拟，而且是在之前生成的搜索树的基础上模拟，假设模拟了 n 次，n 应该是一个较大值，比如100,000。
  接下来我们来说这个搜索树的边存储的变量以及相应的评估方式。搜索树的每条边都存储三个变量：Q(s_t,a)、u(s_t,a) 和 N(s_t,a)。其中，N(s_t,a) 表示在所有的 n 次模拟中，(s_t,a) 这条边被访问的次数，而 Q(s_t,a)和u(s_t,a)都是在这个次数的基础上定义的统计量。 Q(s_t,a) 表示沿着当前路径扩展搜索树获胜的数学期望，以获得的奖励的均值来统计

Q(s,a)=\frac{1}{N(s,a)}\sum_{i=1}^{n}1(s,a,i)V(s_L^i).

1(s,a,i) 表示在第 i 次模拟中 (s,a) 这条边是否被使用过，而每条边的 N(s,a) 正是 \sum_{i=1}^{n}1(s,a,i)。所以，Q(s,a) 表示的正是奖励的期望。公式中的 V(s_L^i) 指的是第 i 次模拟得到的奖励值，s_L^i 则表示该次模拟到树的第 L 层停止后对应的叶节点，V(s_L^i) 由两部分组成

V(s_L)=(1-\lambda)v_\theta(s_L)+\lambda z_L.

v_\theta(s_L) 是基于已经训练好的值网络的一次快速评估，评估在状态 s_L 下获胜的数学期望，z_L 是使用训练好的轻量级策略网络 p_\pi 进行快速的连续的决策，从而在短时间内从状态 s_L 到达某一方获胜的终止状态 s_T 后得到的奖励值。
  在刚开始的时候，每个可能的次状态的 Q(s,a) 都是 \infty，因为 N(s,a) = 0。所以一开始就是随机选择一个，第一次模拟结束后，Q(s,a) 就不是 \infty 了，继而其他的次状态会被继续选中进行模拟，当众多状态都被模拟过一遍时候，就开始进入公平竞争了，谁的 Q 值大，谁被遍历的次数就多。
  u(s,a) 是bonus

u(s,a) \propto \frac{P(s,a)}{1+N(s,a)},

初始化为 P(s,a)，即根据专家经验学习的策略网络 p_\sigma 的对状态-动作对 (s,a) 的评估，而这个bonus会随着访问次数增加而递减，从而直接地维护了每个次状态被访问到的公平性，是exploration思想的一种体现。
  在完成所有的 n 次遍历后，我们选择被访问次数最多的动作执行即可。

184条评论

  16. tubidy

    I’m impressed, I must say. Seldom do I encounter a blog that’s both educative and engaging, and let me tell you, you’ve hit the nail on the head. The problem is something which too few people are speaking intelligently about. I’m very happy that I stumbled across this in my search for something relating to this.

  17. 슬롯사이트

    You’re so awesome! I do not suppose I have read through anything like that before. So good to discover another person with some genuine thoughts on this issue. Seriously.. thank you for starting this up. This web site is something that’s needed on the web, someone with a little originality.

  18. 토토사이트

    The next time I read a blog, Hopefully it doesn’t disappoint me as much as this particular one. I mean, I know it was my choice to read, however I truly believed you would have something interesting to say. All I hear is a bunch of crying about something that you could possibly fix if you weren’t too busy seeking attention.

  28. 바카라사이트

    The next time I read a blog, I hope that it won’t disappoint me as much as this one. I mean, Yes, it was my choice to read through, however I genuinely believed you would have something helpful to say. All I hear is a bunch of complaining about something that you can fix if you were not too busy seeking attention.

  29. sugar defender reviews

    I’ve struggled with blood sugar level fluctuations for years, and it truly impacted my power
    degrees throughout the day. Because starting Sugar Protector, I feel much more balanced and alert, and I don’t experience those mid-day slumps any longer!
    I like that it’s a natural option that works without any rough side
    effects. It’s truly been a game-changer for me

  30. sugar defender reviews

    As a person who’s constantly been cautious about my blood sugar
    level, locating Sugar Protector has been a relief. I feel a lot extra in control, and my current exams have actually revealed
    positive enhancements. Knowing I have a dependable supplement to
    support my regular provides me peace of mind. I’m so grateful for
    Sugar Protector’s effect on my health and wellness!

  31. Sugar Defender

    As someone that’s always bewared concerning my blood sugar, locating
    Sugar Defender has actually been a relief. I really feel a
    lot extra in control, and my recent check-ups
    have actually shown favorable enhancements. Recognizing
    I have a trusted supplement to sustain my routine gives me satisfaction. I’m so thankful
    for Sugar Defender’s influence on my wellness!

  32. sugar defender reviews

    For many years, I’ve battled uncertain blood sugar swings
    that left me really feeling drained pipes and sluggish.
    But considering that incorporating Sugar my energy levels are now steady and
    constant, and I no longer strike a wall in the afternoons.
    I value that it’s a mild, natural strategy that doesn’t
    come with any type of unpleasant side effects.
    It’s truly changed my daily life.

  33. sugar defender

    Finding Sugar Defender has been a game-changer for me, as
    I’ve constantly been vigilant concerning handling my blood sugar
    level degrees. I now feel equipped and confident in my
    ability to maintain healthy and balanced levels, and my newest health checks have actually mirrored this progression. Having a credible
    supplement to match my a huge source of comfort, and
    I’m genuinely appreciative for the considerable
    distinction Sugar Defender has made in my overall well-being.

  34. sugar defender

    Incorporating Sugar Protector right into my daily routine has actually been a game-changer for my overall wellness.
    As someone who already prioritizes healthy consuming, this supplement has
    offered an included boost of security. in my power degrees, and my wish for unhealthy treats so easy can have
    such an extensive impact on my day-to-day live.

  39. blue dream strain

    Right here is the right website for everyone who wants to understand this topic. You understand a whole lot its almost tough to argue with you (not that I personally would want to…HaHa). You certainly put a fresh spin on a topic which has been written about for ages. Wonderful stuff, just wonderful.

  41. eco bij

    Good day! Do you know if they make any plugins to help with Search Engine Optimization? I’m trying to
    get my website to rank for some targeted keywords but I’m not seeing very
    good gains. If you know of any please share. Cheers! You can read similar art here: Blankets

  83. gay porn

    You’re so interesting! I do not suppose I have read a single thing like this before. So nice to discover another person with some original thoughts on this subject. Really.. many thanks for starting this up. This website is one thing that’s needed on the web, someone with a bit of originality.

  84. porn

    I really love your website.. Very nice colors & theme. Did you make this website yourself? Please reply back as I’m hoping to create my own site and would like to learn where you got this from or what the theme is named. Thank you.

  93. porn

    After I initially left a comment I seem to have clicked on the -Notify me when new comments are added- checkbox and from now on whenever a comment is added I receive four emails with the exact same comment. Perhaps there is an easy method you can remove me from that service? Kudos.

  100. porn

    After looking over a handful of the articles on your site, I seriously like your technique of blogging. I book marked it to my bookmark webpage list and will be checking back in the near future. Please visit my website too and tell me what you think.

  101. poocoin

    I’m amazed, I must say. Rarely do I encounter a blog that’s both equally educative and entertaining, and let me tell you, you’ve hit the nail on the head. The problem is an issue that too few men and women are speaking intelligently about. I am very happy that I stumbled across this in my search for something concerning this.

  102. Vavada PL

    Having read this I believed it was really informative. I appreciate you spending some time and energy to put this article together. I once again find myself personally spending way too much time both reading and commenting. But so what, it was still worthwhile.

  109. view

    Hi, There’s no doubt that your website might be having internet browser compatibility problems. When I look at your web site in Safari, it looks fine however, if opening in I.E., it has some overlapping issues. I just wanted to provide you with a quick heads up! Apart from that, fantastic site.

  110. visit this site right here

    I’m amazed, I must say. Seldom do I come across a blog that’s both equally educative and entertaining, and let me tell you, you’ve hit the nail on the head. The problem is something that too few people are speaking intelligently about. Now i’m very happy I came across this during my search for something relating to this.

  111. company website

    An impressive share! I’ve just forwarded this onto a friend who has been conducting a little research on this. And he actually ordered me dinner due to the fact that I discovered it for him… lol. So let me reword this…. Thanks for the meal!! But yeah, thanx for spending some time to talk about this matter here on your blog.

  115. kiara moon porn

    An impressive share! I’ve just forwarded this onto a co-worker who had been conducting a little research on this. And he in fact bought me lunch due to the fact that I stumbled upon it for him… lol. So let me reword this…. Thank YOU for the meal!! But yeah, thanx for spending some time to discuss this subject here on your internet site.

  119. SBI証券のFX取引の単位は

    Now, generalize from that time: It’s all properly and good to have design targets and a perfect game pictured in your head when you begin, however it’s important to be open to change and sensible about what can and can’t be finished in a reasonable timeframe, for an affordable sum of money, with the personnel and know-how accessible to you.

  126. Hoka Shoes

    Can I simply just say what a relief to find somebody who really understands what they’re talking about online. You definitely realize how to bring a problem to light and make it important. More and more people really need to read this and understand this side of the story. It’s surprising you aren’t more popular given that you surely possess the gift.

  127. sugar defender reviews

    sugar defender reviews Finding Sugar
    Defender has been a game-changer for me, as I have actually constantly been vigilant concerning handling my blood sugar levels.
    I now really feel empowered and confident in my ability to maintain healthy and balanced levels, and my most recent health
    checks have actually mirrored this development. Having a reliable supplement to enhance my a significant resource
    of comfort, and I’m really thankful for the significant difference Sugar Protector has made in my general
    health.

  129. rae crush porn

    I’m amazed, I must say. Rarely do I encounter a blog that’s both educative and interesting, and without a doubt, you’ve hit the nail on the head. The problem is an issue that not enough men and women are speaking intelligently about. I am very happy I came across this during my search for something regarding this.

  136. Crypto

    An impressive share! I’ve just forwarded this onto a colleague who has been doing a little homework on this. And he in fact bought me lunch because I discovered it for him… lol. So allow me to reword this…. Thanks for the meal!! But yeah, thanks for spending some time to discuss this matter here on your blog.

  142. Best Stocks

    Next time I read a blog, Hopefully it won’t fail me as much as this one. After all, I know it was my choice to read through, but I really believed you would probably have something helpful to say. All I hear is a bunch of complaining about something you could fix if you were not too busy searching for attention.

  150. 自分を悪く言う人

    The sport depicts or mentions numerous historical figures, including William the Conqueror, Charlemagne, Genghis Khan, Harold Godwinson, Robert Guiscard, Robert the Bruce, Harald Hardrada, El Cid, Constantine X Doukas, Harun al-Rashid, Alexios I Komnenos, Richard the Lionheart, Ivar the Boneless, Alfred the great, Baldwin I of Jerusalem, Boleslaw the Daring and Saladin, however permits for the player to choose less-vital figures resembling minor dukes and counts, and for the creation of totally new characters with the usage of the Ruler Designer DLC.

  152. prostavive

    Hi there! I could have sworn I’ve visited this web site before but after browsing through many of the articles I realized it’s new to me. Anyhow, I’m definitely happy I came across it and I’ll be bookmarking it and checking back often.

  155. https://make1m.com/

    An outstanding share! I have just forwarded this onto a colleague who has been conducting a little research on this. And he actually ordered me lunch due to the fact that I stumbled upon it for him… lol. So allow me to reword this…. Thank YOU for the meal!! But yeah, thanks for spending time to talk about this issue here on your web page.

  156. https://realestatemarket.us.com/

    Can I simply just say what a comfort to find somebody that truly understands what they are talking about over the internet. You certainly realize how to bring a problem to light and make it important. More and more people have to check this out and understand this side of the story. I can’t believe you aren’t more popular since you most certainly possess the gift.

  158. 5starsstocks.com

    An impressive share! I’ve just forwarded this onto a friend who has been doing a little research on this. And he in fact bought me lunch due to the fact that I found it for him… lol. So allow me to reword this…. Thank YOU for the meal!! But yeah, thanks for spending some time to discuss this issue here on your internet site.

  167. more help

    Hello there! I could have sworn I’ve visited this site before but after browsing through a few of the posts I realized it’s new to me. Regardless, I’m certainly pleased I stumbled upon it and I’ll be book-marking it and checking back regularly!

  171. view website

    The very next time I read a blog, Hopefully it won’t fail me as much as this particular one. After all, I know it was my choice to read, however I genuinely believed you would have something interesting to talk about. All I hear is a bunch of complaining about something that you could possibly fix if you weren’t too busy seeking attention.

  180. Ufabet

    An outstanding share! I’ve just forwarded this onto a friend who had been conducting a little research on this. And he actually bought me dinner simply because I discovered it for him… lol. So allow me to reword this…. Thanks for the meal!! But yeah, thanks for spending time to discuss this matter here on your site.

发表回复

您的电子邮箱地址不会被公开。