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

遊戲中的隨機

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

有些遊戲可以產生隨機地圖,像是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)卻可以完成任務,這是因為,它總是能恰巧猜中輸入已經達一半的時機,接下來就開始比對堆疊中的值是否與接下來輸入都是對應的。

瞎猜的神機哪來的?

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

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

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

作者簡介


Advertisement

更多 iThome相關內容