❶ 什麼是「隨機」教你分清「偽隨機」和「真隨機」
很久以前流傳著這樣一則笑話：一個身患重病的人決定去動手術。在手術之前，他問醫生：「這起手術的成功率是多少？」醫生回答他：「只有1%。」他很驚慌，但是醫生說：「沒事的，在你之前我已經治死過99個人了。」
這是一則嘲笑那些不懂「概率」的人的笑話，卻講出了「真隨機」和「偽隨機」之間的區別。
在四月末的時候，我曾寫過一篇 《你打 游戲 靠的是技術，還是運氣？》 ，其中就提及了「偽隨機」這個概念。當時受限於篇幅，沒有詳細展開解釋「偽隨機」的概念。前不久，在因國際邀請賽而備受關注的Dota2在最近一次的更新中，有這么一條更新內容： 「落空的負面效果和下坡攻擊的落空效果現在都採用偽隨機觸發」 。
那麼到底什麼是 「偽隨機」 呢？以及和「偽隨機」對應的 「真隨機」 又是什麼概念？
贗隨機數演算法（Pseudo-Random Number Generator，簡稱PRNG） 是計算機的一個術語——當然，它也可以被叫做「偽隨機數演算法」，只是為了方便與 游戲 中的「偽隨機數」進行區分，本文中統一稱作「贗隨機數演算法」。
眾所周知，計算機程序是由無數「0」和「1」兩種狀態構成的，如果一個狀態不是「0」，那就必定是「1」，頗有種非黑即白的味道。
因此，在計算機程序中，不存在「不確定」的數字，只有確定的「1」和「0」。基於這種特性，計算機無法生成「真正的（不確定的）隨機數」。
那麼在計算機中，需要生成或是使用到隨機數的時候怎麼辦呢？ 通常是利用計算機抓取一些數值，然後將這些數值輸入至一個復雜演算法 （常用的演算法是同餘法和梅森旋轉演算法，有興趣的讀者可以自行查詢，這里就不展開講了） 當中，通過一系列運算得出一個數字，這就是平常說的贗隨機數了。
只要最初輸入的數值（初值）不變，那麼輸出的值都會是同一個值，這就證明了這個數並不隨機，只是看起來隨機而已。
換句話說，只要這個隨機數是由確定演算法生成的，那就是贗隨機數。
所以下一次在和朋友聊天時提到真隨機數、偽隨機數時，如果有人插嘴：「計算機只能生成偽隨機數，所以根本沒有什麼真隨機」，那你就可以霸氣側漏地說他是 「雲玩家」 了。
我們通常說的 真隨機 又名 「純隨機」（True Random Distribution） ，就是我們平常一直說的那種、一般意義上的「隨機」。
在真隨機中， 每一個事件都是相互獨立、服從真隨機分布的，不受其他事件的發生而改變 。比方說某款 游戲 為了吸引用戶，擁有這么一個隨機抽卡系統：每次抽卡時，都有1%的幾率抽出SSR卡片，這個概率服從真隨機分布。
回到我們最開始說的那個「治死99個」的笑話：我們一眼就能看出這個笑話的不合理性。但在抽卡 游戲 中，我們的大腦瞬間失去理智。有相當一部分玩家認為： 我連抽100次，總能抽到這張卡吧！
實際上，連抽100次卻抽不出1%的SSR卡的幾率是為(1-0.01)^100=36.6%，甚至還稍稍超過了1/3。將連抽數字上升至300，也仍有4.9%的幾率。
換句話說，假設有10000個玩家連抽100次，就有約3660個玩家抽不出這張SSR；10000個玩家連抽300次，也仍有約490個玩家抽不出這張SSR ——這對玩家的 游戲 體驗來說可以說是毀滅性的打擊。
盡管純隨機在數學上是無罪的，在代碼中更是明明白白、清清楚楚，但玩家抽不出卡可不會回想到初高中的數學課本， 而是首先懷疑幾率是否被策劃運營篡改、這背後又是否有骯臟的PY交易……
當然不僅僅是在抽卡系統當中如此。在一些競技性比較強的 游戲 中（比如War3、Dota2之中——英雄聯盟幾乎完全摘除了隨機系統，不在此列），連續數次的「走運」極大影響 游戲 的競技性和觀賞性。
比方說Dota中最著名的概率英雄虛空假面的技能「回到過去」： 使虛空假面有25%幾率完全躲避一次傷害。 受限於War3引擎，這個技能採用的是真隨機概率，在某個極端情況下（通常見於精彩集錦中），虛空假面能夠保持很低的血量承受多次傷害卻不死、最終反殺對手。這種帶給敵方極差 游戲 體驗的系統，因此也進入了計師們「整治范圍」之中。
為了避免極差的 游戲 體驗帶來的玩家數量流失，設計者們提出了「偽隨機」的概念： 在不確定性的隨機事件當中，通過一系列演算法使隨機事件均勻分布在多次事件當中，盡可能減少或消除極端情況的發生，以提高玩家的 游戲 體驗。
在設計師們的努力下，「偽隨機」應運而生，這里的偽隨機就和上文的贗隨機數演算法（PRNG）意義不同了。
製造「偽隨機」的方法有很多，在War3、Dota2這類 游戲 當中普遍使用的是 「偽隨機分布」（Pseudo Random Distribution，簡稱PRD） 處理概率。
就拿Dota2中最強大的暴擊技能「恩賜解脫」來舉例： 幻影刺客有15%的幾率造成200%/325%/450%致命一擊傷害 。在PRD機制下，幻影刺客的攻擊實際上 並不是 每一刀都有15%的暴擊率。
根據PRD機制的公式P(N)=N*C可得出15%幾率的C值為3.22%，即幻影刺客的第一次攻擊暴擊概率為3.22%；如果第一刀沒有暴擊，則第二刀的暴擊率提升至2倍，即6.44%；如果仍舊沒有暴擊，則提升至3倍的9.66%，以此類推。
如果繼續推算，可得在第32刀時暴擊幾率會達到100%，最可能觸發暴擊的次數是第6刀，平均觸發刀數是6.67刀等等……
同樣，在連續觸發暴擊時，下一刀的暴擊幾率會減少。RPD機制使競技 游戲 中連續觸發或不觸發技能的幾率降低，避免了運氣成分過度干擾戰斗結果，大幅提升了玩家的 游戲 體驗，但不影響這些隨機事件的正反饋：TI6決賽的「打我五下暈三下」，可是令全球人民集體沸騰了呢！
除了偽隨機分布RPD之外，還有兩種常見的偽隨機： 洗牌演算法 和 組合隨機 。
洗牌演算法 最常見的用法，是在各大音樂播放器中的「隨機播放」之中。在隨機播放時，如果採用真隨機，會導致一首歌無論如何都播放不出，或是同一首歌連續播放數次（有興趣的讀者可以計算一下這些概率）。為了解決這個問題，播放器採用的解決方案即是洗牌演算法：將一個包含所有歌曲的數組像洗牌一樣打亂，然後依次播放這個亂序數組。
至於 組合隨機 ，這是一種廣泛應用於各個 游戲 的做法：在抽獎的時候進行兩次、或是更多次的判斷，一次不隨機，而剩下的判斷則是真隨機。比如說，你會在第X次抽卡時抽到SSR是確定的，但抽中的SSR具體是哪張卡，則是隨機的——這就是廣大手游中的「低保」系統了。
在一堆數據之中想要分清「真隨機」和「偽隨機」似乎並不是那麼容易。那麼接下來為大家介紹兩個例子，有助於更好理解什麼是「真隨機」和「偽隨機」：
真隨機 ：有一天，小明在的班級上舉辦了一次抽獎活動。這個班級有40個學生，所以為了公平起見，保證每個學生都有1/40的幾率中獎，老師准備了40個相同的紙盒，每個紙盒中都有40張紙條，有1張紙條是中獎紙條。這樣一來，每個學生都有1/40的幾率中獎，但每個學生是否中獎並不受其他學生的影響。在極端情況下，這個班上可能40個學生都能中獎。這就是真隨機。
偽隨機 ：小明班上舉辦了抽獎活動。為了公平起見，老師准備了1個紙盒，紙盒中有40張紙條，只有1張紙條是中獎紙條。這樣一來，每個學生都有1/40的幾率中獎——但是顯而易見，這個班上有且僅有一名學生能夠中獎。一名學生在中獎後，餘下的所有學生中獎幾率都會減少至0。這就是偽隨機。
❷ 棋類游戲的演算法有哪些
棋類游戲的演算法有哪些
棋類游戲通常包含三大要素：棋盤、棋子和游戲規則，其中游戲規則又包括勝負判定規則、落子的規則以及游戲的基本策略。下面我來給大家講講各類棋類游戲的演算法。
除了棋盤和棋子的建模，棋類游戲最重要的部分就是AI演算法的設計。目前棋類游戲的AI基本上就是帶啟發的搜索演算法，那麼常用的搜索演算法有哪些呢?
1. 博弈與博弈樹
博弈可以理解為有限參與者進行有限策略選擇的競爭性活動，比如下棋、打牌、競技、戰爭等。根據參與者種類和策略選擇的方式可以將博弈分成很多種，比如“二人零和、全信息、非偶然”博弈，也就是我們常說的零和博弈(Zero-sum Game)。所謂“零和”，就是有贏必有輸，不存在雙贏的結果。所謂“全信息”，是指參與博弈的雙方進行決策時能夠了解的信息是公開和透明的，不存在信息不對稱的情況。比如棋類游戲的棋盤和棋子狀態是公開的，下棋的雙方都可以看到當前所有棋子的位置，但是很多牌類游戲則不滿足全信息的條件，因為牌類游戲都不會公開自己手中的牌，也看不到對手手中的牌。所謂的“非偶然”，是指參與博弈的雙方的決策都是“理智”的行為，不存在失誤和碰運氣的情況。
在博弈過程中，任何一方都希望自己取得勝利，當某一方當前有多個行動方案可供選擇時，他總是挑選對自己最為有利同時對對方最為不利的那個行動方案。當然，博弈的另一方也會從多個行動方案中選擇一個對自己最有利的方案進行對抗。參與博弈的雙方在對抗或博弈的過程中會遇到各種狀態和移動(也可能是棋子落子)的選擇，博弈雙方交替選擇，每一次選擇都會產生一個新的棋局狀態。
假設兩個棋手(可能是兩個人，也可能是兩台計算機)MAX和MIN正在一個棋盤上進行博弈。當MAX做選擇時，主動權在MAX手中，MAX可以從多個可選決策方案中任選一個行動，一旦MAX選定某個行動方案後，主動權就轉移到了MIN手中。MIN也會有若干個可選決策方案，MIN可能會選擇任何一個方案行動，因此MAX必須對做好應對MIN的每一種選擇。如果把棋盤抽象為狀態，則MAX每選擇一個決策方案就會觸發產生一個新狀態，MIN也同樣，最終這些狀態就會形成一個狀態樹，這個附加了MAX和MIN的決策過程信息的狀態樹就是博弈樹(Game Tree)。
2. 極大極小值搜索演算法
極大極小值(Min-Max)搜索演算法是各種博弈樹搜索演算法中最基礎的搜索演算法。假如MAX和MIN兩個人在下棋，MAX會對所有自己可能的落子後產生的局面進行評估，選擇評估值最大的局面作為自己落子的選擇。這時候就該MIN落子，MIN當然也會選擇對自己最有利的局面，這就是雙方的博弈，即總是選擇最小化對手的'最大利益(令對手的最大利益最小化)的落子方法。作為一種博弈搜索演算法，極大極小值搜索演算法的名字就由此而來。
3. 負極大值搜索演算法
博弈樹的搜索是一個遞歸的過程，極大極小值演算法在遞歸搜索的過程中需要在每一步區分當前評估的是極大值節點還是極小值節點。1975年Knuth和Moore提出了一種消除MAX節點和MIN節點區別的簡化的極大極小值演算法，稱為負極大值演算法Negamax。該演算法的理論基礎是：
max(a,b) = -min(-a, -b)
簡單地將遞歸函數MiniMax()返回值取負再返回，就可以將所有的MIN 節點都轉化為MAX節點，對每個節點的搜索都嘗試讓節點值最大，這樣就將每一步遞歸搜索過程都統一起來。
4. “α-β”剪枝演算法
有很多資料將“α-β”剪枝演算法稱為“α-β”搜索演算法，實際上，它不是一種獨立的搜索演算法，而是一種嫁接在極大極小值演算法和負極大值演算法上的一種優化演算法。“α-β”剪枝演算法維護了一個搜索的極大極小值窗口：[α,β]。其中α表示在搜索進行到當前狀態時，博弈的MAX一方所追尋的最大值中最小的那個值(也就是MAX的最壞的情況)。在每一步的搜索中，如果MAX所獲得的極大值中最小的那個值比α大，則更新α值(用這個最小值代替α)，也就是提高α這個下限。
而β表示在搜索進行到當前狀態時，博弈的MIN一方的最小值中最大的那個值(也就是MIN的最壞的情況)。在每一步的搜索中，如果MIN所獲得的極小值中最大的那個值比β小，則更新β值(用這個最大值代替β)，也就是降低β這個上限。當某個節點的α≥β時，說明該節點的所有子節點的評估值既不會對MAX更有利，也不會對MIN更有利，也就是對MAX和MIN的選擇不會產生任何影響，因此就沒有必要再搜索這個節點及其所有子節點了。
5. 估值函數
對於很多啟發式搜索演算法，其“智力”的高低基本上是由估值函數(評估函數)所決定，棋類游戲的博弈樹搜索演算法也不例外。
估值函數的作用是把一個棋局量化成一個可直接比較的數字，這個數字在一定程度上能反映取勝的概率。棋局的量化需要考慮很多因素，量化結果是這些因素按照各種權重組合的結果。這些因素通常包括棋子的戰力(棋力)、雙方棋子佔領的空間、落子的機動性、威脅性(能吃掉對方的棋子)、形和勢等。
6. 置換表與哈希函數
置換表(transposition table)也是各種啟發式搜索演算法中常用的輔助演算法，它是一種以空間換時間的策略，使用置換表的目的就是提高搜索效率。一般情況下，置換表中的每一項代表者一個棋局中最好的落子方法，直接查找置換表獲得這個落子方法能避免耗時的重復搜索，這就是使用置換表能大幅提高搜索效率的原理。
使用置換表最大的問題是置換表的組織和查找的效率。一般來說，置換表越大，查找的命中率就越高。但這個關系不是絕對的，當置換表大小達到一定規模後，不僅不會再提高命中率，反而會因為耗時的查找操作影響演算法的效率。所以置換表不是越大越好，需要根據計算機的性能以及搜索的深度選擇一個合適的大小。此外，為了查找操作更高效，通常都會用可直接訪問的哈希表方式組織置換表，哈希函數的性能就成為影響置換表性能的重要因素。棋類游戲普遍採用Zobrist哈希演算法。