打則演算法

① 棋類游戲的演算法有哪些

棋類游戲的演算法有哪些

棋類游戲通常包含三大要素：棋盤、棋子和游戲規則，其中游戲規則又包括勝負判定規則、落子的規則以及游戲的基本策略。下面我來給大家講講各類棋類游戲的演算法。

除了棋盤和棋子的建模，棋類游戲最重要的部分就是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哈希演算法。

② 求問DND規則中的 攻防傷害公式演算法

1先攻檢定：1d20+屬性調整值（一般為敏捷）+其他調整值（如專長、環境、士氣等）來確定攻擊順序。
2攻擊/命中檢定：攻方為1d20+基本攻擊加值+屬性調整值（一般為敏捷/力量）+體型調整值+其他調整值vs防守方的ac=10+防具調整值（盔甲+盾牌）+屬性調整值（一般為敏捷）+體型調整值+其他調整值。如果攻方大於守方ac則命中，反之，未命中。
3傷害投骰：如果命中，傷害=武器傷害（如長劍1d8）+屬性調整值+其他調整值（如附魔武器）+守方的傷害減免（如果有的話）
基本就是這樣，副手、雙持、重擊等詳細情況請閱讀 玩家手冊~
可以看出dnd中的ac是免傷，不是一般其他游戲的減傷。

③ 長沙麻將演算法

1、長沙麻將詳解：長沙麻將演算法是胡牌+中鳥（一般兩個鳥，中一個就按下面的計算方式乘以2，中兩個就乘以3）。

2、小胡：閑家一番，莊家兩番，然後再看中鳥。

3、大胡：大胡只有清一色、小七對、將將胡、碰碰胡、全求人、杠上花、海底撈。每個大胡演算法是一樣的，即閑家六番，莊家七番。然後再看中鳥。

4、多大胡：會有多大胡的情況，比如清一色的杠上花，龍七對，碰碰胡的全求人的杠上花，那麼演算法就是這樣的，一個大胡在沒有算鳥的情況下算一盒，兩個大胡就是兩盒，三個就是三盒，再算中鳥。

麻將起源

1、我們俗稱「餅」，它其實是一個糧倉屯（土話）的正上方俯視圖，也就是說」筒「是一個抽象的截圖。大家可以結合搜一個糧倉圖（暫沒有找到合適的俯視圖給大家）。儲糧食的時候，人們用席子圍成一個桶狀的立柱空間，糧食儲存在裡面，為了防漏雨，頂是兩圈草墊以同心圓疊蓋結成。

2、因此，從糧倉的正上方俯視下來，我們看到的抽象事物就是一個「筒」，兩個糧倉就是兩個「筒」，以此類推到「九筒」。後來因打仗傳到南方後，叫法上出現了「餅」的讀音，是一種看圖說話的緣故，但這個錯誤也很普遍地沿襲了下來，讓人們對麻將的歷史理解越來越遠。

基礎

1、一般長沙麻將需要任意花色2、5、8序數做將，才能胡牌。

2、少數特殊牌型可以不需要任意花色2、5、8序數做將也能胡牌，後文會詳細說明。

3、可吃、碰、杠，其中杠牌比較特殊分為「補杠」和「開杠」2種。

4、補杠胡牌時不算杠上花，開杠只有在聽牌時才能開杠，開杠後不可以更改聽張。

5、可自摸、放炮，有人胡牌時，立刻算扎鳥。

番型

1、長沙麻將的特色玩法，跟其他地方麻將，有著一種特殊的區別，那就是多一種起手胡。

2、起手胡是幾種特殊牌型，當麻友們正好起手擁有這幾種牌型，即可算做胡牌，（算完後繼續打牌）。

3、起手一共分為4種番型，分別是四喜、板板胡、缺一門、六六順。

4、四喜：起手手中有四張一樣的牌。

5、板板胡：起完牌後，手中沒有一張花色的2、5、8將牌。

6、缺一色：起手手上筒索萬任意缺一門。

7、六六順：起手手中有2個刻字。

牌型

1、爛鬍子：就是屁胡+1番。

2、全球人：四副牌全是吃碰杠，胡他家打出的牌，6番。

3、碰碰胡：不必詳細解釋，一般麻友都懂，6番。

4、清一色：同一花色牌胡牌，不需要2、5、8做將，也是6番。

5、七對：手中7個對子自摸胡牌，6番。

④ 十三張撲克演算法

積分規則演算法如下：

1、牌面大小順序：A>K>Q>J>10>9>8>7>6>5>4>3>2。

2、牌型大小順序：一條龍>同花順>四條>葫蘆>同花>順子>三條>兩對>對子>散牌（烏龍）。

3、贏一墩：同一墩，大於其他某個玩家，自己加1注(頭墩加1注，中墩加2注，底墩加3注)。

