中國(guó)象棋機(jī)器博弈數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)與搜索算法研究.pdf

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

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