北京市大學(xué)生科學(xué)研究與創(chuàng)業(yè)行動(dòng)計(jì)劃

北京市大學(xué)生科學(xué)研究與創(chuàng)業(yè)行動(dòng)計(jì)劃立項(xiàng)申請(qǐng)書基于UCT搜索算法的亞馬遜棋人機(jī)博弈軟件的設(shè)計(jì)與實(shí)現(xiàn)團(tuán)隊(duì)成員：侯亮張婷學(xué) 院：信息工程學(xué)院專 業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)指導(dǎo)老師：吳立成北京市大學(xué)生科學(xué)研究與創(chuàng)業(yè)行動(dòng)計(jì)劃立項(xiàng)申請(qǐng)正文北京市大學(xué)生科學(xué)研究與創(chuàng)業(yè)行動(dòng)計(jì)劃立項(xiàng)申請(qǐng)正文#□□□□□□□□□□□□,□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□,□□□□□□□□□□□□□□□□學(xué)術(shù)價(jià)值博弈是人工智能的重要研究主題， 人工智能的發(fā)展在很大程度上得益于博弈研究的發(fā)展。人類對(duì)機(jī)器博弈的研究衍生了大量的研究成果，這些成果對(duì)更廣泛的領(lǐng)域產(chǎn)生了重要影響。1997年著名的深藍(lán)計(jì)算機(jī)戰(zhàn)勝國(guó)際象棋世界冠軍卡斯帕羅夫成為轟動(dòng)一時(shí)的新聞事件。人工智能的先驅(qū)們?cè)J(rèn)真的表明：如果能掌握下棋的本質(zhì)，也許就掌握了人類智能行為的核心，那些能夠存在于下棋活動(dòng)中的重大原則，或許就存在于其它任何需要人類智能的活動(dòng)中。□□□□□□□□□□□□, □□□□□□□□□□□□□□□ ICGA□□□□□□□□賽的比賽指定棋類。目前在我國(guó)亞馬遜棋的算法研究和搜索分析還只是剛剛起步，亞馬遜棋的算法研究和開發(fā)還有很廣闊的空間。亞馬遜棋不僅為檢驗(yàn)人工智能發(fā)展水平提高了良好環(huán)境，還有助于加強(qiáng)對(duì)人類認(rèn)知能力的理解，而且更能進(jìn)一步推動(dòng)計(jì)算機(jī)博弈理論的發(fā)展，把亞馬遜棋人人對(duì)弈的局面轉(zhuǎn)到可以人機(jī)大戰(zhàn)上來，并且這對(duì)寬帶娛樂、棋類教學(xué)也是非常有意義和幫助的，所以亞馬遜棋計(jì)算機(jī)博弈研究具有重要的理論意義和實(shí)用價(jià)值。團(tuán)隊(duì)優(yōu)勢(shì)：.□□□□□□□□□,□□□□□□□□□□□□□□□□□□□□□□□□□□,□□□□□□□□□□□□□□□,□□□□□□ C++、JAVA等□□□□,□□□□□□□□□□□□□□□□□□□□□□□□□□□,□□□□□□□□,□□□□□□□□□□□,□□□□□□□□□□□□□□□□□□□□□□2、項(xiàng)目組成員成績(jī)優(yōu)秀，獲得過 “中央民族大學(xué)專業(yè)二等獎(jiǎng)學(xué)金”和“信息工程學(xué)院電子設(shè)計(jì)大賽一等獎(jiǎng)”等，理論知識(shí)和實(shí)踐操作能力都非常優(yōu)秀；3.□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□,在□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□ □□□□□□□□□□□□□ □□□□□□□□□ ,□□□□□□□□□□□□□□□□□□□□□□ □□□□□□□□□□□□□□ ,□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□