4、輸一墩：同一墩，小於其他某個玩家，自己減1注(頭墩減1注，中墩減2注，底墩減3注)。

5、強碰（打和）：同一墩，與其他玩家大小一樣，自己加0注。

游戲規則：

四人中一人為莊家，（也可以四人對比，） 莊家把除去大小王的一副牌牌分成四份，每份十三張。開牌前，各閑家向莊家下注。

各人把十三張牌排成三段（道），稱頭（道）、二道及尾（道）。頭有三張，二道及尾各五張。頭道必須小於二道，二道必須小於尾道，否則稱為「相公」。凡「相公」者全賠。

頭段因為只有三張牌，因此不算順、花。只可能是不成花式（稱無頭），一對或三條。各人排好牌後，打開牌跟莊家比較大小。頭跟頭比，二道跟二道比，尾跟尾比。

比較時，先比牌型。牌型相同時，比點數。部分玩法的規則，比點數時由最大點數的牌比起，相同時比第二大的牌，如此類推。倘若完全相同，比最大點數牌的花色。

部分玩法的規則訂成對莊家稍為有利：只比點數最大的一隻牌。倘若相同，一律由莊家勝。任何一方遇上以下的組合通吃，稱為「報到」。

⑤ 珠算的演算法口訣

珠算四則運算皆用一套口訣指導撥珠完成。加減法，明代稱「上法」和「退法」，其口訣為珠算所特有，最早見於吳敬《九章演算法比類大全》(1450)。乘法所用的「九九」口訣，起源甚早，春秋戰國時已在籌算中應用。北宋科學家沈括在其《夢溪筆談》卷十八中介紹「增成法」時說:「唯增成一法稍異，其術都不用乘除，但補虧就盈而已。假如欲九除者增一便是，八除者增二便是，但一位一因之」。「九除者增一」，後來變為「九一下加一」，「八除者增二」後來變為「八一下加二」等口訣。可見「增成法」就是「歸除法」的前身。楊輝在《乘除通變算寶》中，敘述了「九歸」，他在當時流傳的四句「古括」上，添注了新的口訣三十二句，與現今口訣接近。元代朱世傑的《算學啟蒙》(1299，卷上)載有九歸口訣三十六句，和現今通行的口訣大致相同。14世紀中丁巨撰演算法八卷(1355)，內有「撞歸口訣」。總之，歸除口訣的全部完成在元代。有了四則口訣，珠算的演算法就形成了一個體系，長期沿用了下來。

⑥ 演算法與程序的區別與聯系

演算法和程序的區別是：

(1) 兩者定義不同。演算法是對特定問題求解步驟的描述，它是有限序列指令。而程序是實現預期目的而進行操作的一系列語句和指令。

說通俗一些演算法是解決一個問題的思路，程序，是解決這些問題所具體好寫的代碼。演算法沒有語言界限。他只是一個思路。為實現相同的一個演算法，用不同語言編寫的程序會不一樣。

(2)兩者的書寫規定不同。程序必須用規定的程序設計語言來寫，而演算法很隨意。演算法是一系列解決問題的清晰指令，也就是說，能夠對一定規范的輸入，在有限時間內獲得所要求的輸出。演算法常常含有重復的步驟和一些邏輯判斷。

簡單演算法舉例 例：求 1*2*3*4*5

步驟 1 ：先求 1*2 ，得到結果 2 。

步驟 2 ：將步驟 1 得到的乘積 2 再乘以 3 ，得到結果 6 。

步驟 3 ：將步驟 2 得到的乘積 6 再乘以 4 ，得到結果 24 。

步驟 4 ：將步驟 3 得到的乘積 24 再乘以 5 ，得到最後結果 120 。

演算法與程序的聯系 ：

演算法和程序都是指令的有限序列 ，但是程序是演算法，而演算法不一定是 程序。程序 = 數據結構 + 演算法。演算法的主要目的在於為人們提供閱讀了解所執行的工作流程與步驟。數據結構與演算法要通過程序的實現，才能由計算機系統來執行。可以這樣理解，數據結構和演算法形成了可執行的程序。

(6)打則演算法擴展閱讀

演算法的要素：

一、數據對象的運算和操作：計算機可以執行的基本操作是以指令的形式描述的。一個計算機系統能執行的所有指令的集合，成為該計算機系統的指令系統。一個計算機的基本運算和操作有如下四類：

1、算術運算：加減乘除等運算。

2、邏輯運算：或、且、非等運算。

3、關系運算：大於、小於、等於、不等於等運算。

4、數據傳輸：輸入、輸出、賦值等運算。

二、演算法的控制結構：一個演算法的功能結構不僅取決於所選用的操作，而且還與各操作之間的執行順序有關。