中國象棋機器博弈數據結構設計與搜索算法研究.pdf

1、人工智能(AI)是計算機知識、心理學和哲學等知識的綜合體現。中國象棋的計算機博弈屬于人工智能的研究范疇。目前黑白棋、五子棋、國際象棋等棋類的計算機博弈已經取得了成功,而博弈樹更為龐大的中國象棋計算機博弈尚處于萌芽階段。本課題結合在中國象棋機器博弈方面的實踐經驗,對中國象棋計算機博弈做了詳細的分析和研究,主要做了以下工作： 首先,設計了中國象棋計算機博弈軟件的數據結構,對馬和象的著法生成采用模版匹配法,并且根據路向行向比特向量對車

2、、炮等棋子的著法生成采用預置表法。由于采用模版匹配法和預置表法省去了棋子邊界的判斷,并且利用查詢代替搜索,提高了著法生成的速度,進而提高了整個博弈樹的搜索效率,該部分的工作是整個程序的基礎。 另外,研究了博弈樹的搜索算法。在alpha-beta搜索算法的基礎上,采用極小窗口(PVS)、置換表啟發(fā)、歷史表啟發(fā)、靜態(tài)啟發(fā)等啟發(fā)算法,有效的提高了搜索的效率；采用靜態(tài)搜索、選擇性延伸等手段,避免了在葉子節(jié)點由于棋子交換、將軍等因素導致的