: 推 LayerZ:我觉得可以拿LoL的AI来讨论，跟SLG比起来相对简单(只需要操 11/29 11:15 : → LayerZ:做一个单位) 但是光是前方一个敌人走进草丛要不要追击 11/29 11:16 : → LayerZ:可能就要算整场的概念了.. 11/29 11:16 针对这个，我简单的做一下问题的分类： 1. 资讯完全公开的游戏（象棋、围棋、无任何乱数及战争迷雾的回合制SLG） 这类问题的特性是，只要双方做完全一样的事情，就100%可以重现完全相同的结 果。此类问题在不考虑运算量的情况下，穷举法一定会得到最佳解，且穷举完的情况 下，我们一定可以得到先手胜、先手负或和定之类的解。也就是说，完全不需要人为 的额外知识（如围棋的厚势）就能理论上解决。 在运算不完的情况下，人为知识主要都是用於减少运算量。在确保该加入的人为 知识正确的情况下（如，井字棋先手下中间，或象棋某些确定的已解决残局），仍然 一定可以得到最佳解并减少运算量。但在无法保证该人为知识正确的情况下（如，围 棋的厚势概念、围棋的定石），算出来的结果就无法保证为最佳解。举例来说，深蓝 下赢西洋棋王只是证明了西洋棋王在该次赛事中计算此问题输给了深蓝，而不是深蓝 解决了西洋棋问题。注意这里的「人为知识正确」的意义是当使用了这个知识做决策 时，在任何一个盘面或状况的胜负关系都不能被改变，这是很严格的一个限制。 顺带一提，有些无战争迷雾的回合制RSLG升级时会有乱数跳点，或者伤害有乱数 。这会导致这些游戏中进行同一个动作会带来不同结果，导致它们不能分到此类之下 。 2. 资讯非完全公开的游戏（猜拳、桥牌、麻将、德州扑克、任何有随机性的游戏、 RTS） 与前者相反，这类问题的特性就是任一方在所知完全相同的情况下做相同的事情 ，并不一定能得到完全同样的结果。这类问题「一般来说」是穷举法无法直接得到最 佳解的，因为你无法绝对计算你的决策带来的结果。以猜拳为例，在你要决定出什麽 拳时你无法得知你的对手要出什麽拳，因此无法计算出什麽拳必胜。RTS游戏就算没 有战争迷雾，但在你下任何指令时你无法知道对方同时会下什麽指令，你也不知道对 方会不会忽然手软没操作好，因而无法计算出绝对的结果。 但在一个非常严格的条件之下，这类问题有可能用穷举解决，也就是这些未公开 资讯在任何的盘面／情况下绝对不影响最终胜负结果。在这样的前提之下，这类游戏 可以用穷举解决。举例来说，有这样的一个猜拳游戏跟原本规则基本上一样，然後猜 三次采用积分制，赢一拳的可以拿到1分，但是其中A这方多了一种拳是比中指。中指 对上剪刀可以赢2分，对上石头可以赢1分，对上布可以赢5分。对於A来说，他永远无 法在出拳时得知对方想出什麽拳，所以也绝对无法推算最後自己会赢或输几分，可是 他只要一直比中指就会一直赢分数，就算无法得知最後自己赢了几分（分数上没有重 现性），可是最後终归会赢（在最後的输赢上有重现性）。所以在这样的前提下，用 穷举可以找出绝对最佳决策。 在不存在上一段的前提之下，最佳解就无法穷举出来，所以就必须引入一些假设 来辅助。其中，最常使用的就是「机率／期望值最佳 = 最佳决策」之假设。桥牌比 赛中，庄家看不到防家双方的牌，因此在只知道对方加起来张数的情况下，若无法得 到可以兼顾处理各种分配的决策下，往往会采用最高机率的分配来做为决策，来取得 「最可能」赢的打法。比如3张有以下两种分配，分别是2-1 78%、3-0 22%，无法兼 顾的情况下就比较可能以对方是2-1分配的情况来下决策。当然，从叫牌、对手习惯 等等可以做出某些更高机率的猜测，这些就是更多的假设。 而事实上，在第一种分类中的游戏因为复杂度而无法被穷举的情况下，我们就会 同样采用引入假设的方式来以可能的错误换取运算量的减少，但切记这跟第二类游戏 中引用假设虽在做法上可能相似，可是意义上不同。 第一类：你知道它一定能重现，可是你算不完，不知道重现了这一步是好是坏，只好 用假设来猜它的好坏。 第二类：你不能重现它，因此你只好靠假设来装做它是可以重现的问题，然後用解决 第一类问题的穷举方法来解。 回到LayerZ提到的LoL AI是属於第二类，你靠各种假设来猜用脸探草丛有多少机 率对面有人在里面，如果有人那你会被对面造成多少伤害、如果没人你有什麽利益， 这些利益又该怎麽评估，靠这样来装成它是第一类问题，然後就加加乘乘算出各种不 同决策的期望值，选期望值最大的行动来做。但是你又会发现就算这样装成它是第一 类，好像选择还是可能会多到算不完（指向技我有超多的角度可以发，Flash我有超 多的位置可以移），所以在用假设把它从第二类问题降成第一类问题後，你又还要用 更多的假设把它从第一类中算不完的问题降成算得完的问题（我假设指向技一定要指 着一个敌方目标打才有意义，我假设想逃跑时Flash一定要放离对方最远的点或能跳 过墙才最好逃，以此来减少选择的量）。更多不保证是正确的假设，就使得决策的品 质可能更差，但是让问题变得至少可以算出个解来。当然，大多数游戏的假设就是一 堆简单的经验法则写成的if-else，所以解的品质当然就好不到哪去了。 -- 「传说的最後，魔王总是被勇者封印。但勇者会逝去、封印会衰弱，魔王却永远 不灭。传说呢？传说持续着。只是，变质了。所以对於传说而言，只有反覆无常的自 己是主角，而魔王只是配角。勇者？勇者不过是消耗品罢了，封印则什麽也不是。你 好不容易有机会当上配角，怎麽走回头路想成为消耗品？你早晚会什麽也不是的。」 －－星．幻．梦的传说 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 114.32.156.172 ※ 编辑: ddavid 来自: 114.32.156.172 (11/29 15:33)