人工智能實(shí)驗(yàn)報(bào)告.doc

安陽師范學(xué)院 數(shù)據(jù)庫高級(jí)應(yīng)用課外實(shí)踐報(bào)告 人工智能課外實(shí)踐報(bào)告項(xiàng) 目 名 稱： 剪枝法五子棋 所 在 班 級(jí)： 2013級(jí)軟件工程一班 小 組 成 員：李曉寧、白明輝、劉小晶、袁成飛、程小蘭、李喜林指 導(dǎo) 教 師： 薛笑榮 起 止 時(shí) 間： 2016-5-102016-6-18 項(xiàng)目基本信息項(xiàng)目名稱五子棋項(xiàng)目簡介 智力小游戲作為人們?nèi)粘Ｐ蓍e娛樂的工具已經(jīng)深入人們的生活，五子棋更成為了智力游戲的經(jīng)典，它是基于AI的剪枝法和極小極大值算法實(shí)現(xiàn)的人工智能游戲，讓人們能和計(jì)算機(jī)進(jìn)行對(duì)弈。 這個(gè)項(xiàng)目我們實(shí)現(xiàn)了當(dāng)人點(diǎn)擊“開始”按鈕時(shí)，開始下棋，當(dāng)人的棋子落時(shí)，計(jì)算機(jī)會(huì)根據(jù)算法進(jìn)行最佳路徑計(jì)算，然后落子下棋。任何一方贏了都會(huì)彈出哪方贏了。然后單擊重新開始。任務(wù)分工李曉寧 130904021 白明輝 130904001：負(fù)責(zé)界面實(shí)現(xiàn)和估值函數(shù)設(shè)計(jì) 文檔整理劉小晶 130904032 袁成飛 130904051：負(fù)責(zé)極小極大值算法的設(shè)計(jì)與實(shí)現(xiàn) 李喜林 130904019 程小蘭 130904004：負(fù)責(zé)剪枝法的設(shè)計(jì)與實(shí)現(xiàn)一、 系統(tǒng)分析1.1背景1.1.1 設(shè)計(jì)背景 智力小游戲作為人們?nèi)粘Ｐ蓍e娛樂的工具已經(jīng)深入人們的生活，五子棋更成為了智力游戲的經(jīng)典，它是基于AI的剪枝法和極小極大值算法實(shí)現(xiàn)的人工智能游戲，讓人們能和計(jì)算機(jī)進(jìn)行對(duì)弈。 能使人們?cè)谂c電腦進(jìn)行對(duì)弈的過程中學(xué)習(xí)五子棋，陶冶情操。并且推進(jìn)人們對(duì)AI的關(guān)注和興趣。1.1.2可行性分析通過研究，本游戲的可行性有以下三方面作保障（1）技術(shù)可行性本游戲采用Windows xp等等系統(tǒng)作為操作平臺(tái)，使用人工智能進(jìn)行算法設(shè)計(jì)，利用剪枝法進(jìn)行編寫，大大減少了內(nèi)存容量，而且不用使用數(shù)據(jù)庫，便可操作，方便可行，因此在技術(shù)上是可行的。（2）經(jīng)濟(jì)可行性開發(fā)軟件：SublimText（3）操作可行性該游戲運(yùn)行所需配置低、用戶操作界面友好，具有較強(qiáng)的操作可行性。1.2數(shù)據(jù)需求 五子棋需要設(shè)計(jì)如下的數(shù)據(jù)字段和數(shù)據(jù)表：1. 2.1 估值函數(shù)： 估值函數(shù)通常是為了評(píng)價(jià)棋型的狀態(tài)，根據(jù)實(shí)現(xiàn)定義的一個(gè)棋局估值表，對(duì)雙方的棋局形態(tài)進(jìn)行計(jì)算，根據(jù)得到的估值來判斷應(yīng)該采用的走法。棋局估值表是根據(jù)當(dāng)前的棋局形勢(shì)，定義一個(gè)分值來反映其優(yōu)勢(shì)程度，來對(duì)整個(gè)棋局形勢(shì)進(jìn)行評(píng)價(jià)。本程序采用的估值如下： 狀態(tài)眠二假活三眠三活二沖四假活三活三活四連五 分值 2 4 5 8 12 15 40 90 200一般來說，我們采用的是1515的棋盤，棋盤的每一條線稱為一路，包括行、列和斜線，4個(gè)方向，其中行列有30路，兩條對(duì)角線共有58路，整個(gè)棋盤的路數(shù)為88路。考慮到五子棋必須要五子相連才可以獲勝，這樣對(duì)于斜線，可以減少8路，即有效的棋盤路數(shù)為72路。對(duì)于每一路來說，第i路的估分為E(i)=Ec(i)-Ep(i)，其中Ec(i)為計(jì)算機(jī)的i路估分，Ep(i)為玩家的i路估分。棋局整個(gè)形勢(shì)的估值情況通過對(duì)各路估分的累加進(jìn)行判斷，即估值函數(shù)： 72 F（n）= E(i) i=11.2.2 極小極大值算法: 極大極小搜索算法就是在博弈樹在尋找最優(yōu)解的一個(gè)過程，這主要是一個(gè)對(duì)各個(gè)子結(jié)點(diǎn)進(jìn)行比較取舍的過程，定義一個(gè)估值函數(shù)F(n)來分別計(jì)算各個(gè)終結(jié)點(diǎn)的分值，通過雙方的分值來對(duì)棋局形勢(shì)進(jìn)行分析判斷。以甲乙兩人下棋為例，甲為max，乙為min。當(dāng)甲走棋時(shí)，自然在博弈樹中尋找最大點(diǎn)的走法，輪到乙時(shí)，則尋找最小點(diǎn)的走法，如此反復(fù)，這就是一個(gè)極大極小搜索過程，以此來尋找對(duì)機(jī)器的最佳走法。1.2.3. 剪枝法: 剪枝算法簡單來說，就是在搜索過程中減少一定的冗余現(xiàn)象，如已經(jīng)找到極大值，執(zhí)行該走法就可以獲勝，則無須再往下進(jìn)行搜索比較，此過程即為剪枝。對(duì)于極大的MAX結(jié)點(diǎn)，稱為剪枝；反之為剪枝。具體規(guī)則可以簡單描述如下： 剪枝：對(duì)于極大值層結(jié)點(diǎn)的值如果不小于它的任一祖先極小值層結(jié)點(diǎn)的值，即(后續(xù)層)(祖先層)，則可中止該極大值層中這個(gè)MAX節(jié)點(diǎn)以下的搜索過程，這個(gè)MAX節(jié)點(diǎn)最終的倒推值就確定為這個(gè)值。 剪枝：對(duì)于極小值結(jié)點(diǎn)層的值如果不大于它任一祖先極大值層結(jié)點(diǎn)的值，即(祖先層)(后續(xù)層)，則可中止對(duì)該極小值層中這個(gè)MIN節(jié)點(diǎn)以下結(jié)點(diǎn)的搜索，這個(gè)MIN節(jié)點(diǎn)最終的倒推值就確定為這個(gè)值。2剪枝可以進(jìn)一步進(jìn)行改進(jìn)，在走棋過程中，在中心先下的一方往往有一定的優(yōu)勢(shì)，雙方的搏斗糾纏都是在爭奪最佳位置，可以考慮從中心往外螺旋進(jìn)行擴(kuò)展搜索；另外由于防守的需要，落子的位置通常也是在彼此下子的附近，因此可以優(yōu)先考慮在這些位置進(jìn)行搜索，也就是對(duì)落子位置進(jìn)行排序預(yù)先搜索，更進(jìn)一步的縮減冗余現(xiàn)象，進(jìn)而提高搜索效率和行棋質(zhì)量。1.3事務(wù)需求此游戲主要應(yīng)用于人類與計(jì)算機(jī)的對(duì)弈功能。具體功能如下所述：1. 人：點(diǎn)擊開始 找位置 下棋2. 計(jì)算機(jī)：算法設(shè)計(jì) 最佳位置搜索 下棋 3.規(guī)則：五子成珠，先者為勝。1.4完整性及安全性要求 系統(tǒng)的安全性對(duì)系統(tǒng)是否正常使用具有重要意義，為了實(shí)現(xiàn)游戲的安全性，在程序設(shè)計(jì)方面主要采用兩個(gè)步驟:一是操作平臺(tái)的兼容性，二是代碼實(shí)現(xiàn)的安全性。操作平臺(tái)的兼容性:為了防止有的瀏覽器因?yàn)椴患嫒荻a(chǎn)生錯(cuò)誤和系統(tǒng)安全，我們做了瀏覽器的兼容性檢測。代碼實(shí)現(xiàn)的安全性:為了防止一些代碼執(zhí)行存在的風(fēng)險(xiǎn)，我們應(yīng)用最安全，最原生態(tài)的JS來實(shí)現(xiàn)界面和算法的實(shí)現(xiàn)。二、游戲?qū)崿F(xiàn)2.1 開發(fā)環(huán)境2.1.1硬件環(huán)境開發(fā)過程中，所使用的硬件環(huán)境：計(jì)算機(jī)一臺(tái)2.1.2 軟件環(huán)境 在以上硬件的基礎(chǔ)上，開發(fā)系統(tǒng)必須所具備的軟件系統(tǒng)，應(yīng)該包括以下幾個(gè)方面：操作平臺(tái)：Microsoft Windows xp開發(fā)語言：HTML5 CSS3 javascript 2.2系統(tǒng)流程圖根據(jù)系統(tǒng)模塊，得出總系統(tǒng)流程圖如下： 總體流程圖： 2.3用JSP實(shí)現(xiàn)的界面1、 主界面2、 開始電腦下棋3、一輪之后4、 人勝利5、電腦勝利6、人悔棋7、人認(rèn)輸三、問題及解決方法1.在編寫代碼時(shí)發(fā)現(xiàn)代碼明明沒有錯(cuò)誤，可就是運(yùn)行不出來，結(jié)果就不得不重新敲一次，最后才發(fā)現(xiàn)標(biāo)點(diǎn)符號(hào)不是在英文狀態(tài)下。2.在使用插件和JS的框架時(shí)出現(xiàn)兼容問題，在討論和搜索方法之后，好不容易搞定了。 總的來說，本游戲整體性能不夠完整，安全系數(shù)一般,并不是那么完整，但是根據(jù)我們的努力，還是解決了一部分的問題。四、課外實(shí)踐總結(jié)這一學(xué)期剛開始，老師就布置下此次課外實(shí)踐的任務(wù)，但當(dāng)時(shí)我們并不在意，想著還早，再加上剛接觸這門學(xué)科，根本不知從何入手，直到最后，再過幾天就要交作品了，我們才真正慌起來，對(duì)于五子棋我們是熟悉的，但沒想到運(yùn)用AI的剪枝法做起來是那么難，因?yàn)樗惴ǖ脑O(shè)計(jì)如果不完全就會(huì)導(dǎo)致出現(xiàn)粗物，還有內(nèi)存溢出問題，剛開始我們組的同學(xué)就像無頭蒼蠅一樣亂撞，總是找不到重心，通過大家一致的研究算法本身和集體討論估值函數(shù)的設(shè)計(jì)，然后上網(wǎng)查資料，我們?cè)O(shè)計(jì)了算法，然后不斷的優(yōu)化修改，終于達(dá)到理想效果，然后開始實(shí)現(xiàn)代碼