覆面演算法

Ⅰ 軟體測試的方法一共有幾種

1、從是否關心內部結構來看

（1）白盒測試：又稱為結構測試或邏輯驅動測試，是一種按照程序內部邏輯結構和編碼結構，設計測試數據並完成測試的一種測試方法。

（2）黑盒測試：又稱為數據驅動測試，把測試對象當做看不見的黑盒，在完全不考慮程序內部結構和處理過程的情況下，測試者僅依據程序功能的需求規范考慮，確定測試用例和推斷測試結果的正確性，它是站在使用軟體或程序的角度，從輸入數據與輸出數據的對應關系出發進行的測試。

（3）灰盒測試：是一種綜合測試法，它將「黑盒」測試與「白盒」測試結合在一起，是基於程序運行時的外部表現又結合內部邏輯結構來設計用例，執行程序並採集路徑執行信息和外部用戶介面結果的測試技術。

2、從是否執行代碼看

（1）靜態測試：指不運行被測程序本身，僅通過分析或檢查源程序的語法、結構、過程、介面等來檢查程序的正確性。

(2)動態測試：是指通過運行被測程序，檢查運行結果與預期結果的差異，並分析運行效率、正確性和健壯性等性能指標。

3、從開發過程級別看

（1）單元測試：又稱模塊測試，是針對軟體設計的最小單位----程序模塊或功能模塊，進行正確性檢驗的測試工作。其目的在於檢驗程序各模塊是否存在各種差錯，是否能正確地實現了其功能，滿足其性能和介面要求。

(2)集成測試：又叫組裝測試或聯合，是單元測試的多級擴展，是在單元測試的基礎上進行的一種有序測試。旨在檢驗軟體單元之間的介面關系，以期望通過測試發現各軟體單元介面之間存在的問題，最終把經過測試的單元組成符合設計要求的軟體。

（3）系統測試：是為判斷系統是否符合要求而對集成的軟、硬體系統進行的測試活動、它是將已經集成好的軟體系統，作為基於整個計算機系統的一個元素，與計算機硬體、外設、某些支持軟體、人員、數據等其他系統元素結合在一起，在實際運行環境下，對計算機系統進行一系列的組裝測試和確認測試。

在系統測試中，對於具體的測試類型有：

（1）功能測試：對軟體需求規格說明書中的功能需求逐項進行的測試，以驗證功能是否滿足要求。

（2）性能測試：對軟體需求規格說明書的功能需求逐項進行的測試，以驗證功能是否滿足要求。

（3）介面測試：對軟體需求規格說明中的介面需求逐項進行的測試。

（4）人機交互界面測試：對所有人機交互界面提供的操作和顯示界面進行的測試，以檢驗是否滿足用戶的需求。

（5）強度測試：強制軟體運行在異常乃至發生故障的情況下（設計的極限狀態到超出極限），驗證軟體可以運行到何種程序的測試。

（6）餘量測試：對軟體是否達到規格說明中要求的餘量的測試。

（7）安全性測試：檢驗軟體中已存在的安全性、安全保密性措施是否有效的測試，

（8）可靠性測試：在真實的或模擬的環境中，為做出軟體可靠性估計而對軟體進行的功能（其輸入覆蓋和環境覆蓋一般大於普通的功能測試）

（9）恢復性測試：對有恢復或重置功能的軟體的每一類導致恢復或重置的情況，逐一進行的測試。

（10）邊界測試：對軟體處在邊界或端點情況下運行狀態的測試。

（11）數據處理測試：對完成專門數據處理功能所進行的測試。

（12）安裝性測試：對安裝過程是否符合安裝規程的測試，以發現安裝過程中的錯誤。

（13）容量測試：檢驗軟體的能力最高能達到什麼程度的測試。

（14）互操作性測試：為驗證不同軟體之間的互操作能力而進行的測試。

（15）敏感性測試：為發現在有效輸入類中可能引起某種不穩定性或不正常處理的某些數據的組合而進行的測試。

（16）標准符合性測試：驗證軟體與相關國家標准或規范（如軍用標准、國家標准、行業標准及國際標准）一致性的測試。

（17）兼容性測試：驗證軟體在規定條件下與若干個實體共同使用或實現數據格式轉換時能滿足有關要求能力的測試。

（18）中文本地化測試：驗證軟體在不降低原有能力的條件下，處理中文能力的測試。

4、從執行過程是否需要人工干預來看

（1）手工測試：就是測試人員按照事先為覆蓋被測軟體需求而編寫的測試用例，根據測試大綱中所描述的測試步驟和方法，手工地一個一個地輸 入執行，包括與被測軟體進行交互（如輸入測試數據、記錄測試結果等），然後觀察測試結果，看被測程序是否存在問題，或在執行過程中是否會有一場發生，屬於比較原始但是必須執行的一個步驟。

（2）自動化測試：實際上是將大量的重復性的測試工作交給計算機去完成，通常是使用自動化測試工具來模擬手動測試步驟，執行用某種程序設計語言編寫的過程（全自動測試就是指在自動測試過程中，不需要人工干預，由程序自動完成測試的全過程；半自動測試就是指在自動測試過程中，需要手動輸入測試用例或選擇測試路徑，再由自動測試程序按照人工指定的要求完成自動測試）

5、從測試實施組織看

（1）開發測試：開發人員進行的測試

（2）用戶測試：用戶方進行的測試

（3）第三方測試：有別於開發人員或用戶進行的測試，由專業的第三方承擔的測試，目的是為了保證測試工作的客觀性

6、從測試所處的環境看

（1）阿爾法測試：是由一個用戶在開發環境下進行的測試，也可以是公司內部的用戶在模擬實際操作環境下進行的測試

（2）貝塔測試：是用戶公司組織各方面的典型終端用戶在日常工作中實際使用貝塔版本，並要求用戶報告

(1)覆面演算法擴展閱讀

軟體測試的內容：

1 得到需求、功能設計、內部設計說書和其他必要的文檔

2 得到預算和進度要求

3 確定與項目有關的人員和他們的責任、對報告的要求、所需的標准和過程 ( 例如發行過程、變更過程、等等 )

4 確定應用軟體的高風險范圍，建立優先順序、確定測試所涉及的范圍和限制

5 確定測試的步驟和方法 ── 部件、集成、功能、系統、負載、可用性等各種測試

6 確定對測試環境的要求 ( 硬體、軟體、通信等 )

7 確定所需的測試用具 (testware) ，包括記錄 / 回放工具、覆蓋分析、測試跟蹤、問題 / 錯誤跟蹤、等等

