隨機演算之美

語言的標準程式庫中都有隨機函式，可用來作為無法預測的輸入，或者是創造另一種隨機，而能夠處理隨機的演算法具有啟發性與實用性，也突顯了運算的本質。

遊戲中的隨機

遊戲中經常運用隨機來增加變化性，雖然初學程式的新手也能運用隨機建立猜數字遊戲，只不過這類隨機處理過於簡單，未經任何處理，只有建立在某種規律下的隨機性，才能說是變化，例如，勇者拿劍砍某怪會造成某程度的傷害，像是一百點左右的生命值，計算基準可能包含了雙方等級、武器等，而「左右」則是加上某種隨機值作為權重進行計算得來。

有些遊戲可以產生隨機地圖，像是Minecraft的隨機世界，不過地圖看來是隨機，然而若方塊之間沒有任何關聯性，只會得到一堆亂七八槽的方塊，絕不會像是自然地形。此類地圖需要的類似自然界的隨機，而不是全然的隨機，而關於這種應用的隨機演算中，常見的是Perlin噪聲（Perlin noise）。例如，一般的自然地形，在鄰近兩點間的起伏，會具有關聯而感覺有連續性，而以二維的Perlin噪聲來說，其作法是方格的頂點產生隨機值以求得四個梯度，方格內的點噪值不是隨機產生，而是固定依這四個梯度採內插法得到，簡單來說，頂點的梯度是隨機，然而方格內的點噪值具有規律。

遊戲中也常見隨機迷宮之類的元素，迷宮牆不會是完全地隨機產生，否則這迷宮怎麼能走？如果將一個迷宮展開，會發現是棵樹（參考〈In every maze there's a forest〉），也就是說，迷宮的牆本質上是樹枝構成，雖然可以隨機產生分支，然而還是必須從樹衍生出來，有興趣研究迷宮的話，可以參考先前專欄〈迷宮產生演算法之美妙〉。

如果給定任意的n行m列的網格，該如何不重複地走過每個網格呢？這個問題的解是一種哈密頓路徑（Hamiltonian path），問題不會只有一個解，如果想要隨機的解，可以沿著隨機迷宮的牆，畫出輪廓來得到哈密頓路徑，若想在遊戲中運用這種路徑，也許是用來產生隨機路線的溜滑梯或道路之類的作法（參考〈Random scala〉）。

自然界的隨機

Perlin噪聲模仿了自然界的隨機，這意味著，自然界並非全然的隨機，看似隨機的事物，其實彼此有著某些規律，例如長頸鹿的斑紋、蜻蜓翅膀的紋路、葉片的細胞壁等，其空間分割看似混亂，然而又具有某種規律。

俄國數學家Georgy Voronoy建立的Voronoi空間分割，可以模擬這類自然的圖案，這類圖案中的點是隨機散布的，然而每個細胞壁只包含一個點，而相鄰細胞壁中的點，彼此之間必然等距，換個角度看，細胞壁達成了相鄰點間的勢力均衡，我們可以想像，生物的細胞在各處成長速度不同，然而最終會彼此擠壓，達到勢力均衡狀態而形成之圖形。

而Voronoi空間分割演算法出發點，就是基於勢力均衡，最簡單的方式之一是，各點對某點建立正多邊形，將多邊形的一邊推至兩點間等距之處，而這一堆多邊形的交集結果，就會是該點的細胞勢力範圍，不過，這個方式需要大量的交集，導致求得Voronoi分割的速度會變得十分緩慢。

另一個方式是建立Delaunay三角網，在空間中隨意散布多點，Delaunay三角網會將這些點彼此連接成三角形，然而某三角形構成的外接圓，絕不會包含另一個三角形，Delaunay三角網中，若將邊相鄰的三角形之外接圓心連結起來，就會構成Voronoi空間分割。

這是因為三角形邊長，其實就是兩個外接圓的中垂線，將相鄰三角形構成的外接圓心連結起來，必然均分三角形邊長的兩頂點構成之線段，因此外接圓心連結的線，就是勢力均衡線，也就是細胞壁了，這個方式不需多邊形交集運算，只需要計算點，而求得Voronoi分割的速度也會快很多。

隨機演算法

自然界雖有許多現象看來隨機，然而實際上沒有真正的隨機，必然有其規律在其中，只是自然界資訊過於龐大，當人們無法從中釐出規律、有效地解釋這些形象之前，只能先歸類為隨機，正因如此，愛因斯坦才會有句名言「上帝不擲骰子」。

在演算法上，就有一類隨機演算法，會在演算過程中套用某種程度的隨機，因此在輸入相同的情況下，可能會有不同的結果，而這類演算法的目的，並不是為了創造變化性，而是想求得運算結果在可以接受的範圍。

蒙地卡羅（Monte Carlo）演算可能是開發者熟悉的隨機演算法之一，例如用來求圓周率的方式，是在方形區域內隨機散布一定數量的點，看看落在圓內的有多少，套用公式來計算圓周率，點的數量越高，就越接近圓周率。

為什麼會想要求得一個接近的值，而不是確定的值呢？有些需求可能無最佳解，或者需要耗費大量運算才能得到理想的解答，在耗費時間遠大於對品質的考量下，若隨機演算法可以快速求得某個可接受的結果，我們就可能採取這類演算。

在圍棋上贏得人機之戰的AlphaGo，採用的決策過程之一，就有蒙特卡羅樹搜尋（Monte Carlo Tree Search，MCTS），而MCTS存在目的是為了解決搜尋空間過於巨大，難以窮舉全部子樹的問題，MCTS子節點展開後隨機進行遊戲，根據勝負結果來更新沿路至根節點的資訊，作為下次搜尋選取節點的評估之用。

關於隨機的運用，在程式設計中是族繁不及備載，然而可以從運算的本質來探討。

開發者如果接觸過運算原理，都會知道模型中有種非確定性（Nondeterministic）自動機，這類機器具有隨機性，而且天生神力，總是可以猜中接下來不用讀取任何輸入，就直接轉移至可獲解答的狀態。例如，確定性下推自動機（Deterministic Pushdown Automaton，DPDA）並無法判斷迴文；然而，非確定性下推自動機（Nondeterministic Pushdown Automaton）卻可以完成任務，這是因為，它總是能恰巧猜中輸入已經達一半的時機，接下來就開始比對堆疊中的值是否與接下來輸入都是對應的。

瞎猜的神機哪來的？

每次都準確猜中的「神機」是不存在的，就演算法而言絕對無法設計出來，然而，若能接受運氣不好而沒猜中的情況，至少還有能回答「這是迴文」以及「這可能不是迴文」。

雖然現實中打造不出神機，然而，非確定性就像是一種外部參與，例如人類的介入（肉眼看看輸入是否達一半），現實中就有許多程式，一開始會需要人的參與，然而在相關理論或技術進步之後，外部參與就減少了（也就是減少非確定性），在這之前，若某個外部參與可以解決問題，就算是瞎猜（隨機），也會是可行的方向。

非確定性的有限狀態機或下推機，會有等價的確定性機器，只不過狀態通常會暴增，或者難以找出等價的模型，就像是還沒找出自然界中某種規律，只能看似隨機；特意地運用這類隨機，或者持續尋找當中的規律，能獲得許多的啟發，找出更多的實用性，也更能認識運算的本質。