人工智能是近年來很活躍的研究領域之一。計算機博弈是人工智能研究的一個重要分支,它的研究為人工智能帶來了很多重要的方法和理論,產生了廣泛的社會影響和學術影響。國內外對博弈的研究已經較為廣泛,特別是IBM的國際象棋程序“深藍”,已經達到了人類的世界冠軍水平。“深藍”的研究成果,特別是基于剪枝的極大極小樹搜索技術為設計其它的計算機棋類博奕系統(tǒng)提供了良好的參照。但是不同的棋類博奕,其規(guī)則的千差萬別賦予了每一種棋類博奕特殊的專業(yè)知識。這就必然要求設計一個具體的棋類博奕系統(tǒng)時應該深入研究它的基本原理和內在規(guī)律。 本文以計算機五子棋博奕系統(tǒng)做為研究課題,在對大量的相關文獻進行分析研究的基礎上,首先按照人工智能和計算機博奕的一般原理設計了一個五子棋博奕系統(tǒng)的基本模型,所做的工作包括三個方面: 第一研究了五子棋在計算機中的表示問題,討論了計算機中存貯棋局和識別下棋次序,局勢狀態(tài)變化及局勢特征、走法產生等方法。 第二研究了博弈樹的極小極大搜索技術及在此基礎上的Alpha-Beta剪枝過程和剪枝優(yōu)化問題。實現將候選的后繼節(jié)點按位置鄰近順序排序,使剪枝過程得到優(yōu)化。此外還研究了Alpha-Beta剪枝的改進算法NegaScout算法,此算法首先采用一小的有限Alpha-Beta窗口,以確定實際估計值的范圍,再在這個較小的范圍中搜索實際的估計值。由于在較小的范圍中搜索,效率能得以提高。 第三根據五子棋的特點,提取棋局局勢的若干特征,對這些特征賦加權分,并對整個棋局進行特征統(tǒng)計,采用一個線性函數求得棋局的總估計分值。實踐中,采用極小極大搜索加此靜態(tài)估值技術的初版程序,達到了比初學者強的水平,一些比較熟練的業(yè)余人員時常也會負于此程序。 在上述工作的基礎上,本文的創(chuàng)新性研究主要包括以下兩個方面: 第一對五子棋博奕的專業(yè)知識進行了認真的整理,針對五子棋博奕規(guī)則簡單、局勢判斷清楚的特點,對五子棋常見的開局、定式及其后的對局做了細致的統(tǒng)計分析,闡明了五子棋對奕中黑白雙方優(yōu)劣勢并非均衡的規(guī)律,這一規(guī)律作為一個指導原則在設計五子棋博奕系統(tǒng)時起到重要作用。 第二針對初版程序中存在的缺點和不足,通過查找原因,實現了算法的優(yōu)化和加強。初版程序在運行時其搜索速度和對奕表現不能讓人滿意。其主要原因有兩個:使用常規(guī)的Alpha-Beta搜索和NegaScout算法不能避免相同局面的重復節(jié)點的搜索,從而影響搜索速度;采用固定的估值法,估值的不準確使其“智力”較低,而且固定的賦值方式使其不能在對奕過程中提高棋力。解決的方法有兩個:在執(zhí)行常 

 

 

【學位級別】：碩士

 

頁數：59

 

中文摘要

Abstract (英文摘要)

第一章 緒論

    1.1 選題背景

    1.2 計算機博弈研究簡史

    1.3 計算機博弈的研究意義

    1.4 計算機博奕的過程

    1.5 五子棋發(fā)展簡史與基本知識介紹

    1.6 課題主要工作

第二章 五子棋博奕的理論研究

    2.1 五子棋博奕的不同形式

    2.2 五子棋博奕黑白雙方優(yōu)劣勢的分析

    2.3 策略的選擇

第三章棋盤狀態(tài)空間表示與走法產生

    3.1 棋盤局勢狀態(tài)表示

    3.2 棋盤中下棋的順序表示

    3.3 狀態(tài)的變化

    3.4 特征的表示

    3.5 走法的產生

第四章 博弈樹的搜索技術

    4.1 極大極小樹搜索算法

    4.2 Alpha-Beta 剪枝過程

    4.3 Alpha-Beta 剪枝存在的問題及優(yōu)化

    4.4 NegeScout 搜索

第五章 靜態(tài)估值函數

    5.1 棋盤局勢特征

    5.2 估值

    5.3 靜態(tài)估值函數的不足及實踐效果

第六章 搜索算法的優(yōu)化與增強

    6.1 置換表的搜索

        6.1.1 哈希表

        6.1.2 應用置換表的其它問題

        6.1.3 Zobrist 技術

    6.2 威脅空間搜索

        6.2.1 專業(yè)術語和“威脅次序”

        6.2.2 人類專業(yè)棋手的分析

        6.2.3 計算機程序的策略

        6.2.4 人與計算機

        6.2.5 威脅空間搜索

        6.2.6 算法優(yōu)化后效果的檢驗

參考文獻

致謝

在讀期間發(fā)表的論文和