象棋殘局回溯分析演算法之實作與評估

Abstract

電腦象棋的程式設計中，可分為知識庫設計與對局搜尋兩個方向[7.8.9]。在象棋殘局裏，對於一般的審局函數，棋局往往要十餘回合的推衍方能判斷適當的著手，是故一般的對局搜尋法效果有限。本文提出一個依回溯分析(Retrograde Analysis)[3.5.6]演算法設計的殘局知識庫系統，用來解決一般性的象棋殘局問題。 本系統使用回溯的方式，先建構最基本的殘局資料，依序建構複雜度較高的殘局知識庫。此殘局系統具有完全資訊的特性，即對於知識庫中有記載的殘局，都能明確的知道其正確的勝負狀態與最佳的著手。且知識庫系統是電腦自動建構，故不須要有豐富的專家知識。目前在一般常見的殘局如單馬對單士，炮仕對雙士與單車對士象全等表現良好。