Re: [請益] 關於一些遊戲的AI

看板GameDesign作者ddavid (謊言接線生)時間11年前 (2012/11/29 15:27)推噓2(2推 0噓 19→)

留言21則, 4人參與討論串6/22 (看更多)

: 推 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)

推

cowbaying

11/29 15:47, , 1^F

11/29 15:47, 1^F

→

cowbaying

11/29 15:47, , 2^F

11/29 15:47, 2^F

→

ddavid

11/29 15:51, , 3^F

11/29 15:51, 3^F