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

 

 

【學(xué)位級(jí)別】：碩士

 

頁數(shù)：59

 

中文摘要

Abstract (英文摘要)

第一章 緒論

    1.1 選題背景

    1.2 計(jì)算機(jī)博弈研究簡史

    1.3 計(jì)算機(jī)博弈的研究意義

    1.4 計(jì)算機(jī)博奕的過程

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

    1.6 課題主要工作

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

    2.1 五子棋博奕的不同形式

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

    2.3 策略的選擇

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

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

    3.2 棋盤中下棋的順序表示

    3.3 狀態(tài)的變化

    3.4 特征的表示

    3.5 走法的產(chǎn)生

第四章 博弈樹的搜索技術(shù)

    4.1 極大極小樹搜索算法

    4.2 Alpha-Beta 剪枝過程

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

    4.4 NegeScout 搜索

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

    5.1 棋盤局勢特征

    5.2 估值

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

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

    6.1 置換表的搜索

        6.1.1 哈希表

        6.1.2 應(yīng)用置換表的其它問題

        6.1.3 Zobrist 技術(shù)

    6.2 威脅空間搜索

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

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

        6.2.3 計(jì)算機(jī)程序的策略

        6.2.4 人與計(jì)算機(jī)

        6.2.5 威脅空間搜索

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

參考文獻(xiàn)

致謝

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