人工智能五子棋論文

人工智能五子棋論文人工智能五子棋論文本文將這些技術(shù)用于五子棋中。設(shè)計(jì)了一個(gè)智能五子棋系統(tǒng)，實(shí)現(xiàn)人和計(jì)算機(jī)兩方進(jìn)行博弈。下面是學(xué)習(xí)啦我整理共享的關(guān)于人工智能五子棋論文的相關(guān)文章，歡迎瀏覽!人工智能五子棋論文篇一智能五子棋博弈算法研究摘要：人工智能是一門正在迅速發(fā)展的新興的綜合性很強(qiáng)的邊緣科學(xué)。博弈是人工智能的主要研究領(lǐng)域之一，他涉及人工智能中的推理技術(shù)、搜索方法和決策規(guī)劃。本文將這些技術(shù)用于五子棋中。設(shè)計(jì)了一個(gè)智能五子棋系統(tǒng)，實(shí)現(xiàn)人和計(jì)算機(jī)兩方進(jìn)行博弈。關(guān)鍵詞：五子棋人工智能搜索人工智能是一門綜合性很強(qiáng)的邊緣科學(xué)，它研究怎樣使計(jì)算機(jī)去做那些過去只能靠人的智力才能做的工作。而博弈是人工智能研究的一個(gè)重要分支，它不僅存在于游戲、下棋之中，也存在于政治、經(jīng)濟(jì)、軍事和生物競(jìng)爭(zhēng)中。五子棋是起源于中國古代的傳統(tǒng)黑白棋種之一。當(dāng)代五子棋日文稱之為“連珠〞，英譯為“Ren-ju〞，英文稱之為“Gobang〞或“FIR〞(FiveinaRow的縮寫)，亦有“連五子〞、“五子連〞、“串珠〞、“五目〞、“五目碰〞、“五格〞等多種稱謂。與其他棋類相比，五子棋每一層搜索節(jié)點(diǎn)數(shù)量龐大，因而盤面預(yù)測(cè)的計(jì)算量是非常大的，比方對(duì)于五子棋的中盤走法中，假如要預(yù)測(cè)四步的局面數(shù)的話能夠到達(dá)一百萬。本文是對(duì)五子棋算法的設(shè)計(jì)原理和實(shí)現(xiàn)方法進(jìn)行討論和研究，主要包括數(shù)據(jù)構(gòu)造、搜索算法和優(yōu)劣評(píng)價(jià)函數(shù)組成，主要的特點(diǎn)包括快速的數(shù)據(jù)構(gòu)造設(shè)計(jì)實(shí)現(xiàn)、以及高效率的搜索算法和盡可能的模擬人類的智能。1、棋局的數(shù)據(jù)構(gòu)造表示我們知道五子棋的走法中有優(yōu)先和禁手，如連四肯定是沒有三四優(yōu)先，而假如是黑方出現(xiàn)三三(包括“四、三、三〞)、四四(包括“四、四、三〞)，而黑方只能以四三取勝，假如黑方走出禁手則是輸;五連與禁手同時(shí)構(gòu)成，先五為勝，等等的規(guī)矩。但是電腦畢竟不是人類，能夠類人但是卻不能夠本人考慮，那么就需要給電腦一個(gè)它能夠明白的評(píng)判標(biāo)準(zhǔn)。下面，我列出基本的棋型優(yōu)先順序：造一個(gè)二hellip;hellip;造四個(gè)二沖三hellip;hellip;沖兩個(gè)二和一個(gè)三沖雙三沖四沖四三。之所以這么設(shè)置是由于五子棋的下法所致，只要構(gòu)成5顆一線就贏了，所以講一條線上構(gòu)成的越多那么就有優(yōu)勢(shì)，當(dāng)然就是棋數(shù)越多，分越多。那么為了讓電腦明確的知道是不是應(yīng)該落子，就給它一個(gè)標(biāo)準(zhǔn)：分值。用程序語言表示：enumValue{FAILED=-99999，SKIP=20，LENG=10，TWO=100，THREE=1000，IF0UR=10000，F(xiàn)OUR=50000，SF0UR=70000，WIN=100000};假如某一點(diǎn)導(dǎo)致失敗，則分值為FAILED，由于它足夠小，所以無論任何棋型與它的組合都小于0，SKIP之所以給它20分，是為了避免電腦出現(xiàn)無棋可下的情況，LENG是有可能發(fā)生長連的點(diǎn)，這有可能導(dǎo)致禁手，TWO、THREE、FOUR、WIN觀名知意，TFOUR和SFOUR分別是弱四和強(qiáng)四。強(qiáng)四的點(diǎn)比普通的沖四重要的多，比方一個(gè)活四，意味著即將判出勝負(fù)。弱四是為了提供更大的靈敏。也許有某種沖四并不一定比沖三重要，我在這里并沒有使用，以后能夠擴(kuò)大。2、五子棋算法介紹及初步實(shí)現(xiàn)2.1五子棋博弈樹中的極大極小搜索和alpha;-beta;剪枝為了使議論更有條理性[5]，將博弈的雙方分別命名為MAX和MIN。而搜索的任務(wù)是為MAX找最佳的移動(dòng)。假設(shè)MAX先移動(dòng)(此時(shí)暫時(shí)不考慮五子棋的禁手等規(guī)則)，然后2個(gè)博弈者輪流移動(dòng)。因而，深度為偶數(shù)的節(jié)點(diǎn)，對(duì)應(yīng)于MAX下一步移動(dòng)的位置，稱為MAX節(jié)點(diǎn);深度為奇數(shù)的節(jié)點(diǎn)對(duì)應(yīng)于MIN下一步移動(dòng)的位置，稱為MIN節(jié)點(diǎn)(博弈樹的頂節(jié)點(diǎn)深度為0)。k層包括深度為2k和2k+1的節(jié)點(diǎn)。通常用層數(shù)表示博弈樹的搜索深度。他能夠表示出向前預(yù)測(cè)的MAX和MIN交替運(yùn)動(dòng)的回合數(shù)。用整個(gè)棋盤估值的函數(shù)h(n)為靜態(tài)估值函數(shù)。設(shè)想當(dāng)前棋局S為輪到計(jì)算機(jī)方下棋(用方框表示)，任選一空點(diǎn)作為計(jì)算機(jī)方的下棋位置(可有若干種選擇)，接著考慮在此情況下游戲者一方下棋的棋局(用圓圈表示);從某一個(gè)圓圈棋局出發(fā)，任選一空點(diǎn)作為游戲者一方的落子處(又有若干種選擇)。再次構(gòu)成計(jì)算機(jī)方下棋的方框棋局;依此類推，這樣可構(gòu)成一棵以S為根結(jié)點(diǎn)的博弈樹，該樹以圓圈棋局為第2層子結(jié)點(diǎn)，以方框棋局為第3層子結(jié)點(diǎn)等等。假如繼續(xù)向前搜索，可構(gòu)成多層子結(jié)點(diǎn)，如今以向前搜索3層子結(jié)點(diǎn)為例來講明極大極小值的經(jīng)過。對(duì)第3層子結(jié)點(diǎn)的某一棋局n，求出其估計(jì)值h(n)，假設(shè)有一博弈樹已構(gòu)成，如圖1所示[2]，h(n)的值由各結(jié)點(diǎn)旁的數(shù)值給出。根據(jù)極小極大化分析法，先計(jì)算第3層子結(jié)點(diǎn)h(n)值，然后第2層子結(jié)點(diǎn)的估計(jì)值取他的各后繼子結(jié)點(diǎn)的極小值，根結(jié)點(diǎn)的估計(jì)值取他的各子結(jié)點(diǎn)的極大值。這個(gè)獲得最大估計(jì)值的子結(jié)點(diǎn)即為從S出發(fā)的計(jì)算機(jī)方的最佳落子方案。棋盤上某一行、某一列或某一對(duì)角線為一路，這里使用的棋盤為19行19列，因而，行和列方向上共有19+19=38路;從左下到右上方向的對(duì)角線有37路，同樣，從左上到右下方向的對(duì)角線也有37路。但對(duì)于五子棋來講必須在一條直線上有連續(xù)五個(gè)棋子才能贏。因而，在對(duì)角線上就能夠減少8路。所以，整個(gè)棋盤路的總數(shù)為：38+(37-8)+(37-8)=96路。對(duì)某一棋局n[14-15]，第i路得分：h(i)=h(i)t-hm(i)[1]。我們不用把每個(gè)節(jié)點(diǎn)都搜索一遍可以獲得和極大極小搜索同樣結(jié)果的走步，不搜索分支節(jié)點(diǎn)而舍棄該分支的經(jīng)過叫剪枝。常用的剪枝方法是alpha;-beta;剪枝算法。在極大極小搜索的經(jīng)過中，存在著一定程度的數(shù)據(jù)冗余。如下列圖2所示左半部的一棵極大極小樹的片斷，節(jié)點(diǎn)下面為該節(jié)點(diǎn)的值，設(shè)A為極大值節(jié)點(diǎn)，節(jié)點(diǎn)B的值為18，節(jié)點(diǎn)D的值為16，由此能夠判定節(jié)點(diǎn)C的值將小于等于16(取極小值);而節(jié)點(diǎn)A的值為節(jié)點(diǎn)Max(B，C)，是18，也就是講不再需要估節(jié)點(diǎn)C的其他子節(jié)點(diǎn)如E、F的值就能夠得出父節(jié)點(diǎn)A的值了。這樣將節(jié)點(diǎn)D的后繼兄弟節(jié)點(diǎn)減去稱為Alpha剪枝(alpha;剪枝)。如圖2：同樣道理在圖3右半部一棵極大極小樹的片段中，設(shè)A為極小值節(jié)點(diǎn)，節(jié)點(diǎn)B的估值為8，節(jié)點(diǎn)D的估值為l8，由此能夠判定節(jié)點(diǎn)C的值將大于等于18(取極大值);而節(jié)點(diǎn)A的值為Min(B，c)，是8。也就是講不再需要求節(jié)點(diǎn)C的其他子節(jié)點(diǎn)如E、F值就能夠得出父節(jié)點(diǎn)A的值了。這樣將節(jié)點(diǎn)D的后繼兄弟節(jié)點(diǎn)剪去稱為Beta剪枝(beta;剪枝)。如圖3：將Alpha剪枝和Beta剪枝參加極大極小搜索，就得到alpha;-beta;搜索算法。如今假設(shè)五子棋問題深度為3的搜索樹給出alpha;-beta;剪枝算法，用類C語言對(duì)其進(jìn)行描繪：設(shè)電腦為Max，人為Min，初始時(shí)alpha;為-infin;，beta;為+infin;;函數(shù)Evalue()返回對(duì)當(dāng)前局面的估值在p處下黑子;if(已到達(dá)搜索的最后一層)returnEvalue();假如Max(pointp，alpha;，beta;)函數(shù)，則返回對(duì)Max結(jié)點(diǎn)最有利的走步的局勢(shì)靜態(tài)估值函數(shù)值。反之Min(pointp，alpha;，beta;)函數(shù)，則返回對(duì)Min結(jié)點(diǎn)最有利的局勢(shì)靜態(tài)估值函數(shù)值。兩種互為遞歸調(diào)用，能夠動(dòng)態(tài)改變搜索深度。2.2優(yōu)化估值函數(shù)通過以上的研究能夠看出，在博弈的程序中電腦的行為都是以估值函數(shù)為根據(jù)的，所以講估值函數(shù)在很大的程度上是決定了電腦的棋力高低。我們能夠采用遺傳算法來改良靜態(tài)估值。遺傳算法的優(yōu)點(diǎn)：(1)由于搜索算法是從問題的解開場(chǎng)的，而不是一組參數(shù)。所以被局部震蕩干擾導(dǎo)致求最優(yōu)解失敗的可能性大大減小。(2)此算法能將搜索重點(diǎn)集中于性能高的部分，能較快地求出最佳的參數(shù)。遺傳算法的優(yōu)化估值參數(shù)的經(jīng)過：首先是①隨機(jī)產(chǎn)生幾組參數(shù)作為初始種群;接著②對(duì)種群的參數(shù)進(jìn)行收斂判定，收斂則③輸出優(yōu)化結(jié)果并且評(píng)估經(jīng)過結(jié)束，否則就④執(zhí)行復(fù)制操作產(chǎn)生一組新參數(shù);然后⑤取0、1之間的隨機(jī)數(shù)，讓隨機(jī)數(shù)和穿插概率進(jìn)行比擬;若大于⑥則執(zhí)行穿插操作改變新參數(shù)，若小于就不用執(zhí)行這一步;⑦接著取0、1之間的隨機(jī)數(shù)，隨機(jī)數(shù)和變異概率進(jìn)行比擬，若⑧大于就執(zhí)行變異操作改變新參數(shù)，小于就不執(zhí)行這一步;接著是⑨把較差的一組參數(shù)從種群中去除;接著跳回第二步判定能否已經(jīng)收斂，如此循環(huán)就能將搜索重點(diǎn)集中于性能高的部分，能較快地求出最佳的參數(shù)。畫圖4表示如下：2.3禁手特征計(jì)算五子棋中還有項(xiàng)規(guī)則就是是禁手的判定，在上邊已經(jīng)給出了3顆棋子的時(shí)候的分值為1000。假如是雙三則需要乘以2，即2000。電腦在分值表中將會(huì)判定雙三點(diǎn)比一個(gè)三的點(diǎn)更為重要。這在電腦進(jìn)行全局判定的時(shí)候也是正確的，可是假如電腦執(zhí)黑子，這一點(diǎn)是不能落子的，否則將導(dǎo)致失敗。但是電腦不能真的會(huì)本人去判定，只要以為的給他一個(gè)判定的標(biāo)準(zhǔn)，處理的方法是：在累加分值的時(shí)候增加一個(gè)判定語句，假如正好構(gòu)成雙三，那么這一點(diǎn)不參加分值表同時(shí)判定此點(diǎn)落棋將判為負(fù)，其他禁手按同樣的方法處理。3、結(jié)論及瞻望將來3.1總結(jié)本文介紹了應(yīng)用人工智能設(shè)計(jì)五子棋的總體方法。用極大極小值的經(jīng)過以及啟發(fā)式搜索的方法，采用靜態(tài)估值函數(shù)對(duì)各節(jié)點(diǎn)的代價(jià)進(jìn)行估計(jì)，應(yīng)用遺傳算法對(duì)估計(jì)的值進(jìn)行了優(yōu)化，克制了人為主觀因素的片面性。對(duì)博弈的研究具有一定的借鑒意義。在實(shí)際五子棋系統(tǒng)的設(shè)計(jì)中。應(yīng)用本方法只向前搜索了三步，就能夠獲得很好的效果。可以以增加搜索的深度來提高系統(tǒng)的判定能力，但是是以犧牲電腦的運(yùn)算速度為前提的，畢竟加深搜索的話就需要更大的運(yùn)算量。此外，可以以通過增加機(jī)器學(xué)習(xí)，比方電腦對(duì)棋局進(jìn)行記憶，在對(duì)手落子之前對(duì)棋局和之前記憶的棋局進(jìn)行比擬，先判定出更優(yōu)的走法，就能夠進(jìn)一步提高系統(tǒng)的智能。3.2將來瞻望隨著IntelHP(超線程技術(shù))的實(shí)現(xiàn)和將來多處理器PC機(jī)的普及.對(duì)于數(shù)據(jù)計(jì)算量大的人機(jī)對(duì)弈問題必然要求應(yīng)用并行的思想去處理。超快搜索速度和必要的復(fù)盤“反思〞必然帶給下棋電腦更多智慧。參考文獻(xiàn)：[1]蔡自興.人工智能及其應(yīng)用[M].北京：清華大學(xué)出版社，1999[2]閻平凡.人工神經(jīng)網(wǎng)絡(luò)與模擬進(jìn)化計(jì)算[M].北京：清華大學(xué)出版社，2002[3]王小春.游戲編程(人機(jī)博弈)[M].重慶：重慶大學(xué)出版社，2002[4]NilsJNilsson，鄭扣根，莊越挺譯.ArtificialIntelligenceANewSynthesis[M].北京：機(jī)械工業(yè)出版社，2000[5]陳爾紹.傳感器實(shí)用裝置制作集錦[M].北京：人民郵電出版社，1999[6]鄧天炎，李愛華，尹正主編.離散數(shù)學(xué)教程[M].徐州：中國礦業(yè)大學(xué)出版社，2002[7]潘金貴，顧鐵成，曾儉等編譯.當(dāng)代計(jì)算機(jī)常用數(shù)據(jù)構(gòu)造和算法[M].南京：南京大學(xué)出版社，1994[8]王小平.遺傳算法-理論應(yīng)用與軟件實(shí)現(xiàn)[M].西安：西安交通大學(xué)出版社，1998[9]王永慶.人工智能原理與方法[M].西安：西安交通大學(xué)出版社，1998[10]林堯瑞，馬