二、研究目標(biāo)、內(nèi)容、關(guān)鍵問題及解決方案研究目標(biāo)□□□□□JAVA□□□□□□□□□□□□□□□□□, 通過使用UCT□□□□□□□□□□□□□,□□□□□□□□□□□□□□□□□□□,□□□□□□□□□□□□□□□□□□□□□□□研究?jī)?nèi)容.博弈界面的設(shè)計(jì)。包括對(duì)口界面、菜單選項(xiàng)等的設(shè)計(jì)，同時(shí)嵌入音效、動(dòng)畫等功能?！酢酢酢酢酢酢? □□□□□ JAVA語言進(jìn)行開發(fā)，它不僅具有高移植性，并且擁有強(qiáng)大的界□□□□□□□□,□□□□□□□□□□□□□.搜索引擎的設(shè)計(jì)與優(yōu)化。對(duì)已有的多種搜索算法進(jìn)行測(cè)試、分析、調(diào)整，選擇并設(shè)計(jì)□□□□□□□□□□□□□□,□□□□□□ UCT搜索算法提高軟件的搜索效率。.軟件的調(diào)試與測(cè)試，通過手動(dòng)調(diào)整、自動(dòng)對(duì)戰(zhàn)、人機(jī)對(duì)戰(zhàn)等方法對(duì)該博弈軟件進(jìn)行測(cè)□□□□,□□□□□□□□□□□□□□□□□□2.3軟件各部分簡(jiǎn)述□□□□□□□□□□□□□□□□□□：□□□□□□□□□□□□□□□□□□□□□□□□.棋盤表示(BoardRepresentations)0~99進(jìn)□□□□□□□□□□□□□□□, □□□□□□ 10*10二維矩陣表示棋盤， 0~99進(jìn)□□□□□□□□□□□□□□,□□□□□□□□□□□□□□□□□□□□□□2.著法生成(MoveGeneration)□□□□□□□□□□□□ □□□□□□□□□□□□□□， □□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□3.□□□□(atuationFunction)□□□□□□□□□□□□□□□，□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□，□□□□□□□□□□□□□□□□□□□□□□□,□□□□□□□□□□□□□□□□□□□□□子靈活度估值、 基于QueenMove和KingMove的評(píng)估□□□□□□□□□□□□,□□□□□□□□□□□□,□□□□□□□□□□4.搜索技術(shù) (searchTechniques)□□□□□□□□□□□,□□□□□□□□,□□□□□□□□□□□□□□□□□□□□□□□□,□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□,□□□□□□□□□□□□□□□□□ UCT搜索算法 □□□□□□□,□□□□□□□□□□□□□□,□□□□□□□□□□□□□□□□□5.開局庫 (OpeningBook)□□□□□□□□□□□□□□□□□,□□□□□,□□□□□□□□□□□□,□□□□□□，□□□□□□□□□□□□□□□□□□□□□□□□□，□□□□□□□□□□□□□□□2.4要解決的關(guān)鍵問題及解決方案1、UCT搜索算法在亞馬遜棋中的運(yùn)用UCT算法源于圍棋，但同樣使用于亞馬遜棋，只是在將圍棋中的算法復(fù)制到亞馬遜棋中時(shí)，會(huì)有一定的變化?；静襟E：由當(dāng)前局面建立根節(jié)點(diǎn)，生成根節(jié)點(diǎn)的子節(jié)點(diǎn)(1)．從根節(jié)點(diǎn)開始；(2)口利用 UCB公式計(jì)算每個(gè)子節(jié)點(diǎn)的 UCB值，選擇最大值的子節(jié)點(diǎn)；(3)．若此節(jié)點(diǎn)不是葉節(jié)點(diǎn)，則從此節(jié)點(diǎn)開始，重復(fù) (2)；(4)．直到遇到葉節(jié)點(diǎn)，如果葉節(jié)點(diǎn)曾經(jīng)被模擬對(duì)局過 40次，為這個(gè)葉節(jié)點(diǎn)生成子節(jié)點(diǎn)，從此節(jié)點(diǎn)開始，重復(fù) (2)；(5)．否則對(duì)這個(gè)葉節(jié)點(diǎn)進(jìn)行模擬對(duì)局，得到勝負(fù)結(jié)果，將這個(gè)收益按對(duì)應(yīng)顏色更新到該節(jié)點(diǎn)及它的每一級(jí)祖先節(jié)點(diǎn)上去；(6)．回到 (1)，除非時(shí)間結(jié)束或者達(dá)到預(yù)設(shè)循環(huán)次數(shù)；(7)．從根節(jié)點(diǎn)的子節(jié)點(diǎn)中挑選平均收益最高的，作為最佳點(diǎn)；UCB公式：UCB=X+k*ln(parentcount)

