能否設計口袋妖怪的必勝AI?
規則按照PO上面的OU來考慮 單打6v6 是否可以設計出一個人工智慧 可以擊敗所有的人類對手?
或者考慮到口袋妖怪的隨機性(比如連續六次一擊必殺命中) 是否可以設計出一個人工智慧 在與每一個人類選手的多次對戰後結果都能佔優?
按照慣例先上結論:
必勝AI,不可能。
對玩家佔優的AI,很可能。
(注意:本答所述情況,均是在不違反遊戲規則的情況下的,例如AI不會「後操作」、「窺伺」玩家隊伍、操縱隨機數等)
在二人的有限遊戲中,如果雙方皆擁有完全的資訊,並且運氣因素並不牽涉在遊戲中,那先行或後行者當一必有一方有必勝/必不敗的策略。
由此定理可知,象棋、圍棋、五子棋(無禁手)、井字棋等棋類,如果兩個「經濟人」進行遊戲,那麼遊戲的一開始結局就是確定了的。最優的策略一直存在,有些尚未被發現,例如象棋、圍棋;有些已經被發現,例如五子棋、井字棋。
但是顯然,口袋不滿足其中很重要的條件:完全消息、不涉及運氣。
策梅洛定理的逆定理並不成立,但是我們可以直觀地感受到:口袋不存在必勝策略。
很簡單,你用什麼隊伍,我也用什麼隊伍,請問哪方能必勝呢?
雖然口袋不滿足策梅洛定理的條件,但是有些思想方法我們依舊可以採用。
即:每一步都是有有限的操作方式,由根溯源終究能找到最初的解法。
只不過,由於運氣原因,收益不再是1和0,而是90%和10%而已。
1. 量化收益,找出最優行動。
2. 將各行動組合成混合策略均衡,行動多元化。
3. 針對對方的行動風格,預測對方行動並採取行動。
4. 具有聯想能力,根據對方以往風格,結合雲數據,綜合行動。
5. 具有大局觀,清晰預見局勢,有自己的戰術,預判對方戰術,找出雙方弱點。
6. 找出偏離計劃原因,及時修正計劃,隨機應變。
7. 掌握初步的心理學知識,善於利用對方心理,對簡單陷阱學會設計、破解。
8. 從實戰中總結經驗,結合經驗自行修復更新戰術與程序。
(為了理解方便,答主採用了擬人的手法,但是必須知道計算機的「思考方式」與人類有很大區別)
展開說一下吧:.
第一級AI僅僅需要做的是「找出當回合的最優操作」。例如我的雷精靈面對你的暴鯉龍,我選擇十萬,而非影球一樣。
第二級需要做的類似一個博弈論中的「警察與小偷博弈」。絕大多數的情況下,口袋對戰中的納什平衡不是帕里托最優,換言之,不存在單一策略均衡。AI需要做的是一個混合策略均衡。具體的答主曾經在貼吧發表過一個耿鬼與超夢的博弈問題,類似於那個。這樣AI的操作就不會均一化,而是若干幾率進行這個操作,若干幾率進行那個操作。
第三級需要做的是一個動態的改進。達成一、二級的AI可以說是操作非常穩健的一個AI,但是對於口袋對戰來說,僅僅穩健是不夠的。我們對戰時,誰也不會每回合都拿紙筆計算,即使我們有這個耐心,也沒有這個運算能力。我們總會對納什平衡略有偏移,這級AI需要做的就是找出這個偏移,從而佔據比納什平衡點更大的優勢。
第四級和第三級類似,只是不局限於當場戰鬥的操作風格,而是放眼於對面多場的風格。任何人對戰的風格在短期內都不會有很大改變的,有些人操作穩健,有些人則操作激進。第三級AI開局時都按照平衡進行,逐漸分析對面風格。而第四級AI則是結合雲數據,在與對方對戰開始時,就對對方的操作有一個「清晰的印象」了。
前四級AI完成之後,在計算方面AI已經會佔據很大優勢了。至於技術部分代碼的實現,並非多麼複雜的事情。
第五級是將計算機的思考方式更加「人格化」。達到此級的AI有「清晰的頭腦」和「敏銳的眼睛」,說的擬人化了點,其實不過是逐個比較自己和對方的PM、操作而已。
第六級是設計一個糾錯機制。防止AI一條路走到黑,不撞南牆不回頭。必須注意這裡的「隨機應變」不是人類的隨機應變,而是不斷重複第五級找出最優策略的方式。
第七級教給計算機一些「心機」。這看似異想天開,讓一個機器學習心理學,這豈不是開玩笑?然而,其實很多心理學的陷阱也有一些規律可循。舉個簡單的例子,點球大戰中你是守門員,對方連續往左邊踢了兩次點球,第三個點球你通常會往哪邊撲呢?確實會有一些隊伍喜歡不斷往一個方向踢,但是對於大多數情況,尤其是一些新手隊伍來說,無疑往右撲會收益更大一些。這是比較簡單的陷阱,還有一些更加複雜的,在此不再贅述。
第八級是學習功能。AI的學習一直是一個世界級難題,在此不談。
後四級AI是將其「人格化」。
AI比起人類的優勢在哪?運算能力強,有大量數據可以運用。
AI比起人類的弱勢在哪?缺乏大局觀,操作單一,墨守成規。
後四級AI就是用來彌補(注意不是消除)其弱勢。
此部分的代碼無疑會非常複雜,保守估計在答主的有生之年是難以看到的。
但是本答只討論戰略問題,不討論戰術問題。
一個高級的AI與人類對戰,會有一個不合常識的結論:
AI對新手勝率較低,對老手勝率反而較高。
新手的操作更為「感情化」,而且沒有大量的數據可供分析,就像世界盃上常常會出現一些黑馬一樣,很少被研究過,結果打了對面一個措手不及。
老手的操作則更為「理性化」,與計算機的分析有異曲同工之處,而人類想與計算機比拼計算?或許只有馮·諾依曼這樣的天才在那個時代才可能獲勝吧。
因此,一個高級的AI與一個人對戰,很可能的情況是剛開始時AI的勝率並不突出,隨著與這個人的對戰次數越來越多,它的勝率也越來越高。當然不可能達到100%,但是保守估計的話,80%還是有的。
說了這麼多,或許很多人會覺得這是「一本正經地胡說八道」。
PM的AI複雜度,會大大超過圍棋。目前來說圍棋的AI也僅僅是取得了突破性進展,並未達到完勝的程度,沒有資金支持的PMAI就更不用說了,答主覺得有生之年是看不到的。
但是科技的發展是越來越快的,我們現在十分接近於科技的爆發點,誰也不能預知未來十年、二十年會有多麼翻天覆地的變化。
況且,思考思考總是好的,萬一,它就實現了呢?
——————————————————————————————
上面主要是關於「實現方法」的問題,再補充一下關於「可行性」的問題(感謝 @許AB 的建議)。
口袋比起圍棋、象棋等棋類來說,RP因素佔據比例會大很多。
但是在分析時,我們只要取【期望值】即可。
答主曾經在貼吧的一篇文章中分析過一個簡單的耿鬼超夢博弈情景:耿鬼與X夢的博弈問題
其它的情況,不過是操作更多,情況更加複雜,但是本質是一樣的。
而此種情況,我方的策略可以推導出公式直接計算(勝率對於對方操作概率的偏導數為0),只要帶入數據即可得到結果。
人類可以,計算機也可以。
比較麻煩的是估值函數。
一個科學的口袋估值函數,需要大量的經驗支撐,這也就需要很多口袋玩家的共同努力。
當然,如果某天計算機能夠算到八百甚至一千回合以上,估值函數就幾乎不再需要了(很少有對戰能夠達到如此長度)。但是以現在的情況來說,等到這樣的計算機出現,比研究出估值函數,時間要長得多吧。
如果計算機技術發展到一定程度之後,理論上口袋AI是行得通的。
終於找到自己比較適合回答的話題了。
作為玩了10幾年口袋妖怪,一直以筆紙計算器同圈子內的幾個人堅持著玩口袋妖怪,對於PM的數值問題我是很敏感的,現在在讀計算機專業,假期在做一些粗淺的機器學習的項目,我想我應該比樓上幾位有資格回答這個問題= = 不知道我那幾個一起玩的朋友上不上知乎,過兩天問問邀請過來回答。
首先說,就目前的演算法和口袋妖怪的複雜度以及硬體能力,設計必勝的AI是不可能的,但是我們理論上是可以做具有高勝率的AI的。
先說口袋妖怪,後說機器學習的最基本概念。
1.口袋妖怪中什麼是贏?在我們熟悉的6V6的情況下,最根本的就是打倒對方6個PM為贏。那麼我們怎麼判斷什麼是正樣本,什麼是負樣本?也就是每一步中我們怎麼判定這一步走得好或者走的不好?這個是很難說的,層次不同對局面的把握也不同,對於每一步的用意看的深度也不同。比方說,我用龍舞強化策略,前期有1~2隻PM清了場,控制了天氣,放了釘子,並逼對面換人為我方的龍系PM佔據先機,但這兩隻PM死掉了,那我們說這個是盈還是虧呢?這一點不搞清,那麼普通的BP類神經網路(後面會粗淺談談)是根本沒法應用的。
2.口袋妖怪的複雜度。我們說為什麼圍棋AI那麼難開發?一個是它的盈虧情況不好做一個簡單的判斷,另一個就是其高的嚇人的可能性(貌似是1e360?不懂圍棋)。那麼我們說口袋妖怪的複雜度到底有多高?第一點,選取6隻PM,從721隻Pm中,那麼假設是隨機選取,結果是1.9108e+14。第二點,我們的Pm在場上時,我們所做的動作,可以有四個招式和換人,那麼假設沒有PM陣亡,就有9種情況,設一局我方做80步控制,那麼有9^80種操作情況。第三點,我們的PM的個體值和努力值如何分配。這是一個整數的離散問題,如果真的細分到每種情況,那麼我們就不用往下考慮了,到此口袋妖怪的複雜性就已經足夠了。但讓我們再做假設,我們只出現極限XX滿XX的情況,那麼在努力值上有720種分配方案。個體值默認全31或者類似小小龍戰術全0(不細算)。第四點,相互克制與互不相剋問題,涉及問題太多,無法做出簡單又不脫離實際的簡化。我做了一下大致推算,如果把努力和個體數值嚴格求解,在目前的假設下最終總的複雜度大約是1e116以上,自行對照下表,感受一下難度。順便說,你可以把這個量級和阿伏伽德羅常數比比,你想像一下。
下面是一位知乎用戶提供的圖表,侵刪
3.口袋妖怪的不確定性
這個問題是很有意思的。不確定性在哪裡?首先,如果你常常手動計算口袋妖怪的傷害問題,那麼你一定了解口袋妖怪傷害公式中的0.85到1的隨機數問題,這也誕生了口袋妖怪的一個量化參數,即秒殺概率問題,相信我,在網上還不流行傷害公式的時候我們在初二就在研究這個問題,我現在大二了都= = 扯遠了,第二點,招式自帶隨機問題,就像1GB這種問題,完全是臉黑不黑的問題,你這次瞎貓碰死耗子1GB成功了,將這個樣本給AI做學習訓練的時候,它由於發現這個東西很「厲害」,會把網路中的權值在很大程度上偏向於選擇1GB,而這在我們資深玩家眼裡看來是完全不應該的。第三點,PM自帶道具的概率問題。我就不多說我在戰鬥工廠內連續五次被對面的同一個頭巾防住(1e-5概率)。第四點,會心一擊= = 第五點,異常狀態持續時間問題,如冰凍和睡眠。
不論你是否贊成我前兩點,那麼第三點這個隨機問題會成為「必勝」的絕對否定,無論你有多好的戰術,如果對面臉就是好,那你就是沒有必勝的能力。
本來想談關於神經網路的入門知識的,後來想想不配圖很難讓人理解,找那麼多圖又不如讓人自己去Wiki或者百度。在你大概了解機器學習的方法後看我下面的話。
假如你使用BP神經網路,你根本無法得到一個優秀的特徵向量作為輸入,這是口袋妖怪作為一個極為複雜的對戰策略遊戲決定的,前文說過,你沒有一個很好的判定步驟優劣的方法,那你想要得出一個標準模型去讓演算法學習,這是不可能的。同理,SVM,嶺回歸之流一個道理
假如你說,你看看谷歌人家的圍棋也沒有好方法,那人家咋做出來了。這是他們的演算法會自動選取特徵而不需要人來提供,相當於只要給棋譜就能學,這樣,據說谷歌拿了3000W盤棋交給機器學。那麼我們說我們的口袋妖怪有這麼多學習樣本給機器嗎?我想應該沒有。而且隨著口袋妖怪的PM數量不斷增加,係數也越來越多,相當於你在教給AI一個不斷變化規則的圍棋,這樣的情況下,訓練網路的代價函數可能永遠都不會收斂,或者說它的代價函數始終隨著你的樣本數量增加而不斷「跳躍」,達不到你要的效果。我知道有人看不懂上面的一段話,翻譯成口袋妖怪的術語就是:當暴鯉龍流行(強勢期)時,一大批地面系的PM的選擇就需要多加思考很多PM的覺醒力量還要帶個電屬性,那麼班吉拉強勢的時候,大家又對脆皮的衣帶要改變玩法。
所以,你們這樣變來變去的玩法讓計算機很迷茫知道嗎!?
以上是分別從多方面簡化的口袋妖怪的模型和粗淺的機器學習概念,解釋為什麼設計一個口袋妖怪的必勝AI是不可行的。我還說過設計一個較高勝率的AI是可行的,請參考某些棋類和爐石傳說的AI,他們在某些方面是與口袋妖怪類似的,在此不再贅述。2月4日增加一些估算
簡化條件估算平均複雜程度的下限
雙方明牌(技能已知)
通過調整對應參數很容易將結果上下調整e10,這裡給出具體過程,有興趣可以按照自己標準估算。
6v6
選出36種。40回合。前20每回合9種操作,後20每回合7種。場上2隻。
36*(9^2)^20*(7^2)^20→e70
64double
選出8100種。單體技能要選擇目標(不考慮同伴是兩種選擇),aoe及場地類,幫手,保護等不用選擇目標,就技能而言平均會有6到7種選擇(兩單體至三單體),場下有精靈可以上場,按8種算。計10回合
8100*(8^4)^10→e40
64輪盤
選出32400種。不考慮場下精靈了。聚聚說精靈特別難死。就認為兩方場上都是三隻精靈。計30回合。
32400*(12^2)^30→e70
66三打
選出14400。相比雙打技能打擊對象更多,波動類,飛行類,中間的精靈可以打擊到全場,換人更靈活。操作變多。計8回合
1400*(10^4*12^2)^8→e55
===========================================
2月3日編輯完了
以下說明可能為了舉例的方便會各種模式夾雜著說,還請諒解。
個人不懂某些地方的具體實現,所以以下有口胡請輕噴。
以下腦補部分也很多,有哪些地方有疏漏還請指出。
按照題主的問題,
這是一個上分ai!
這是一個上分ai!
這是一個上分ai!
重要的話說三遍。
先看比較傳統的方式
首先拋出一個問題。如果你的信息對ai來講是完全透明的,也就是說,ai知道你隊伍的完全信息,在你出手後ai才出手(即ai作弊),但隨機因素ai也不清楚,如沸水燒傷。那麼ai是否有必勝策略?
這個問題仁者見仁智者見智,我的意見是,在ai有一個不錯的隊伍時,ai是很有可能可以做到必勝的。
類似棋類遊戲,下面是一個可行的方法。
不妨考慮這樣一個估值函數,它可以衡量場面好壞,值越高即場面越好。在信息完全透明的情況下考慮這樣一些因素:己方對面場上精靈能力等級與血量異常狀態,不同精靈的重要程度,是否存在難以突破精靈,是否存在壓制己方的精靈,速度線,場地,空間順風,場下精靈etc(口袋是細節非常多的遊戲,這個函數必定十分複雜,但我相信這個函數有辦法找到)。以我的經驗這個函數應該有這樣的特點:當局面膠著或局面不清時函數值會在某個範圍內波動,當場面出現大變化,如:某隻精靈變得難以突破、某隻精靈可以貫穿全隊等等,函數值會突變。
這裡插一句,單只精靈的狀態在大部分情況下是沒有意義的,精靈之間的關係才是有意義的。這點很重要。
那麼在對己方所有可能操作遍歷之後每個局面都會有一個估值,找出對己方最有利的局面,選擇它。(但每個操作最後局面可能不穩定,如燒傷冰凍ct等,所以還是需要用概率來修正)
再作進一步假設:假設對面隊伍信息仍然是完全已知的,但是我們不知道對面操作,那麼該怎樣作改進?
搜索深度加深。對面有心機了,如可能會用暫時的犧牲換取後續的強化,或者兌掉某隻難以處理的精靈,加大搜索深度便能想辦法「識破」這些情況。就6v6而言,適當的剪枝是很容易的,我們可以把深度加深到「任何口袋的戰術都會被識破」的深度。一般而言6v6戰鬥某個小戰術需要四回合以上來施放就很困難了,當我們不斷加深深度時,程序會表現得「具有大局觀」。
選擇隨機化。怎樣猜拳佔優,比如圍巾地鼠對上忍蛙,地鼠地震能打死忍蛙,忍蛙場下有一隻飛機,這時需要猜拳。根據環境,查一下有關猜拳的論文可以想辦法在大量數據下佔優。(而且可以根據對手分段決定怎麼操作)
再進一步,在我們只知道對面隊伍以及環境數據時怎麼辦?
看看哪些變數變得未知:精靈信息。
但也只是相對未知。還記得我說什麼嗎,這是一個上分ai,當我們了解環境,看到一隻精靈心裡有數,看到耿鬼會考慮替身束縛鬼火同旅滅亡歌影球滅歌而不會認為會使用舌舔,當你試探出一部分信息,比如對面放了替身,你會發現這隻耿鬼是很可能沒有滅歌的,同時你會小心束縛。也就是說:利用已有的信息(初始信息就是環境數據)縮小未知信息的範圍,並利用新信息(對面使用過的技能、對面的操作etc)不斷修正未知信息。
不過,精靈信息未知,估值函數怎樣處理?這裡我們不妨回憶一下我們自己是怎麼處理的。當你看到對面隊伍里有一隻噴,Y噴你的地龍能中轉,X噴你的河馬也能中轉,那你是怎樣處理的?
除非對面隊伍/操作明確表現出這是一隻y(如隊伍妙蛙火鋼椰蛋樹噴etc)(這點可以通過環境數據來確定是y的概率),否則當作最壞情況來打算。
具體是什麼意思?記得剛剛說了什麼嗎,「精靈之間的關係才有意義」,也就是說,考慮噴和地龍之間的關係時把它當作X,考慮和河馬關係時把它當作Y,(這個例子可能不太好),這樣,你可能會用其他的精靈來中轉。也就是說,自然而然的,ai會表現的像在「試探」。
機器學習看到有專業的答題了。我就不口胡了。@五德。
最後說一句,以上都是我腦補的,我盡量讓它看上去每一步都沒那麼困難。==
1.不能
原因眾所周知
而且不難
不可能。能保持70%的勝率就不錯了,何況人類玩家保持這樣的勝率並不難。
在口袋妖怪對戰領域人工智慧並沒有什麼卵用。首先它要有一個隊伍,有了隊伍就有弱點,沒有一個隊伍是完美的。還有運氣因素的存在,假設這個ai是1600的水平,遇到1200水平的歐洲狂魔也會束手無策。氣合彈miss,鬼火miss,暴風miss,人家三角攻擊凍你一隻,燒你兩隻,麻痹你三隻,你還怎麼玩?
扯開運氣不談,寶可夢對戰還有很多生死先讀的情況。栗子:雙方都只剩下最後一隻精靈,一隻極攻氣腰斗笠菇(只剩一滴血)和一隻極速鋼兵(鋼兵和袋鼠速度種族值一樣,所以鋼兵快),這時候就要猜拳。斗笠菇面前有兩種選擇:音速拳和蘑菇孢子。鋼兵的選擇是偷襲或者鐵頭。如果袋鼠點音速拳而鋼兵點偷襲,鋼兵勝利;袋鼠點音速拳而鋼兵點鐵頭,袋鼠勝利;袋鼠點蘑菇孢子而鋼兵點鐵頭,鋼兵勝利;袋鼠點蘑菇孢子而鋼兵點偷襲,袋鼠勝利。這時雙方都有50%的贏面,人工智慧可以保證每一次都讀中嗎?不能。什麼?你想統計聚聚們對戰遇到生死讀時的選擇?很抱歉,這個就算統計出來了也沒什麼卵用,而且會十分接近50%。因為就算同一個人,在面對生死讀的時候都要思慮再三。
就算不是生死讀,中低手的亂讀也能讓ai痛不欲生。例子就不舉了。相信在座的各位都有被新手瞎jb讀讀死的情況╰( ̄▽ ̄)╭
以上。
實機的AI真的讓我感覺是偷窺操作+操控隨機數
隨機性太強了……強行讓非洲人勝歐洲人是行不通的……
戰鬥塔的ai……6次先至爪1GB,嗯,理論上來說現在還沒有冰免疫,所以絕零是可行的,為了破堅硬和氣腰,再有一個永遠發動的氣息頭巾精靈配燕返。講道理,歐皇用什麼隊都能贏
可以。
第一,技能的隨機性(例如miss、暴擊等)在單純一局中可以主導局面,但是並不阻止在長期中佔據優勢。Zermelo"s Theorem可以應用到有隨機性的遊戲中,此時只需要把結論中的」必勝/必不敗」改成「期望值大於等於某值」就可以了。因此,這個隨機性並不構成原則上的障礙。
第二,上面有回答有提到了混合策略納什均衡和例子。這裡舉個最簡短的石頭剪子布例子
例子:
雙方均只剩一隻PM,一方為半血耿鬼,還剩兩招影子球/替身;另一方為1血爆了氣腰的鋼兵,兩招偷襲/打落,pp足夠多。
羅列結論:
偷襲 打落
影子球 鋼兵勝 耿鬼勝
替身 耿鬼勝 鋼兵勝
這時局面屬於典型石頭剪子布,無必勝策略。
此時,只需隨機出招,即可將本方勝率保持在50%。因此不存在在一種必勝或者能保證取得優勢的演算法。
然而,我們已知,石頭剪子布的AI演算法(可以使用很多方案)是可以利用人類並不是真隨機這個弱點取得長期優勢的。因此在這裡AI仍然能佔據優勢。
綜上兩點,設計出佔有優勢的AI是可行的。
論實踐的話,分兩步。
第一步組隊,遍歷所有可能進行組隊的複雜度大約是 (700PM * 1000種配招 * 3種特性 * 25種性格 * 31^6種個體值 * 30^6種努力值)^6 = 10^153,完全不可接受。但是這可以通過對已有對戰數據進行採集+貪心演算法迅速減少,實際上必須要考慮的配置也不過2000^6 = 6*10^19。由於隊員之間的耦合其實很鬆散,最終搜索也就是2000*6的幾倍而已。然而這個搜索依賴於對「固定隊伍對戰」搜索的結果作為參考。
第二步是對戰。答主對此進行過實踐,其中對於答主這樣的業餘人士的最大的困難是:口袋對戰每生成一個新狀態很慢,比國際象棋和圍棋之類慢的多:因為隨便什麼動作都要包含大量判斷,例如一個攻擊動作需要考慮幾十種特性,天氣,XX,XX和XX等等,而且很多動作還有歷史效應(節拍器),答主自己寫的AI實際計算中產生一個新狀態耗時高達1毫秒。OK,如果用窮舉法,雙方玩家每人各有4種可能行動+5個換人操作,那麼一回合就是81個狀態,兩步有6561個狀態。OK,暴力窮舉兩回合(還沒窮舉完)就要6.6秒,第三回合就爆炸了不具有實用性。就算提速100倍(因為渣代碼速度很慢)也只能窮舉三回合而已。
算上很多幾率技能會有很多額外的狀態還要加數倍(至少每個攻擊技能都有miss/命中/CT三個狀態),也就是一回合可以產生(4*3+5)^2=289個狀態,就比上面更慢了。
這是我的夢想 匿了 十年後一定答
這個問題得sidwjjjj把妹和CS都大成後才能回答
先讀ct這種東西我估計還是有難度
匿了
除非是歐洲AI,技能效果每次必發動,否則基本沒有可能。
這個智能該是歐洲還是非洲呢?
當然不能因為你永遠也不可能打敗sidwjjjj。畢王。
推薦閱讀:
※算命能算出人工智慧的未來嗎?
※華為Mate10 AI有哪些特性?
※如何看待魯大師初次公布的手機AI「智商榜」?
※如新是不是傳銷?
※現在人工智慧教育機器人市場怎麼樣?有多大的盈利空間?
TAG:人工智慧 | 演算法 | 編程 | 博弈論 | 精靈寶可夢Pokémon |