8 確定對測試的輸入數據的要求

9 分配任務和任務負責人，以及所需的勞動力

10 設立大致的時間表、期限、和里程碑

11 確定輸入環境的類別、邊界值分析、錯誤類別

12 准備測試計劃文件和對計劃進行必要的回顧

13 准備白盒測試案例

14 對測試案例進行必要的回顧 / 調查 / 計劃

15 准備測試環境和測試用具，得到必需的用戶手冊 / 參考文件 / 結構指南 / 安裝指南，建立測試跟蹤過程，建立日誌和檔案、建立或得到測試輸入數據

16 得到並安裝軟體版本

17 進行測試

18 評估和報告結果

19 跟蹤問題 / 錯誤，並解決它

20 如果有必要，重新進行測試

21 在整個生命周期里維護和修改測試計劃、測試案例、測試環境、和測試用具

Ⅱ 游戲攻擊判定的三種模式

轉自：http://www.gameres.com/677620.html

攻擊判定流程幾乎是所有包含戰斗玩法的游戲都無法繞過的一塊內容，常見的攻擊判定流程有瀑布演算法、圓桌演算法以及混合演算法三種。本文簡述了這三種判定流程的特徵，以實例對比分析了瀑布演算法與圓桌演算法各自的優點，以期為後續其他戰斗數值設計內容的論述提供一定的基礎。

攻擊判定流程概述

自此開始正文內容的敘述——讓我們直接代入一個實例：

在一款游戲中，攻擊方有命中率和暴擊率兩個攻擊屬性，而防守方有閃避率、招架率和格擋率三個防禦屬性。於是相應的，一次攻擊有可能產生6種判定結果：未命中、普通命中、閃避、招架、格擋和暴擊。當採用不同的判定流程進行攻擊結算時，6種判定結果出現的頻率會截然不同。

1.  瀑布演算法

顧名思義，在瀑布演算法中，各事件的判定順序如同瀑布一般自上而下。如果「水流」在某個位置被截斷，則後面的流程都將不再繼續進行。據我所知，瀑布演算法是大多數游戲所採用的攻擊判定演算法。

上述實例若採用瀑布演算法，則會以如下方式進行判定：

先判定攻方是否命中

再判定是否被守方閃避

再判定是否被守方招架

再判斷是否被守方格擋

最後判定該次攻擊是否為暴擊

瀑布演算法流程圖

由此我們可以得出：

瀑布演算法特徵1：多次擲骰，一次擲骰只判定單個事件的發生與否

瀑布演算法特徵2：後置判定依賴於前置判定的通過

註：有的游戲會將命中和閃避合並在一次擲骰中判定，這意味著將攻方命中率與守方閃避率合並計算出實際擊中概率後再進行擲骰判定，仍是瀑布演算法

我們再代入一些具體的數值，設攻守雙方角色的面板屬性如下：

攻方命中率=90%

攻方暴擊率=25%

守方閃避率=20%

守方招架率=15%

守方格擋率=30%

按照上述的流程判定，6種判定結果將會按如下的概率分布：

實際未命中概率=1-命中率=1-90%=10%

實際閃避概率=命中率*閃避率=90%*20%=18%