nodecount

UCB=X+k*X：由模擬對(duì)局輸贏次數(shù)決定，表現(xiàn)該節(jié)點(diǎn)基本性質(zhì)k：常數(shù)系數(shù)， k取大表示希望模擬更多的兄弟節(jié)點(diǎn)，取小表示希望走入更深的口中；parent_count：□□□□□□□□□□□；node_count：□□□□□□□□□□□□亞馬遜棋中使用UCT算法需要額外確定的一些參數(shù)和變化：.節(jié)點(diǎn)被模擬多少次后決定展開：當(dāng)一個(gè)節(jié)點(diǎn)被模擬對(duì)局一定次數(shù)后，才能初步得到此節(jié)點(diǎn)的統(tǒng)計(jì)學(xué)信息，并展開節(jié)點(diǎn)。.提前剪枝：亞馬遜棋中每步的著法過于龐大，一般在 1000步左右，而許多著法可以很容易的判定為垃圾，所以一般進(jìn)行提前剪枝，保留 400步左右的著法。.決定展開節(jié)點(diǎn)后，子節(jié)點(diǎn)需要用提前剪枝后的順序排列，并且并不生成所有的子節(jié)點(diǎn)而是按順序先生產(chǎn)一定數(shù)量的子節(jié)點(diǎn)，在父節(jié)點(diǎn)的訪問量突破一定數(shù)量時(shí)，再?zèng)Q定下一步生產(chǎn)的子節(jié)點(diǎn)。.模擬對(duì)局層數(shù)的決定：一般選擇 6至10層。.底層評(píng)估方法：一種為返回輸贏，一種為返回輸贏程度 。21開局庫的設(shè)計(jì)□□□□□□□□□□□□□□□□□,□□□□□□□□□□□□□□□□□□,□□□□□□□□□□□□□□□□□□□□,□□□□□□□□□□□□□□□□□,□□□□□□□□□□□□□□□□□□□□□□□□□□研究基礎(chǔ)□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□,□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□ PC□□□□□□□ C++源代碼，并已對(duì)其性能、算法和優(yōu)缺點(diǎn)進(jìn)行□□□□□□,□□□□□□□□□□□□□□□□□□PC□□□□□□□□□□□□□□□□□□□□□□□,□□□□□□□□□□□□□□□□□□□□□□□□□,□□□□□□□□□□□□□□□□□□□

本項(xiàng)目的主要特色及創(chuàng)新之處□□□□□□□□□□□□□□□,□□□□□□□□□□□□□□□□□□□□□□件?！酢酢酢酢酢酢酢酢酢酢酢?□□□□□ MC/UCT□□□□,□□□□□□□□□□□□□□□,□□□□□□□ PC□□□□□□□□□□□□□□□□□□□□□□□□JAVA語言編寫。 JAVA語言是一種相當(dāng)簡(jiǎn)潔的“面向?qū)ο蟆背绦蛟O(shè)計(jì)語言?？谑÷?C++語言中所有的難以理解、容易混淆的特性，例如頭文件、指針、結(jié)構(gòu)、單元、運(yùn)算JAVA編JAVA編□□□□□□□□,□□□□□□□□,□□□□□□□□□□□□□□□□□□□□□□4.對(duì)PC博弈軟件界面及功能進(jìn)行合理優(yōu)化，保證程序在計(jì)算機(jī)中運(yùn)行的良好性能。在人機(jī)□□□□□,□□□□□□□□,□□□□□□□□□□□□□□□三、預(yù)期效果與具體成果預(yù)期效果1.□□□□□□□□PC博弈軟件能在計(jì)算機(jī)上運(yùn)行，1.□□□□□□□□PC博弈軟件能在計(jì)算機(jī)上運(yùn)行，□□□□□□□□□□□□□□□面。2.□□□□□□□□□□□,□□□□□□□□□□□□□□□□□□□□□面。2.□□□□□□□□□□□,□□□□□□□□□□□□□□□□□□□□□3.□□□□□□□□PC博弈軟件用JAVA3.□□□□□□□□PC博弈軟件用JAVA語言編寫，□□□□□□□□□□□□□□□□□□4.□□□□□□□MC/UCT搜索算法，能與高水平的亞馬遜棋愛好者對(duì)弈，搜索效率高、4.□□□□□□□□□□□□□具體成果1口高棋力亞馬遜棋 PC博弈軟件1套2．研制報(bào)告一份，包括系統(tǒng)總體及各部分的設(shè)計(jì)書、軟件源代碼、仿真文件，以及試驗(yàn)結(jié)果等。

