网页
资讯
视频
图片
知道
文库
贴吧
地图
采购
进入贴吧
全吧搜索
吧内搜索
搜贴
搜人
进吧
搜标签
日
一
二
三
四
五
六
签到排名:今日本吧第
个签到,
本吧因你更精彩,明天继续来努力!
本吧签到人数:0
一键签到
可签
7
级以上的吧
50
个
一键签到
本月漏签
0
次!
0
成为超级会员,赠送8张补签卡
如何使用?
点击日历上漏签日期,即可进行
补签
。
连续签到:
天 累计签到:
天
0
超级会员单次开通12个月以上,赠送连续签到卡3张
使用连续签到卡
12月15日
漏签
0
天
宇宙溯源吧
关注:
40
贴子:
1,887
看贴
图片
吧主推荐
游戏
5
回复贴,共
1
页
<返回宇宙溯源吧
>0< 加载中...
【长文恐惧症】不要再用穷举法来侮辱围棋和阿尔法狗
只看楼主
收藏
回复
宇宙溯源
宇宙面
9
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
阿西的HCl镇楼
前言:
自从阿尔法狗第一次赢了欧洲冠军后,就一直有人在说穷举法,叫嚣着不过是个职业二段,什么时候干掉李世石再说话;现在阿尔法狗光速打脸,第一局比赛中干掉李世石,依然有人在拿穷举法狡辩。
每次看到高举【穷举法大法好】的人,我真想一棋盘加361颗棋子全塞到他的嘴巴里。
楼下开始放正文。
送TA礼物
IP属地:浙江
1楼
2016-05-27 13:53
回复
宇宙溯源
宇宙面
9
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
一、围棋他妈的到底有多少种可能性?
让我们先来看看常用的两种估计方法。
1.假设不会出现大家都被提光再从头再来的情况,那么,第一步有361种选择,第二步有360种选择,以后的情况大致如此,我们就以361为界,那么变化数是361!,约为10的768次方。
2.另一种估计方法大概是宋朝的沈括老先生首先使用的:棋盘上每个点有黑、白、空三种状态,所以围棋变化数是3的361次方,约为10的172次方,用沈老先生的说法,就是“连书‘万’字四十三”。这虽然也很大,但比起前面的估计值来,小得实在是太多了。
不幸的是,沈老先生的估计方法是错误的。他只考虑了这种种状态,却没有考虑这些状态间的相互关系。就比如数学中的图,沈老先生只考虑了顶点的总数,却忘了把连接顶点的边算进去了。
那么回到第一种方法计算出来的数值:10的768次方,这又是个什么概念呢?我们知道,宇宙中所有基本粒子的总数,据估计为10的80次方。然而,对我们来说,10的768次方和10的80次方,又和无穷有什么区别?(这意味着把已知全部宇宙的物质做成内存,每个原子,干脆,每个夸克存储一种状态,都是远远不够的)
看到这里,你一定会想,哇,围棋的变化这么多啊!
那你就太天真了!
IP属地:浙江
2楼
2016-05-27 13:53
回复
收起回复
宇宙溯源
宇宙面
9
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
很遗憾的是,连第一种估计方法都是错误的。围棋真正的变化数,连10的(3的361次方)次方都挡不住,大学学历的人都清楚,一旦出现指数天梯,那这个数字有多大已经是不可想象的了。
如果从结局入手的话,棋盘上一共361个点位,局终时每一个点位上不是白子就是黑子,要么就是空,也就是说每一个点位有三种选择,那么按照排列组合的规律,围棋的结局就有3的361次方=1.7408956e+172
《梦溪笔谈》的作者沈括,就是用这种方法在计算,按他的话说,这个数字的大小是——连书“万”字四十三次!
这还单单只是结局的数量,因为围棋过程中势必会出现打劫——也就是双方互相提子的情况,这就导致了哪怕是同一种结局,也可能拥有着无数种完全不同的过程:比如这一局在第N手提子、那一局在第N+1手提子;这一局连提两子,那一局隔一子提一子……沈括的这种算法,其实只是一个终态或者说静态值,并没有包含对弈过程中可能出现的动态变量。比如“2+3=?”沈括确实计算出了“5”这个答案,但是反过来说“5”却不一定等于“2+3”,它也可以等于“1+4”,如果取上小数的话,能够让“5=?+?”这个等式成立的值就是无穷多!
也就是说:围棋结局的数量确实是一个有穷的数值,但是导致这些有穷结局的过程量,却是无穷的!所以说围棋的棋局数量,是没办法枚举出来的,又所谓:纵横十九行,围棋千古无同局!
IP属地:浙江
3楼
2016-05-27 13:53
回复
收起回复
宇宙溯源
宇宙面
9
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
二、你说了那么多废话,你怎么还不说阿尔法狗是怎么下围棋的?
阿尔法狗之所以能够战胜九段高手李世石。我们先来看看官方怎么用专业名词跟民众吹逼的:
“它背后主要的方法是 Value Networks(价值网络)和 Policy Networks(策略网络),其中 Value Networks 评估棋盘位置,Policy Networks 选择下棋步法。这些神经网络模型通过一种新的方法训练,结合人类专家比赛中学到的监督学习,以及在自己和自己下棋(Self-Play)中学到强化学习。这不需要任何前瞻式的 Lookahead Search,神经网络玩围棋游戏的能力,就达到了最先进的蒙特卡洛树搜索算法的级别(这种算法模拟了上千种随机自己和自己下棋的结果)。我们也引入了一种新搜索算法,这种算法将蒙特卡洛模拟和价值、策略网络结合起来。”
说了半天,阿尔法狗这些看起来很牛逼的什么鬼网络是什么意思呢?
其实很简单,阿尔法狗的两个网络——价值网络和策略网络,就是围棋中常说的“大局观”和“算子能力”。
价值网络给予了阿尔法狗对整个棋盘局势的判断,也就是大局观,大局观是人类棋手最大的优势,有了大局观,你可以在很短的时间内筛选掉绝大多数无用的落子。如今阿尔法狗装备了价值网络,使得阿尔法狗能够快速的判断整个棋盘哪里最为重要最为紧迫,做到主动出击而不是被动应战,能够“吃着碗里看着锅里”而不是“捡了芝麻丢了西瓜”。这是他能够从一堆围棋AI中脱颖而出的很大一个原因。
策略网络则是旧调重弹了。下过棋的都知道,对这一步棋后续的发展,能够预测得越后,一般就说明这个人水平越高。拿围棋举例,经过一段时间学习的人(达到了可以独立依照正常套路对局能力)一般可以思考落子后的两到三步的大部分可能性,达到段位级别至少能够分析五步,而对于李世石这种职业九段的大神来说,给他时间,他能分析到之后十多步的情况。然而这在阿尔法狗的策略网络面前都是不堪一击的,十多步的预测对于阿尔法狗来说那就是饶痒痒,可以说,在局部作战,阿尔法狗是无敌的。
IP属地:浙江
4楼
2016-05-27 13:53
回复
收起回复
宇宙溯源
宇宙面
9
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
四、回归标题
总而言之我跟你们这些人废话了这么多,就是想说一句:
你们这些整天穷举的啊,偶摸希裸衣!你们呐,穷举也是要按照基本法来的!不懂围棋又不懂编程,就不要瞎逼逼,不然闹出笑话下不了台的话就excited了!
IP属地:浙江
6楼
2016-05-27 13:54
回复
收起回复
宇宙溯源
宇宙面
9
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
六、穷举法(补充)
什么是穷举法?三体吧的起点是维基百科,落点是百度百科,于是我都翻了一遍给一些不理解概念的人来看。
维基百科
计算的复杂性最明显的算法就是穷举法,即寻找一切组合并取其最短。这种算法的排列数为n!(n的阶乘,其中n为节点个数)。用动态规划技术,我们可以在O(n22n))[1]时间内解决此问题。虽然这仍然是指数级的,但要比O(n!))快得多。
百度百科
本词条由“科普中国”百科科学词条编写与应用工作项目提供内容并参与编辑
穷举法的基本思想是根据题目的条件确定答案的范围,并在此范围内对所有可能的情况逐一验证,直到全部情况验证完毕。若某个情况验证符合题目的全部条件,则为本问题的一个解;若全部情况验证后都不符合题目的全部条件,则本题无解。穷举法也称为枚举法。
爱问知识人
穷举法也叫枚举法或列举法。
在研究对象是由有限个元素构成的集合时,把所有对象一一列举出来,再对其一一进行研究。
IP属地:浙江
7楼
2016-05-27 13:54
回复
收起回复
登录百度账号
扫二维码下载贴吧客户端
下载贴吧APP
看高清直播、视频!
贴吧热议榜
1
济大泡面大叔非个人原因离校
2523720
2
冯骥说自己白来TGA了
1935634
3
韩国紧急向中美日通报
1184733
4
明日方舟终末地二测实机演示
1061268
5
樊振东0-3不敌徐瑛彬
940950
6
TGA收视率创历史最高
918000
7
韩宪法院16日就弹劾案举行会议
795685
8
韩国代理总统称将加强韩美同盟
585904
9
湖南卫视跨年阵容官宣
471345
10
斯诺克官方强烈反对丁俊晖言论
400420
贴吧页面意见反馈
违规贴吧举报反馈通道
贴吧违规信息处理公示