實際招架概率=命中率*（1-閃避率）*招架率=90%*(1-20%）*15%=10.8%

實際格擋概率=命中率*（1-閃避率）*（1-招架率）*格擋率=90%*(1-20%)*(1-15%)*30%=18.36%

實際暴擊概率=命中率*（1-閃避率）*（1-招架率）*（1-格擋率）*暴擊率=90%*(1-20%)*(1-15%)*(1-30%)*25%=10.71%

實際普通命中概率=命中率*（1-閃避率）*（1-招架率）*（1-格擋率）*（1-暴擊率）=90%*(1-20%)*(1-15%)*(1-30%)*(1-25%)=32.13%

瀑布演算法的判定結果分布

由此我們可以得出：

l 瀑布演算法特徵3：各事件出現的概率符合經典的概率計算方法

l 瀑布演算法特徵4：擲骰輪次越偏後的屬性衰減程度越大，但不會出現無效的屬性

2.圓桌演算法

將所有可能出現的事件集合抽象成一個圓桌桌面，便是圓桌演算法這一稱呼的由來。圓桌演算法的實質，是將所有可能發生的事件狀態按優先順序依次放上桌面，直至所有事件被放完或桌面被填滿。圓桌演算法正是史詩級巨作魔獸世界中所採用的演算法。據筆者了解，使用該演算法的游戲並不多見，但即便僅魔獸世界這一款，已足以使這種演算法成為永恆的經典~

上述實例若採用圓桌演算法，則會用一次擲骰判定該次攻擊的結果。

圓桌演算法流程圖

圓桌演算法的操作步驟可以歸納為：

（1）攻方角色的命中率決定圓桌桌面的大小

（2）將各個事件狀態按優先順序依次放上桌面，直至所有的事件均放置完或桌面被填滿

（3）若桌面還未填滿，則用普通命中填滿空桌面

將先前設定的數值代入，6種判定結果將會按如下的概率分布：

實際未命中概率=10%

實際閃避概率=20%

實際招架概率=15%

實際格擋概率=30%

實際暴擊概率=25%

實際普通命中概率=90%-實際閃避概率-實際招架概率-實際格擋概率-實際暴擊概率=90%-20%-15%-30%-25%=0%

註：在上述計算中，優先順序按如下排序：閃避>招架>格擋>暴擊>普通命中

圓桌演算法的判定結果分布

可以看出，由於普通命中的優先順序最低，所以它被完全擠出了桌面。這意味著，若攻守雙方以此數值模型進行對決，則攻擊方的攻擊結果中將不存在普通命中。

由此我們可以得出：

圓桌演算法特徵1：一次擲骰即得出該次攻擊的判定結果

圓桌演算法特徵2：事件有優先順序，圓桌放滿後優先順序低的事件將被擠出桌面。這意味著那部分溢出的屬性將不再生效

圓桌演算法特徵3：圓桌內的各事件出現概率不會衰減，只要優先順序低的屬性沒有被擠出圓桌，各種事件的實際發生概率就與面板屬性數值吻合

3. 混合演算法

這是一種先判定攻方事件，再判定守方事件的判定流程。筆者曾在一篇帖子中看到過這樣判定流程，不確定是否有實際的游戲應用，故僅在此做一些簡單的理論分析。

混合演算法在單方事件的判定中採用圓桌演算法，即：

攻方判定結果：普通命中OR未命中OR暴擊

守方判定結果：閃避OR招架OR格擋OR被命中

混合演算法流程圖

註：上面這個圖僅作示意之用，從流程圖的角度來看可能不太嚴謹

將先前設定的數值代入，6種判定結果將會按如下的概率分布：

實際未命中概率=10%

實際閃避概率=攻方命中率*閃避率=90%*20%=18%

實際招架概率=攻方命中率*招架率=90%*15%=13.5%

實際格擋概率=攻方命中率*格擋率=90%*30%=27%

實際暴擊概率=攻方暴擊率*敵方被命中概率=25%*(1-20%-15%-30%)=8.75%

實際普通命中概率=攻方普通命中概率*敵方被命中概率=(90%-25%)*(1-20%-15%-30%)=22.75%

混合演算法的判定結果分布

由此我們可以得出：

混合演算法特徵1：先判定攻方事件，再判定守方事件，共進行兩次擲骰

混合演算法特徵2：先在單方事件的判定中採用圓桌演算法，再用瀑布演算法串聯攻守雙方事件

混合演算法特徵3：會產生並發動作，例如暴擊被閃避等

註：這也正是實際暴擊率較低原因所在

瀑布演算法與圓桌演算法的特性對比

在上一塊內容的鋪墊之下，我們不妨繼續以魔獸世界中的攻擊判定流程設計實例作為切入點，對比分析一下圓桌演算法與瀑布演算法各自的特性。

（1）面板屬性傳遞信息的直觀性

瀑布：由於各屬性在判定流程上的生效時間有先後之分，所以各屬性的實際效用與面板顯示的不符。

圓桌：由於屬性的判定沒有先後之分，只要沒有屬性被擠出圓桌，則所有屬性的實際效用與面板顯示的相當。

這里可以看出圓桌演算法的優點：

屬性的實際效用與面板顯示相符顯然更易於普通玩家的理解，便於玩家掌握自身的戰力情況。

（2）屬性的價值

瀑布：擲骰輪次越偏後的屬性衰減程度越大，但所有的屬性均會生效。

圓桌：只要沒有屬性被擠出圓桌，則不存在屬性效用的衰減。

這里可以看出圓桌演算法的優點：

由於不存在判定流程上的先後，所以各屬性的實際價值會比較接近，一般不會出現玩家堆了某個判定流程靠後的屬性結果很廢的情況。

同樣也可以看出其缺點：

一旦有屬性溢出，則該部分屬性的效用為0，完全沒有價值。

（3）相同面板數值下的生存能力

圓桌：在面板數值相同的情況下，魔獸世界用圓桌演算法大大提高了坦克角色的生存能力，使得他們可以應對來自首領怪的超高攻擊，匹配大型團隊副本的玩法設計。

瀑布演算法下，免傷概率=18%+10.8%+18.36%=47.16%

圓桌演算法下，免傷概率=20%+15%+30%=65%

傳統的概率為相乘關系，圓桌為相加關系，後者的概率總和要大的多

並且，當防禦職業將三維堆至一個閾值（70%）後，配合技能可達100%的免傷覆蓋，將命中和暴擊全部擠出桌面，從而衍生出特定的玩法（70級年代伊利丹的剪切技能）。

瀑布：相同的面板數值在瀑布演算法的框架下，免傷概率相較於圓桌演算法要低得多。換言之，角色達到相同的有效生命值，所需的免傷屬性要高得多。

這里可以看出：

在圓桌演算法的框架之下，屬性投放若是脫離了控制超過了閾值，將對平衡性產生較大的沖擊（70級的盜賊單刷格魯爾——當然在暴雪光環的作用下，玩家會認為這是精妙的設計~）。

在國產游戲收入導向的大環境下，設計者是否能頂住收入壓力，嚴守屬性投放的極值不越界，是值得慎思的問題。採用瀑布演算法，能有更大的數值空間用於能力投放，更為適合現階段的市場環境。

（4）運算量

瀑布：多次擲骰

圓桌：單次擲骰

顯而易見：

擲骰次數越多，運算量越大。圓桌相較於瀑布，有著相對較小的運算量。簡單即是美。

註：除魔獸世界外，《冒險與挖礦》的技能施放也採用了圓桌演算法，大大簡化了技能施放的判定流程。可以想像一下，一次攻擊至多發動一個技能。而每一次攻擊，一個隊伍中有幾十個角色的技能施放需要判定，如果採用瀑布演算法，將產生多大的運算量。

思考與總結

對戰斗數值的研究，應該基於理論推導而歸於實踐應用。畢竟游戲數值設計不是做數學研究，其本質應是一種體驗設計。最後希望交流的是筆者個人對於這兩種演算法的一些理解。

（1）不同的攻擊判定流程會向玩家傳達不同的戰斗感受

究其本質，不同的攻擊判定流程，影響著一場戰斗中的各種攻擊判定結果將以何種概率分布出現。

假設在一款游戲中，閃避率的投放上限是30%，暴擊率的投放上限是40%，命中率的投放上限是100%。瀑布演算法下，出現閃避、暴擊和普通命中的概率是30%、28%和42%；圓桌演算法下，則為30%、40%和30%。這兩種不同的概率分布，必然會帶給玩家不同的戰斗體驗，但在缺少其他條件的情況下，並不能判斷孰優孰劣。

使戰斗體驗匹配游戲的核心玩法，使屬性投放的極限值能滿足游戲的商業化需要，是設計攻擊判定流程時首先要考慮的。

註：甚至於部分競技游戲強調公平性，將暴擊做成了偽隨機。

使用瀑布演算法，則不應該設計種類繁多的事件狀態

若是仿照魔獸世界的做法設計一連串的事件狀態（未命中、閃避、招架、格擋、暴擊、普通命中、偏斜、碾壓），非但運算繁雜，而且後置判定的屬性衰減幅度較大，效果極不明顯。這種隱晦的設計將不易傳達，同時還會影響玩家的游戲感受（某個判定流程靠後的屬性堆得很高結果卻沒用）。

使用圓桌演算法，則應該嚴守屬性投放的上限，防止平衡崩壞的情況發生

需要澄清的是，並不是說使用瀑布演算法就可以無限投放數值，而是說，相較於瀑布演算法，圓桌演算法的屬性投放上限會低很多（免傷概率的相加與相乘）

（2）不同的攻擊判定流程將影響有效生命EHP和有效攻擊EDPS的表達式

幾乎每個數值策劃都會將角色的屬性轉化為EHP和EDPS以衡量其的戰斗能力，但曾見過不少人對所有的游戲都用統一的EHP、EDPS表達式進行分析模擬。這種偏差較大的模擬方式必然會影響體驗設計的精準性。在不同的攻擊判定流程之下，EHP與EDPS有著截然不同的表達式，舉例說明如下。

瀑布演算法下：

若命中閃避分兩次判定：

EHP=HP/(1-免傷率)/(1-閃避率)/(1-招架率)

EDPS=DPS*命中率*[1+暴擊率*(暴擊傷害倍率-1)]

若命中閃避合並判定：

EHP=HP/(1-免傷率)/(命中率-閃避率)/(1-招架率)

EDPS=DPS*(1+暴擊率*(暴擊傷害倍率-1))

圓桌演算法下：

EHP=HP/(1-免傷率)/(1-閃避率-招架率)

EDPS=DPS*[命中率-敵方閃避率-敵方招架率+暴擊率*(暴擊傷害倍率-1)]

註：閃避、招架>暴擊>普通命中，且各狀態發生概率之和未超過圓桌大小

混合演算法下：

EHP=HP/(1-免傷率)/(1-閃避率-招架率)

EDPS=DPS*[命中率+暴擊率*(暴擊傷害倍率-1)]

可能有人會覺得：模擬得這么准又有什麼卵用，數值平衡最後還不是靠調？誠然，在數值設計領域，確實有名言曰：數值平衡是調出來的。但在筆者看來，調節應該建立在正確的理論推導的基礎之上。依靠調節來掩蓋數值模型的錯誤設計，是本末倒置的行為。即便達到了所謂的平衡，也不過是扭曲的平衡，會為後續版本的迭代埋下隱患。

寫在最後

市面上的大多數游戲，都不會設計復雜繁多的攻擊事件，且基本採用瀑布演算法。如此看來，攻擊判定流程的設計十分簡單。那麼為什麼要大費周章地將簡單問題復雜化呢？

愛因斯坦曾說過：Everythingmust be made as simple as possible, but not one bit simpler——凡事應該力求簡單，但不能過於簡單。從了解一種數值設計方法到理解如此設計的目的，從模仿成功游戲的數值設計到理解其設計的內在意義，這是每個數值策劃成長的必經之路。

從全盤照搬一種數值體繫到能夠融會貫通並根據實際情況靈活運用，這是一條並不好走的路。知其然，也應知其所以然——這是一個入行一年有餘的新人的一點感悟。

免責申明：

1.筆者無法保證本文所用詞彙的普適性，能力所限，請多包涵~

2.不保證文中魔獸世界實例中的設定均與原作完全相符。但即便不相符，也不會影響圓桌理論的推

Ⅲ 怎麼求最小面積的三角形覆蓋平面上的點集的演算法

#include <stdio.h>
#include <math.h>
// 輸入最多的點數目
#define MAX_POINTS_AMOUNT 100

struct Point
{
double x,y;
};
// 求點 p1, p2 的距離
double distance(struct Point p1, struct Point p2)
{
return sqrt((p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y));
}
// 求 a, b, c 中的最大值
double max(double a, double b, double c)
{
return a>=b && a>=c
? a
: b>=a && b>=c
? b
: c;
}

// 判斷長度為 a, b, c 的 3條線段能否組成三角形
// 判斷依據為：至少有一條邊的長度，大於另兩條邊的長度差（絕對值），小於另兩條邊的長度和
int canMakeTriangle(double a, double b, double c)
{
return a>fabs(b-c) && a<(b+c) ||
b>fabs(a-c) && b<(a+c) ||
c>fabs(a-b) && c<(a+b);
}

// 判斷長度為 a, b, c 的 3條線段能否組成銳角三角形
// 判斷依據：根據餘弦定理，求出 3 個角的餘弦值
int canMakeAcuteTriangle(double a, double b, double c)
{
unsigned int i;
double cos_a, cos_b ,cos_c;
if(canMakeTriangle(a, b, c))
{
cos_a = (b*b + c*c - a*a)/(2*b*c);
cos_b = (a*a + c*c - b*b)/(2*a*c);
cos_c = (a*a + b*b - c*c)/(2*a*b);
return cos_a>0 && cos_b>0 && cos_c>0;
}
return 0;
}

/* 求覆蓋 n 個點 points 的最小圓的半徑
演算法：
只要分別求出所有3點組合覆蓋的最小圓，取其中半徑最大者即為所求。
確定覆蓋3點的最小圓的步驟可以如下：
(1) 若3點組成直角或鈍角三角形，或3點共線，此時，最小圓的半徑為三邊中最長邊的一半。
(2) 否則，3點組成銳角三角形，最小圓為3點的外接圓。
(3) 外接圓半徑計算方法：
(a) 若3點構成一個三角形(即3點不共線)，
並設3點的坐標為 (x1,y1)，(x2,y2)，(x3,y3)，求出兩點(x1,y1)和(x2,y2)之間的距離
L1=sqrt((x1-x2)^2+(y1-y2)^2), 同樣求出(x1,y1)和(x3,y3)之間的距離L2，
以及(x2,y2)和(x3,y3)之間的距離L3。
(b) 求出三角形半周長L=(L1+L2+L3)/2以及面積S=sqrt(L*(L-L1)*(L-L2)*(L-L3))。
(c) 根據公式4SR=L1*L2*L3，求外接圓半徑R=L1*L2*L3/(4*S)。
參數：
n ： 點數目
points ： n 個點的坐標
start ： 遞歸參數。表示當前從在 n 個點的第 start 個開始選取。初始值為 0。
selectPointsAmount ： 遞歸參數。表示當前已經選好了的點數。最多為 3 個。初始值為 0。
selectPoints : 遞歸參數。表示當前已經選好了的點的坐標數組。初始值為 NULL。
返回：
覆蓋 n 個點 points 的最小圓的半徑。

*/
double minCircleRadius(unsigned int n, struct Point points[],
unsigned int start, unsigned int selectPointsAmount, struct Point selectPoints[])
{
if(n <= 1)
return 0.0;
if(n == 2)
return distance(points[0], points[1])/2.0;
else
{
if(selectPointsAmount == 3)
{// 已經選好了 3 個點，求能覆蓋它們的最小圓的半徑

double L1 = distance(selectPoints[0], selectPoints[1]);
double L2 = distance(selectPoints[0], selectPoints[2]);
double L3 = distance(selectPoints[1], selectPoints[2]);
double L = (L1 + L2 + L3)/2.0;
double S = sqrt(L*(L-L1)*(L-L2)*(L-L3));
if(canMakeAcuteTriangle(L1, L2, L3))
{// 能組成銳角三角形
return L1*L2*L3/(4.0*S);
}
else
{// 其他情況：三點共線，組成直角三角形，或銳角三角形
return max(L1, L2,L3)/2.0;
}
}
else
{// 任選 3 個點
double r, minR = 0.0;
unsigned int i;

struct Point temp[3];
if(selectPoints == NULL)
selectPoints = temp;

for(i=start;(n-i)>=(3-selectPointsAmount);i++)
{
selectPoints[selectPointsAmount] = points[i];
r = minCircleRadius(n, points, i+1, selectPointsAmount+1, selectPoints);
if(minR < r)
minR = r;
}
return minR;
}
}
}
int main(int argc, char *argv[])
{
struct Point points[MAX_POINTS_AMOUNT];
unsigned int i,n;
while(scanf("%d",&n)!=EOF)
{
for(i=0; i<n; i++)
scanf("%lf,%lf",&points[i].x, &points[i].y);
printf("%.4lf\n",minCircleRadius(n, points, 0, 0, NULL));
}
return 0;
}
/*
4
4.2,5.6
78.3,3.8
35.4,15.9
29.88,42.56
*/

Ⅳ 我國植被覆蓋率如何計算，與森林覆蓋率的區別是什麼

植被覆蓋率是指所有植被,包草本木本植被,其覆蓋率的演算法為:以一個區域內的植被覆蓋面積除以這個區域的總面積.
與森林覆蓋率的的區別是:植被覆蓋率所指的范圍更廣.

Ⅳ 象棋軟體引擎分析，詳細信息，引擎是怎麼搜索招式的

作者:nicepeople10

中象棋軟搜索引擎揭密(一) fenon
北京大賽終於過去了, 在這場盛事前後這段時間, 靜下心來回顧了走過的象棋研究的路子,心得感觸良多.為了紀念這段時間的美好, 我決定把這段時間積累的對象棋引擎的心得, 總結分享出來
我個人希望通過這篇文章,把一些頂尖棋軟的知識普及開來,提高開源象棋軟體的水平.

1. 搜索引擎和審局之間的關系, 如何建立

閱讀下面的內容時, 首先需要了解幾個背景知識
a. 人工智慧的博弈搜索樹和PVS搜索之間的關系
b. PVS搜索是無損搜索
c. PVS的搜索效率和搜索次序的關系

首先明確幾點:

a. 做一個全PVS的搜索, 在限定了層數的情況下, 如果基於不正確的知識(比如子力表),並不能保證一定能把殺棋找出來(可能會跑去吃子)
b. 為了提高棋力, 無損搜索PVS是不足夠的, 還是需要剪枝的
c. 搜索樹和審局之間的關系, 首先知識必須能夠引導搜索到正確盤面(這個地球人應該都知道), 第二是避免搜索把正確的分支剪除掉(這個談論得少一些,我以前曾經有很長一段時間不知道)
我認為, 審局和搜索之間的關系的建立, 在於
a. 知識是帶有正確的傾向性的(只能說是傾向性,因為知識很難做到全面准確)
b. 搜索是根據知識而採取剪枝方式的(這個下面詳細分析)

下面我舉一個簡單的例子, 來說明知識和搜索之間的關系

帥
_____
| | |
馬 _| 將_|_兵
| _ |_ |_ |_象

在這個盤面, 兵只要靠近王一步, 就可以將死了對方, 但是基於子力表做depth=1的PVS搜索,只會選擇: 兵吃象, 有利, 而且評估子力分數很高, 所以吃象

那麼, 有什麼辦法避免這種情況呢?

a. depth=1的時候不做剪枝
b. 給予引擎審局的知識, 告訴引擎保持"馬非底線兵"這種組合對將才具有殺傷力

這樣就給出了兩種選擇, 哪種更好?

實際上, b這種選擇有兩種局限
a. 局限於現在對審局模型建立的水平, b這種情況需要花費大量的人力功夫來維護完整的知識, 而且很難做到准確
b. 目前的引擎的搜索棋步排序, 大都是基於最近訪問->殺棋步->吃子步這樣的棋步排序方法, 我們可以很容易想像到, 使用全面復雜的知識, 會引起搜索結果沖突(湊著一個吃子或者殺棋的步子去走, 但是最後發現達不到預期的效果), 大大降低了搜索的效率

正是因為上面的原因, 現在我所了解到的高端引擎, 大都是通過控制剪枝的危險程度, 來彌補知識的不足, 比如, 在nullmove中限制depth>=2, 或者, 在lmr(late move rection)--如變種:fruit的history pruning, 控制depth>=3, 都是利用控制剪枝來彌補知識的缺陷.

我們很清楚知道, depth<=2的時候, 都限制了不能剪枝的話, 那麼剛才的盤面, 並不需要任何知識,就可以找出殺棋步, 但是, 這個是不是我們需要的呢? 我想不是的, 如果限制了depth<=2不能剪枝的話, 我們會發現我們的搜索, 產生了大量的節點, 啊, 天啊, 可怕的搜索浪費

當然, 最理想的方法是, 搜索排序的次序是基於知識的, 而且盤面評估是基於知識的, 如果我們能夠達到這樣的效果, 嗯, 我想depth<=1不剪枝的限制也可以去掉了, 這樣的引擎肯定效率更高吧

現在, 讓我們想想, 哪些分支我們是不想被錯誤剪掉的? 當然是殺棋步, 殺棋>吃子, 基於子力表的搜索PVS, 很可能漏掉的棋步是殺棋步, 而這個恰恰是我們不想見到的
對於攻殺激烈的中國象棋,可以說兩個引擎的差別在於,誰能更快更准確找到殺棋步.

口語化一點來說,給你多搜索兩層的能耐,你能保證絕對能通過蠶食我的大子把我變成光棍司令? 尤其是隨著高層效應的出現(引擎和硬體的發展,搜索的層數越來越大), 這種可能更是趨向於零, 所以, 我們應該盡量避免漏掉殺棋步

我知道有很多引擎的做法是, 對有潛在攻勢的局面做出模糊判斷, 並且賦予高分, 如越容易發生殺棋的棋步, 給予越高的分數, 例如三子歸邊的分數>馬炮的分數, 這樣就可避免因為吃馬炮而漏掉殺棋, 但是這種模糊判斷有些致命的缺點
a. 模糊知識,會造成大量的搜索浪費(條件越不準確, 越容易造成搜索浪費)
b. 模糊知識會造成錯誤的判斷, 導致亂棄子
c. 引擎發展需要更長的發展周期, 需要大量的對局來積累知識

一種比較適中的解決方案是, 採取depth<=1不剪枝的搜索方法, 並且給予depth=1時候, 可以形成殺棋的棋型知識的判斷
這種方法的原理是, depth=1的搜索,可以達到depth==2的效果, 並且可以避免模糊知識判斷帶來的誤搜索的缺陷

這種解決方案的優點在於
a. depth=1可以生成殺棋的知識可以窮舉
b. 知識准確度高,可以大幅度減少搜索浪費

缺點在於, depth=1可以形成的殺型, 覆蓋面有限, 剩下的知識, 還是需要通過一些模糊判斷來補充, 當然, 這種補充少很多了, 而且完善起來也難度降低很多

上面的介紹可以說是知識模型的缺陷造成的對搜索的依賴, 下面我再來說說, 知識對搜索產生的影響

我們假設有一個盤面, depth=11的PVS全搜索才能發現殺棋, 那麼下面的知識, 做depth=10搜索時,哪種才能走出正確的棋步呢?

a. 對depth=1情況可殺棋的知識評估
b. 對depth>=2情況可殺棋的知識評估
c. 子力組合(如單車單王勝單王)和子力優勢
d. 位置分(不是子力表,只是位置的分數,如靈活度等)

實際上我們很容易就可以判斷出來, depth=1的知識評估,能走出正確的棋步,情況b也可能走出正確的棋步, 但是會有一定的誤判, c, d大都情況下, 走不出正確的棋步

我們現在對所有的知識打分, 這個分數依賴的因素應該是(depth, 准確度, 搜索浪費), 即score=形勢*(准確度/(depth*搜索浪費))

因為用評估盤面希望得到的分數等於depth>3的棋步, 准確度是相當低甚至會引起大量錯誤的, 所以我們對盤面評估會有一定的限度,同理,評估depth=1變化內的盤面,我們可以做到非常精確,這個時候可以給一個准確的分數

上面提到的a,b,c,d四種知識,對中國象棋軟體的知識覆蓋面是相當廣了, 我們可以很簡單看出, a可以獎勵>馬炮的分數, 而b因為可能走入誤區, 常常只是獎勵>士相的分數, 子力組合不會產生誤區,但是需要搜索很深才能得出正解,所以分數也是不會太高,位置分則更小了

但是, 給予引擎全面而准確的知識是否恰當呢? 即, 知識是不是越全面, 棋力越強呢? 很多朋友都問過這個問題, 並且認為恰當的知識會減少搜索量, 而且這也是很多朋友追求的方向. 我實踐的答案是否. 搜索其實是追求一種性價比, 單位搜索量內, 能得到最好的搜索結果, 才是好的搜索. 簡單說說原理, 當盤面有兩三個知識傾向都可以產生PV路徑的時候, 只會帶來引擎的左右徘徊, 尤其在殺棋的盤面, 會大大降低搜索的效率, 這部分的實踐結果, 我會在"6. 建立以kingsafety為核心的審局, 以及審局模型的詳細分析"再進一步詳細分析

這里我想糾正一個錯誤的想法,常常有一些不了解搜索引擎原理的朋友,拿一些盤面,讓棋軟去判斷,看誰能更快更准找到正解,要盡快解出這種盤面,往往需要大量的模糊知識,或者足夠的深度,前者無疑是把棋軟送上絕路的一種做法.這種評估只是有一定的意義,但絕對不是衡量棋軟水平的標准.

2. fruit引擎分析, fruit引擎能達到2600的高度的原因 (對比crafty進行闡述)

fruit引擎並不追求速度,實際上,fruit並沒有使用流行的bitfile,bitrank技術或者bitboard,所以fruit的nps在國際象棋引擎中並不算高(我想比起crafty應該比不上),如果說兩者的差異在於評估的話,嗯,那不在我所了解的范圍,我只談談兩者引擎上面的差別

a. fruit的pv節點的意義以及基於pv節點搜索剪枝的效率
能夠在搜索中, 把PV節點區分出來, 並且根據節點類型進行剪枝, fruit可以說對PVS理解是非常深刻的.

PV節點的定義大家可以查查相關資料, 既然PV節點表示正確的搜索結果, 那麼就肯定不應該剪掉. 同樣,對於不是PV節點的, 就不會找出正確的搜索路徑, 這就應該剪掉.這個也是fruit剪枝的理論依據。

道理是這樣說, 但是我們一開始並不知道每一個節點的類型, 所以在搜索的時候, 會假設某個節點不是PV節點, 然後看它是否會fail, 如果fail,再做PV節點的搜索.

假如這種假設是成立的, 那麼就成功完成了對該非PV節點路徑的剪枝,否則,需要重新搜索,因為對PV節點假設判斷的搜索是做windows=1的搜索,所以耗費的代價是很低的.

下面來看看fruit的實現方法,我認為fruit對PV節點理解的實現方法非常優雅.

int search_root()
{
本節點做PV搜索

if (樹根節點並且首節點)
下一層節點為PV節點 // 這個時候還沒有找出PV路徑,所以必須做PV節點搜索
else
{
下一層節點做假設不是PV節點的搜索
if (fail)
下一層節點做PV節點的搜索
}
}
int search_full()
{
根據上一層對該節點的判斷, 進行節點搜索

if (首節點 || 假設不是PV節點的搜索) // 當假設不是PV節點時, windows=1這個時候不應該假設,應該直接計算了,否則就是重復計算浪費時間
下一節點的節點類型跟本節點類型一致
else
{
下一層節點做假設不是PV節點的搜索
if (fail)
下一層節點做PV節點的搜索
}
}

中象棋軟搜索引擎揭密(二) fenon
crafty中,對PV節點的區分方法,是PV節點是否落在[-vMate,+vMate]中,實際上,這種判斷方法,對子樹的PV節點並不能做出有效的判斷,這也直接導致了搜索效率的下降

正是因為PV節點的特殊意義,所以凡是PV節點,fruit都不做剪枝,不從HASH取步,甚至PV節點還需要加強搜索的強度(參考TogaII)

b. fruit的nullmove剖析

我們先來看看fruit的nullmove的實現
if (UseNull && depth >= NullDepth && node_type != NodePV) { // 不對PV節點進行剪枝, 而且depth==1時不剪枝(原因參考上文)

if (!in_check // 不是將軍盤面
&& !value_is_mate(beta) // 當落入一個不知道上限的窗口時,不剪枝,這種情況發生在height==2時
&& do_null(board) // 國象規矩限定子>=2
&& (!UseNullEval || depth <= NullRection+1 || eval(board) >= beta)) { // 根據距離葉子或者alpha,beta搜索中,棋形的評估進行控制

我想, 對上面的控制條件,大家都是很好理解的, fruit中NullRedcution==3, 這個可以理解為fruit審局做得比較完善,depth<=4進入審局搜索盤面評估的結果, 逼近搜索的結果, 而eval則是對depth>4時候剪枝的控制條件,這種控制條件往往是根據棋形進行控制, crafty是控制大子的個數, fruit是控制評估的結果, 考慮到這個結果因引擎而異, 我就不在這里討論哪種條件才是更好的了

new_depth = depth - NullRection - 1;

move_do_null(board,undo);
value = -full_search(board,-beta,-beta+1,new_depth,height+1,new_pv,NODE_OPP(node_type));
move_undo_null(board,undo);

fruit的nullmove會導致一種和以外不同的搜索情況產生,crafty的做法是,上一層做了NULLMOVE,現在輪到我了,我應該移動棋步,但是fruit的做法,會引起雙方的等待,這是否正確?

答案是,很正確.首先,考慮演算法上面的等價性,連續做NULLMOVE,其實等價於我不知道你是否做了NULLMOVE,不過我也嘗試做一個NULLMOVE,看你是否能對我造成威脅,這個並不違背NULLMOVE的思想,而且一個不會產生PV路徑的節點,做搜索有意義嗎?沒有意義.既然如此,那麼就剪掉吧.

對nullmove的結果,fruit有兩種特別的處理手段

第一,不保存結果,因為fruit的演算法的剪枝,會讓實際的值和nullmove產生的值差別很大
第二,對某些特殊情況,fruit會做一個nullmove verify的search, fruit嘗試全面利用nullmove, 但是某些情況, nullmove成功的概率有限, 需要做一定的驗證

fruit對nullmove的實現方法,可以說得上是歷史性的(開源的引擎來說),這個演算法的優異,是fruit搜索效率特高的一個根本原因

c. fruit的qs加強

在上文中, 我已經提過, fruit是嘗試通過控制depth<=1使用全搜索的方法, 盡可能發現殺棋, 那麼, 對nullmove來說, 如果depth<=4,發生了一個剪枝, 立刻進入了qs, 馬上就把殺棋步剪掉了

為了防止這種情況, fruit對剛進入qs的棋步,不單單生成吃子步,還生成將軍步,這可以有效防止把殺棋步漏掉的情況.

qs裡面,fruit對吃子步產生的將軍步,會解將,讓對方保持繼續進攻的機會,這也是為了防止qs漏掉殺棋步的一種有效措施

雖然qs的論述很少,而且很簡單,但是,對qs中,將軍的檢查,卻有著消耗20%性能,提高50%功能的性價比,這個也是crafty所缺少的

d. fruit的history pruning

要了解history pruning, 首先建議參考國象中成熟的演算法lmr (late move rection)的論述
fruit對lmr引入了history value,並且對搜索結果做了verify,有效避免了lmr曾經的fail high的問題
這里就不對history pruning的限制條件做詳細的闡述了,實際上這種防止危險的檢查方法和nullmove的限制是類似的,而且會根據不同引擎知識和搜索結合的特點而存在差異
history pruning經實踐證明, 是一種非常有效的剪枝方法, 並且絕對不會對棋力有降低的影響(其實根本原因是不會漏掉殺棋步)

history pruning根據國外的測試,能夠提高elo 100,舊版的crafty並沒有history pruning

e. fruit的hash實現方法

fruit的hash實現方法,經實踐,大概比crafty的方法提高了5%~10%的性能

fruit對每個盤面,保存了一個上界和一個下界,如果對一個盤面搜索時,發現該盤面的搜索范圍上界比過往的下界都要小, 則返回保存的下界, 如果發現搜索范圍的下界比保存的上界要大, 則返回保存的上界, 如果發現盤面落入保存的窗口中, 則當保存的上界和下界重合而且搜索深度比當前搜索深度更深時, 返回保存的結果

這種hash的處理方法,修正了crafty中,只能對單邊情況保存的不足, 有效提高了效率

需要注意的地方是, 在iterative search中, 每次fruit都會把搜索出來的PV路徑都保存到hash中,這是用於取步(不是取值), 還有,在處理hash沖突時候, fruit使用了多個cluster的方法...需要細究的細節很多, 大家有興趣可以仔細看看fruit的實現

f. fruit的search root move list

fruit對每次搜索後對root節點記錄分值,並根據分值重新排序,以便下一次使用,當棋步產生振盪的時候(在兩個棋步之間徘徊)會有效提高引擎的搜索效率

g. fruit的FAIL SOFT

嗯, 關於FAIL SOFT以及實踐的方法, 可以參考縱馬奔流的****和fruit的代碼, 我就不再無聊多說一次了..

3. fruit 2.1和TogaII1.2.1的差異,elo 100的差距原因

首先需要說明的是,我是用diff的方法,比較兩者在搜索實現上的差別的, 應該是沒有遺漏的

兩者的差別列舉如下
a. 延伸的差異, 根據特定棋形做了depth+1的搜索, 也就是越搜反而越深(當然TogaII有手段防止過深)
b. 剪枝的差異, 包括打開futility, delta, 並且對底層也做了history pruning
c. 對棋步穩定的盤面(只產生一個PV路徑), 用渴望窗口搜索, 減少搜索量
d. 對危險情況的搜索的加強

兩者差異原理分析
簡單概括TogaII的改進,那就是利用國際象棋的知識調整了fruit的搜索樹,對危險的盤面進行了更深的搜索,否則就剪掉.

首先，TogaII最有效的改進，是在葉子附近，利用history value把證明曾經無效的葉子節點丟棄掉，這是一個非常有效的演算法，這裡面的道理值得我們深思？為什麼我們不能夠發現一個這樣的演算法呢？

如果光是觀察futility和delta剪枝法, 我想肯定會有人對我提出疑問? 不是說這些根據子力情況剪掉的分支會漏掉殺棋步嗎? 為什麼還打開剪枝, OK, 我來一個簡單的回答, 假如已經是用了知識判斷過這類分支並不危險, 那就可以剪掉了.

TogaII能改進fruit的原因基於對國際象棋的深刻理解(也許是大量的測試的證明), 它的剪枝和延伸, 是相輔相成的, 如果有人想嘗試這個方向, 千萬不要只開剪枝或者只加延伸

這個方向, 是在搜索樹中, 加入對棋類知識的判斷. 調整搜索樹更適合某種棋規.

4. fruit演算法應用於中象引擎的分析及中象引擎演算法改進分析

下面的內容，是基於上述闡述的一些具體應用的例子，可對引擎做出一定的修正

a. nullmove改進

nullmove限制條件中, 當depth<=4時, 進入nullmove. 這種情況會忽略了depth=1可能產生的殺棋步, 當審局的知識缺乏該方面的內容時, 會漏掉殺棋步

這個時候, 可以根據自己引擎的審局知識的特點, 做depth=1的search_verify

代碼如下

if (depth<=4)
do_nullmove;

if (nullscore>=beta)
do_search_verify(depth=1);

這種方法可以避免一些殺棋情況的漏算, 這個也可以算是搜索和知識結合的一個典型例子吧

b. history pruning改進

考慮下面的情況

[炮]吃車1, 車2吃[炮], 車2移動, 和車1移動, 這兩個棋步, 會引起同樣的history value的減少, 雖然限制了history pruning發生在不吃子的情況, 但是, 中象的交換頻率遠>國象, 這種情況對fruit中historyvalue<9830就剪枝(60%)顯然不適合, 因為中象發生上面的情況要高多了, 而historyvalue<9834(60%)只要該棋步有一次被檢索的情況就會發生, 這個時候, 修正historyvalue<16384*45%, 可以有效減少誤判

c. futility剪枝及delta剪枝的意義分析

嗯, 這個, 首先參考TogaII和fruit對比的文章

futility和delta, 如果不會漏掉殺棋步, 或者, 在不會被對方殺死的情況, 非常有助於擴大自己的子力優勢, 這是這兩個剪枝法的機制決定的(注意，這兩個剪枝法的依據是擴大子力優勢，所以適用的范圍是有限的，對雙方對殺的盤面是會削弱攻擊能力的)

我建議使用這兩個剪枝法, 當然是建立在調整過搜索樹以後(避免在容易引發殺棋的盤面使用，常見的手段是判斷kingsafety，是否處於被攻擊狀態中)

中象棋軟搜索引擎揭密(三) fenon
d. 棋步排序的改進

從PVS搜索的原理出發, 搜索效率取決於搜索次序

常見的棋步排序是歷史步->吃子步->killer->etc, 這是基於最大化子力優勢的搜索, 當對殺時, 這種搜索排序效率是非常低的.

考慮killer棋步,如果能夠發生一個killer步的分數是殺棋步,那麼調整棋步排序為歷史步->killer->吃子步->etc,這樣就很好地把殺棋和吃子都結合起來了

5. fruit演算法和象眼的差異, 如何提高象眼的棋力
通過本篇的介紹, 希望能夠把開源的象眼程序, 改進到一個全新的高度, 假如有人希望一起完成象眼的改進, 請站內和我聯系

下面是我認為可以有效提高象眼棋力的幾個地方
a. 基於PV節點的nullmove pruning
b. qs加強
c. History pruning及TogaII剪枝法
d. 棋步排序
e. hash的改進
f. IID演算法修正
g.search root move list

6. 建立以kingsafety為核心的審局, 以及審局模型的詳細介紹

a. 對盤面區分階段, 不同階段採取的策略是不同的, 開中殘差異是很大的

實際上, 開局通過開局庫和子力位置分+若干簡單知識, 是很容易走出正確的棋步盤面的, 這個研究不深, 我更多是依賴開局庫解決這個問題

殘局時候, 調整位置分表, 判斷子力組合, 這個時候因為子力很少, 基本上難以進取, 更多是應該考慮防守, 控制搜索的危險程度和給予適當的分數, 很容易做到這點

中局是比較復雜的, 下面詳細說說我所理解的地方

b. 對某個階段的知識, 不要給引擎太多的選擇, 避免引擎找出多個PV路徑, 引起棋步的來回選擇, 如中局, 應該集中思考殺棋或者擴大子力的優勢

c. 上面1.講述了搜索和知識之間的關系, 其中也提及了depth=1時候的殺棋知識評估的重要性, 但是, 只是局限於depth=1的殺棋知識, 我們的盤面判斷力還是很有限的, 這個時候怎麼辦? 我們能不能對depth>=2的情況進行評估

我提供一個實踐的方法, 那就是分層次打分.

比如: 三子歸邊的判斷, 我們通過以下三種層次評分
(a) 有沉底炮, +分 (depth=3)
(b) 有沉底炮和車可做炮架, +分 (depth=2)
(c) 有沉底炮和車並且馬進入了可以助攻的區域, +分 (depth=1)

剛才在上面的審局和搜索的關系中，我列舉了4種知識，並且強調了知識只應該選擇有效的，下面分別說說哪些知識是必須的，不在下面列表內的知識，我都不做判斷了
a. 准確的殺型
利用位置分值提示車馬兵攻擊王周圍，依賴搜索完成
b. 模糊的殺型
(a) 當頭炮 (空頭炮,鎮中)
(b) 底炮 (三子歸邊)
(c) 雙車殺
c. 子力組合，只做會引起問題的子力組合判斷，如兌子後雙馬不佳
d. 某些特別容易出問題的知識的補充

7. 國際象棋Rybka的勝利以及將來棋軟發展的一些展望

一些未來的研究方向, 所以個人的意見應該是一些胡言亂語,僅作笑料

上面所說的一切, 都是基於知識會有一個確定的分數, 但是, 這明顯是錯誤的, 誰能說三子歸邊是400分,而不是395分呢? 有沒有一種方法, 可以動態評估這個分數, 從而達到知識的最優化呢?

第二,傳說中的根據知識排序棋步的方法

在國外流行的認為Rybka超越其他軟體的原因是因為更聰明的搜索和知識, 從作者言論和Rybka反映的信息做一個猜測(nps超低, 搜索准確度超高), 一致認為Rybka在搜索和評估中, 都採取了全新的方法

其中一個流派3moves現在被認為是Rybka最有可能採取的方法(包含了我的理解補充)

什麼是3moves? 首先, 當前盤面移動一步, 對可以攻擊的子,計算3步內可以攻擊的點集,這個點集每個點都有權重.那麼,多個攻擊子做交集的時候, 密度最高權重最高的區域, 就是當前盤面最容易攻擊的位置, 這表明了這一個棋步的攻擊能力
當這個棋步能攻擊到王或者其他子時, 這自然就是一個好的棋步,這時候根據點集的情況進行算分,自然是非常准確的.

這種方法超越了子力表和知識分數的局限, 而且更好理解了棋規, 也難怪被認為是最有可能的

以上轉載，不知是否你想要的？