四、具體安排及進(jìn)度第一階段□4個(gè)月）軟件的設(shè)計(jì)和編寫：原有亞馬遜棋程序的消化；計(jì)算、測(cè)試估值函數(shù)的準(zhǔn)確性；測(cè)試選擇最優(yōu)的搜索算法，并組成搜索引擎；軟件代碼編寫：1、界面開發(fā)；2、搜索引擎代碼編寫；3、算法代碼實(shí)現(xiàn)4、組員共同討論對(duì)程序的優(yōu)化和完善。對(duì)軟件整合后進(jìn)行運(yùn)行測(cè)試，解決運(yùn)行中發(fā)現(xiàn)的問題，并修改不便之處；檢驗(yàn)運(yùn)行成功，軟件初成品開發(fā)完成。第二階段□1□□□□系統(tǒng)的初測(cè)試：讓系統(tǒng)與性能低的亞馬遜棋軟件博弈，大約對(duì)弈 100到300口，記錄全部對(duì)口數(shù)據(jù)；讓系統(tǒng)與性能高亞馬遜軟件對(duì)弈，記錄全部對(duì)弈數(shù)據(jù)第三階段（2個(gè)月）ODDO：分析前期系統(tǒng)與各亞馬遜棋軟件的對(duì)弈數(shù)據(jù)， 列出具體的缺陷和不足；借鑒其他軟件的優(yōu)勢(shì)，修改和補(bǔ)充系統(tǒng)的缺陷和不足，再次提高系統(tǒng)的性能；通過和其他軟件進(jìn)行對(duì)比，優(yōu)化操作界面，使操作更人性化。第四階段□□□□□人機(jī)博弈：?請(qǐng)棋手與系統(tǒng)進(jìn)行對(duì)弈，測(cè)試系統(tǒng)的性能?咨詢棋手，了解系統(tǒng)的性能、界面和軟件是否存在“低級(jí)錯(cuò)誤” 口第六階段（2個(gè)月）DODD：?總結(jié)整個(gè)項(xiàng)目的開發(fā)過程和經(jīng)驗(yàn)；?撰寫論文和研究報(bào)告。五、經(jīng)費(fèi)預(yù)算DO說明經(jīng)費(fèi)DODD□□□□□□□ PC□□□□□□□□□□□□□□□□□□□□□□□□□□□□□： KadonEnterprises開發(fā)的“ Amazons”1000資料費(fèi)購(gòu)買書籍、論文及影印資料費(fèi)等。250差旅交通費(fèi)□□□□□□□□□□□□□火車票： 600*2=12003100食宿費(fèi)： 550*2=1100□□□□□： 800參賽報(bào)名費(fèi)參加全國(guó)大學(xué)生計(jì)算機(jī)博弈大賽報(bào)名費(fèi)500總計(jì)4850六、參考文獻(xiàn)[1]喬治，黃鴻.□□□□□□□□□□ [R].北京理工大學(xué)，2009Jens.Lieberum:AnevaluationfunctionforthegameofamazonsTheoretical.ComputerScience349(2005)230-244.J.Conway:OnNumbersandGames，AcademicPress，NewYork，1976.RichardJ.Lorentz:AmazonsDiscoverMonteCarlo.