好,那我们最后再来谈一下那个 stochastic Games,就是如果这个game, 这个游戏里面有一些随机,比如说你是像大富翁你要掷个骰子,没有人知道掷骰子出来 结果是怎么样,好,那这样的话,我们在 search 的过程,我们就必须要 introduce 一个新的叫chance node 来 好,那这 chance node 就是,比如说,在这边你必须要,如果 0.5 0.5 你可能是丢个硬币嘛 那如果是正面的话,往这就是这一支,那反面就是这一支,等等,那 我们如果今天要做一样,这里 面我们什么叫做optimum decision,基本上我们可能不再是 原来的那个直接的值,而是我们要 minimax 是那个期望值哦,就是 expected minimax value. OK,那它的写出来式子其实还是一样, 就是基本上就是 max 和 min 其实并没有什么差别,这个 差不多,但是如果是你是 chance node 的话,我们就假想把 chance 也当作一个 player,当作一个 player,但是它做事情就是丢骰子,你就把它丢出来,然后决定要走哪 一条路,那这样的话它基本上就是这个期望值嘛,就是直接 Summation 把它的 probility,然后乘上它的回传这个值, 那同样就是跟 minimax 的 Optimum 是一样的意思,当你说 expected minimax 这个东西其他我们说是 perfect play,但是 perfect play 意思是什么呢?就是记得第一个 要套上 minimax Optimum 就是你的对手也是 绝对不会出错,就是一样要最大化他的期望值的情况下,那我们尽量最大化期望值, 意思就是说你在 多次 play 下,你的拿到的总 pay off 是最高的. 你要够多次,那原则上其实讲严重一点,就是无穷多次,也就是一样嘛,就是这种运气成分 即使用你所谓最佳策略,你可能运气很差,所以这一次打的很低,但是 long term 来说,你应该是 OK 的. 好,这是所谓的我们 perfect play 的意思. 好,那你的整个 search 呢基本上跟 minimax 一样,但是我们现在必须多一个就是 chance node. 那在 minimax 里面, 你如果加了 chance node 这个几率进去,其实有一个比较困扰的,是你的 我们要提醒一下,就是 heuristic 是需要特别设计的,要设计的小心一点,因为 原本来说我们大部分的情况下 heuristic 只是一个相对值,对不对,我们不需要绝对,就是对我们来说,譬如说,我们说 国王比皇后重要对不对,那国王你给一千分,皇后给十分,和你 国王给一万分,皇后给一千分,对我们来说没有什么差别.理论上还是一样. 你只要是同样的,某层上放大或 调整,一般来说不见得,在 minimax 上不见得会有什么差别. 可是,今天我在加入 chance node 以后其实会有不一样,譬如说像我们像 下面这两个例子,那这边左边跟右边唯一的差别就是我们把 1,2,3,4 把 它改正,就是你原本这边是一 的,你如果今天换另外一个 heuristic,它的相 对没有变,它就变得 1,20,30,400. OK,它就不同的用,一种非线性放大 的情况下,那你去看一下这边,这蛮明显的,这边是 一一大于一,三三大于三,那你一跟三这边 chance node 你要做的是,它们相,期望值嘛,1 乘上 0.2 加上 3 乘上 0.8 结果是 2.6 好,你可以去算这个数字,这就是 chance node 算的数值的方法,那 你可以同样去算一下这边,那主要问题是在左边这张图,因为这边 2.6 比 2.4 最后你会选择往这边走,但是右边这张图,因为值很明显就是 400 放太大 400 相对是放很大,那你有一个几率往这边走 的情况下,你这个加乘加的很多,所以最后算出来是 96 比 24.2,所以 在右边这张图,你会决定要走 A2 这一个,也就是说如果在原来的 minimax search 的情况下,我们 heuristic 只要是 iii 的变化,意思就是说原本小的还是比较小,相对 order 没变,原本比较差的还是比较差,原本比较好的还是比较好的情况下. 你 minimax 决定不会更改,对吧,往左边,左边这条路好还是左边这条路好,但是这件事情在 expected 的 minimax 是不会成立的,不一样,就是它可以会变化. 就是这两个 heuristic 一个往左走好一个往右走好,所以你在设计 heuristic 的时候 也就是说它的不仅相对的值有意义,这 heuristic 绝对的值是有意义的. 这是一定要小心,所以你在设计 heuristic 的时候,必须要把它绝对的那个值必须一并考虑进去.同理的效率会比原来的差很多,那另外一点,它的 branch factor 呢 你 introduce chance node 之后,branch factor 从原来的 b 变成 bn b 变成 bn,那 bn 是什么呢,就是你 可能走的不同的,哦,不同的 iii,假设你是由六面骰的话 我不管那个几率是不是六分之一,不是六分之一也没关系,因为我 search 还是要 branch 六支, ,将有可能非零的,几率非零的我都要 search 下去 OK,所以这蛮惨的,基本上这个,你如果是,如果大部分就是等于说你 branch factor,有印象吧,基本上 branch factor 只要大一倍,就非常惨,你的 service space 会呈 iii 成长 简单讲就是,你直接 用 expected minimax 去做 search 不管你加不加,第一个是它的 本身 search 就变得非常非常庞大,第二个是你的,之前我们刚刚提的 pruning 的技巧在这边很多都 不太适用,所以这些去这样做,简单讲就是在大部分的问题你都不能这样解,那 有很多技巧来解决这个问题,那我们这边没有细讲,但其中一种很著名的是蒙特卡洛 叫 Monte Carlo simulation, 好,那怎么蒙特卡洛概念是怎么样呢,就是你现在面对是非常大树, 非常庞大的树,可是在这种情况下你没办法去真的去 search ,因为这个树太大, 太夸张,你如果要去做 search,你的深度可能只能一层两层,那我们 不愿意,那蒙特卡洛想法就是那我干脆不要 不要全走这个树,我是譬如说根据我的时间假设说,我的时间容许我 search 一 百万条,10 的 6 次方,search 一百万条 path,那你这个蒙特卡洛就好像是丢骰子,遇到 chance node 呢那你就 真的根据那个chance 的几率丢骰子,丢出来哪一个你就走哪一个. 我就走一条,也就在这边我就走一百万条,10 的 6 次方,走这个 走这里走这边,然后你走,你如果时间容许,你做一百万次一样的事情,你就 真的去丢骰子走一百万次,然后把这个一百万次的结果平均起来当作最后最后这个回传的- 这个值. 好,那这个称为蒙特卡洛搜寻,那它就是基本上深不够. 当然它有很多,这上面有很多地方你都没 search 但是 在几率上来说也是还蛮不错的,那基本上蒙特卡洛不仅适用在 iii,那基本上像 最近几年,像围棋这个东西,围棋因为 iii,如果 我不加任何限制的话,它的 branch 基本上就300多,一开始就 361 每一个点都可以放.就是 你的 branch factor 那么大的情况下,我面对一个那么大的树,其实蒙特卡洛还是蛮有用的,那最近几年比较好的 生效不错的 iii 大致上都是一种蒙特卡洛 situation 的一些辨析,那有兴趣的同学可以在读一下 最近几年的一些 paper,那最后我们再谈一个就是 partially observable Game,那 partially observable 跟 stochastic 它有蛮大不一样,stochastic 就是一个几率,但你也不知道骰子丢出来 会怎么样,但是我们这边讲,partially observable 意思是说你不能观察部分是 对手决定,它现在没有什么几率,即譬如说我们刚讲 Bingo 嘛,对不对,我们画一张 Bingo 这 个图,你不知道你的对手把摆成什么样子,好那 在这种情况下你有不同的 situation,所谓的 optimum 其实是很 arguable 的. 因为你有地方观察,那对方也是一样,你不能完全观察到所有的 information,所以 什么是 optimum 呢,很难讲清楚,那 这部分通常研究都通常涉及 iii 理论,那在这 iii 理论其中有一个蛮著名的东西叫做平衡点,那平衡点,有各种平衡点. 那其一种蛮著名是纳什平衡,那一般而言有一种 大家公认的就是如果在一个游戏,如果纳什平衡存在的话,一般我们会把 纳什平衡称为最佳最佳.这是一般一种讲法. 好,我们这边很简单介绍一下 Nash 的观念.那比较详细的观念其实那像 赛局里面的coursera课上其实也有.也有这样的课程.那大家有兴趣可以去看看. 那大家再去,网络上还有其他资源.那在这门课本的话其实有提到,在chapter 17. 第17章会提到.那我们这边是,略过,我们只讲一下. 那 Nash equilibrium,提出就是这个 Nash 就是John Nash.那 John Nash 有 部片就是拍他的电影啦.A Beautiful Mind.那2001年的电影,那 呃,讲 Nash 的一生.不过他那里面并没有对 Nash 一生讲太多啦.你如果对他一生有兴趣的话 可以看一下.有一种,它是一个蛮不,就 informal 的 introduction. 好,那这边我也是很简单的讲,他的 Nash 平衡意思就是说如果在一个,在,一个 赛局里面,如果当我,每,当我一个player如果我知道其他player的所有他们 呃,所要出的strategy ,所要,所要运行的.所以这我都知道的 在这种情况下,如果我不更,不会更改我的策略, 好,不会更改我的策略,就我认为我的策略对我来说是最好的.那这个情况,如果这同样情况- apply 对每个 player 都 apply 也就每个 player 都知道其他所有 player 的策略而他不会更改他的策略. 就他一样选择这个策略对他最有利.那如果这件事对每一个player 都成立的话,那这,这个点我们称为 Nash 的平衡点. 那,Nash 平衡有些是存在有些是不存在.那它也分成所谓pure equilibrium 还有 mixed equilibrium 那以 pure 来讲的话就是你的 招数就只能出一种.那譬如我举个例子像剪刀石头布这样的游戏里面. 剪刀的单纯,就是纯粹Nash平衡是不存在的嘛.对不对?比如说我就两个人来好了.好,- 那你如果,如果我知道你会出剪刀的话我一定会出石头. 反过来一样,你如果对手知道我会出石头的话那他就不会继续 keep出剪刀.他会应该会改出布.所以你可以看出这里面 呃,纯粹,就pure的Nash平衡是不存在的.那你如果考虑 mixed strategy 的话,那 Nash 平衡存在.然后存在的地方就是出剪刀石头布的几率都是三分之一.好. 那 Nash 平衡其实有解释,又,很容易来解释一个像囚犯两难困境. 那,这是一个例子.就是你想像有两个罪犯,就 A 跟B 那他们,呃,就是被,被询,被警方寻问. 那他们可以考,考虑就是,就是承认犯罪.那,就是,等于,简单说背叛啦. 等于说背叛对,对方把,呃,罪情招认.就是帮助警方 找这些罪证.那另外个可能就是他可以 keep silent 就是打死不招这个样子. 那这边是,这个 table 是他的,呃,utility 就是如果两个人都不招,A B 两个人都不招的情况下, 那,警方就拿不到够多证据,那每个人都最多只能被关一年. 好那相对来说如果一个人打死不招.好,可一个人,B 背叛他,就什么都讲清楚.那警方就, 都会拿到证据嘛.那A 就领很重的罪,被关五年.那同时 B 可能污点证人就,你就不用被关,你就直接free 那 Nash equilibrium 蛮能解释囚犯困境这个问题哦.那囚犯困境这个问题是在描述 说有两个罪犯.那他们,呃,基本上就警方在询问他们.他们可以有两个选择,一个就是招供. 就是把他们的犯罪都招出来.一个就是他抵死不从,就是不跟警方合作. 那这边这个 table 所列出来的是他们的 pay off. 就是或 utility 那也就说如果两个 罪犯他们都不和警方合作那结果就是, 警方没办法找到足够的证据所以他们每个人都只能被关一年. 那另外一个可能是.就是,呃,一个罪犯都不 合作.那另外一个罪犯招了.就是等于说他背叛了 A, 这个 背叛 A 这个朋友.那结果就是罪证很明显所以他们被关五年.那 B 因为可能是就 协助警方,当作污点证人他就直接释放,都没事.那另外有可能就是 两个人都抢着认罪,那结果就是没有人需要当污点证人因为警方不需要他们, 所以罪证简单,明显地,每个人都被 serve 三年.好,那如果我们用fair wear 的情况下来看.就是两人合起来所要serve 的年数最少的话.似乎应该是在这个位置对不对? 加起来嘛,两个就加起来.就两年.一人一年,两人加起来.可是实际上呢, 依照Nash equilibrium来讲的话,这件事会发生.这不是平衡点.会发生是在这个位置. 原因是因为这样.你 A 会这样想,A ok 想要在这边.可是他会想说 如果我背叛他的话.我背叛 B 的话,我现在就马上出狱.因为他只 care 他自己的.而且他会, 正常 rational 的想法他会觉得,ok B 应该也会这样想,对不对?就是 B 应该也会想如果 这样的话他就可以free所以他应该也会马上背叛我.所以这样的话还不如我也背叛他. 所以最后结果就是你会发现从这个 column 到这个 column 基本上有这样的效果,就是,呃,这样. 这里到这里,然后在这个点会移到这里.在这个点会移到这边.所以基本上这不是一个,这边- 不是一个平衡点,而这边是最后的一个平衡点. 就两个人都被关三年.好,这是用 Nash equilibrium 来讨论,解释 囚犯两难困境.所以最后得到平衡点在这边.那如果在电脑赛局中有类似的情况下,有一些 uncertain state那基本上马上都跟赛局的研究有关.或是,呃,赛局,就是赛局里面有超过两个- 人以上. 比如说,三人以上.那基本上都跟赛局有关.因为你可能要在某一个时间点跟另外一个 player 合作来对抗第三个player. 那以上是我们这里讲的整体的内容.首先我们主要在探讨怎么.就包含alpha beta pruning. 那譬如说我们,这是一种非失真的,那我们也讲mega scout. Mega scout那基本上把alpha beta window缩到最小.那如果 search 的结果不行, 就是代表你可能有多坎.那,不安全的多坎,那我们可能就背叛这个 结果再 search 一次.那我们有介绍失真的方法,比如说你可以用beam search 你可以用probable count就机,用统计来算.你被砍的几率多少.那只要够高你干脆就直接把它砍掉. 那再大部分的电脑赛局里面你都不太可能 search 到最下面. 因为 时间的关系,那所以我们会用,用 heuristic 来做.那如果是对stochastic game 的话,那再整个search 过程你必须要增加一个 就chance node 那chance node 增加蛮惨的就是你 alpha beta pruning 会不太有效率. 而且整个树的 branch factor会长得非常的庞大.那比较常用的方法我们是用蒙立卡罗的simulat- ion. 来就是在够深的,你还是要search 到够深的,呃,搜寻的结果才有品质的保证. 那可是我不能没办法整个这么深的树全部搜寻完.我们用蒙立卡罗就是, 在我时间可以容许的范围random 地去挑我够大的数量来做平均,来做统计. 那如果针对limited,呃,就是你observation 没办法 对整个游戏有些地方你是看不到的.然后这些看不到的地方是 hold 在你的对手身上的 那这部分,呃,大部分研究都会跟 game theory 有关.那这部分相关的可能要看赛局的一些课程. 以上的是我们这一讲的内容.