百科问答小站 logo
百科问答小站 font logo



蒙特卡罗算法是什么? 第1页

  

user avatar   tsun 网友的相关建议: 
      

太数学的东西就不说了,只用通俗唱法回答楼主的问题。

蒙特卡罗算法并不是一种算法的名称,而是对一类随机算法的特性的概括。媒体说“蒙特卡罗算法打败武宫正树”,这个说法就好比说“我被一只脊椎动物咬了”,是比较火星的。实际上是ZEN的算法具有蒙特卡罗特性,或者说它的算法属于一种蒙特卡罗算法。

那么“蒙特卡罗”是一种什么特性呢?我们知道,既然是随机算法,在采样不全时,通常不能保证找到最优解,只能说是尽量找。那么根据怎么个“尽量”法儿,我们我们把随机算法分成两类:

  • 蒙特卡罗算法:采样越多,越近似最优解;
  • 拉斯维加斯算法:采样越多,越有机会找到最优解;

举个例子,假如筐里有100个苹果,让我每次闭眼拿1个,挑出最大的。于是我随机拿1个,再随机拿1个跟它比,留下大的,再随机拿1个……我每拿一次,留下的苹果都至少不比上次的小。拿的次数越多,挑出的苹果就越大,但我除非拿100次,否则无法肯定挑出了最大的。这个挑苹果的算法,就属于蒙特卡罗算法——尽量找好的,但不保证是最好的

而拉斯维加斯算法,则是另一种情况。假如有一把锁,给我100把钥匙,只有1把是对的。于是我每次随机拿1把钥匙去试,打不开就再换1把。我试的次数越多,打开(最优解)的机会就越大,但在打开之前,那些错的钥匙都是没有用的。这个试钥匙的算法,就是拉斯维加斯的——尽量找最好的,但不保证能找到

所以你看,这两个词并不深奥,它只是概括了随机算法的特性,算法本身可能复杂,也可能简单。这两个词本身是两座著名赌城,因为赌博中体现了许多随机算法,所以借过来命名。

这两类随机算法之间的选择,往往受到问题的局限。如果问题要求在有限采样内,必须给出一个解,但不要求是最优解,那就要用蒙特卡罗算法。反之,如果问题要求必须给出最优解,但对采样没有限制,那就要用拉斯维加斯算法。对于机器围棋程序而言,因为每一步棋的运算时间、堆栈空间都是有限的,而且不要求最优解,所以ZEN涉及的随机算法,肯定是蒙特卡罗式的。

机器下棋的算法本质都是搜索树,围棋难在它的树宽可以达到好几百(国际象棋只有几十)。在有限时间内要遍历这么宽的树,就只能牺牲深度(俗称“往后看几步”),但围棋又是依赖远见的游戏,甚至不仅是看“几步”的问题。所以,要想保证搜索深度,就只能放弃遍历,改为随机采样——这就是为什么在没有MCTS(蒙特卡罗搜树)类的方法之前,机器围棋的水平几乎是笑话。而采用了MCTS方法后,搜索深度就大大增加了。比如,在题主说的ZEN与武宫正树九段的对局中,我们可以看这一步棋:


武宫正树九段(执白)第53步大飞,明显企图攻角,而ZEN(执黑)却直接不理,放弃整个右下角,转而把中腹走厚。这个交换究竟是否划算,就不在这里讨论了,但我们至少可以看出,ZEN敢于在此脱先,舍弃这么大的眼前利益,其搜索深度确实达到了人类专业棋手的水平。




  

相关话题

  请问有哪些最优化算法可以做全局优化? 
  如何评价李开复称「ICO 是最大的泡沫,可能导致 AI 泡沫破裂」? 
  如何看待北大古生物「一个人的毕业照」主人公转行计算机?「冷转码」(冷门专业转码农)现象反映出哪些问题? 
  Windows 7用的时间久了变慢怎么办? 
  卡内基梅隆大学(CMU)的Eric Xing(邢波)教授为什么能读完一般学校的分子生物学PhD后到伯克利去CS PhD? 
  装上固态硬盘后,如何处理旧的机械硬盘? 
  电脑打补丁会导致机器很慢,可以不打补丁吗? 
  5173打不开是怎么回事? 
  未来五年,数据科学家(Data Scientist)的岗位需求会如何变化? 
  面对飞速发展的人工智能,我们应该如何调整对孩子的教育? 

前一个讨论
你身边有网瘾少女吗? 她们的日常是怎样的?
下一个讨论
痘痘没了,留下痘印痘坑怎么办?





© 2024-11-21 - tinynew.org. All Rights Reserved.
© 2024-11-21 - tinynew.org. 保留所有权利