基于Android的五子棋游戲

1、北京聯(lián)合大學(xué) 畢業(yè)論文 引 言隨著當(dāng)今社會的不斷發(fā)展變化，智能化、網(wǎng)絡(luò)化已經(jīng)成為未來社會的發(fā)展趨勢。智能手機(jī)的迅速普及早已對我們的生活產(chǎn)生了巨大的影響，智能手機(jī)數(shù)量在2014年將極有可能首次超過組裝電腦，并且用戶數(shù)量還保持著大幅的增長速度。同時伴隨著3G、4G甚至是5G等移動電話行動通信標(biāo)準(zhǔn)技術(shù)的不斷發(fā)展，將給人們帶來更加優(yōu)越的用戶體驗。對于移動互聯(lián)網(wǎng)這個巨大的市場，智能手機(jī)領(lǐng)域的爭奪更是愈演愈烈。在移動終端設(shè)備成本不斷下降、移動開發(fā)技術(shù)快速更新升級的大背景下，搶占市場份額、瓜分已有用戶群，同時挖掘潛在用戶群將更加艱難。在智能手機(jī)領(lǐng)域，手機(jī)游戲的開發(fā)與推廣已經(jīng)成為手機(jī)制造商和運營商的重要業(yè)務(wù)增

2、長點，依此可以進(jìn)而實現(xiàn)提升游戲軟件產(chǎn)業(yè)價值的目的。時至今日，社會的發(fā)展步伐逐漸加快，面對人們?nèi)找嬖鲩L的物質(zhì)文化需求，尤其是在精神層面上更高的需求，能夠在工作之余緩解壓力、在生活中獲得身心的享受成為更多人們的追求。手機(jī)游戲作為手機(jī)軟件產(chǎn)業(yè)的高附加值操作軟件之一，在持續(xù)推動手機(jī)軟件技術(shù)升級進(jìn)步的同時，恰好迎合了一部分大眾通過玩手機(jī)游戲的方式來調(diào)節(jié)情緒、放松心情的想法，來滿足他們精神上的需求。面對當(dāng)今快節(jié)奏的生活方式，手機(jī)游戲儼然已成為了人們在繁重工作之余娛樂生活的一部分，并且扮演的角色越來越重。所以，在智能手機(jī)上開發(fā)一款寓教于樂的手機(jī)游戲，從而實現(xiàn)讓客戶滿意、讓開發(fā)商獲利的雙贏目標(biāo)。目前，使用手機(jī)

3、進(jìn)行游戲占手機(jī)用途中的很大一部分比例，在手機(jī)用途多樣化的今天，手機(jī)游戲已經(jīng)成為人們考核手機(jī)使用體驗的一項標(biāo)準(zhǔn)。近幾年來手機(jī)產(chǎn)業(yè)快速發(fā)展，形式多樣的手機(jī)游戲更是層出不窮，但在讓用戶享受手機(jī)游戲帶來的娛樂體驗的同時，也遇到了一些使用中的困惑和問題。一款好的手機(jī)游戲可以在適合它的智能手機(jī)平臺上良好運行使用，但一款開發(fā)不完善的手機(jī)游戲則會給用戶帶來許多不必要的麻煩。一個成熟的下載平臺與購買機(jī)制可以讓用戶更快的體驗手機(jī)游戲，反之會讓用戶面對自己感興趣的手機(jī)游戲望而卻步。想體驗一下，卻因為沒有良好的購得渠道而放棄這款游戲，這種情況對于開發(fā)商來說更是一個巨大的損失。一款游戲在設(shè)備以及系統(tǒng)平臺上不能夠完美的運

4、行，是影響用戶體驗的一大問題。往往對于手機(jī)游戲開發(fā)考慮的不夠全面，導(dǎo)致開發(fā)不完善，因為一些小的問題或者兼容性的問題導(dǎo)致用戶直接放棄此游戲的情況不在少數(shù)，也就不能使開發(fā)商的利益達(dá)到最大化。用戶使用一款游戲軟件一段時間之后，對此款游戲有了一定的感受和認(rèn)識，對其也有了自身的意見和建議，此時用戶和開發(fā)商之間的溝通顯得尤為重要。一個完善的溝通渠道可以讓開發(fā)商最快的了解用戶的需求，從而調(diào)整已有的產(chǎn)品和服務(wù)、更好的制定未來的發(fā)展方向，這樣才能在市場競爭中處于不敗之地?？傊?，諸如此類的出現(xiàn)在手機(jī)游戲系統(tǒng)中的問題，使得這樣的手機(jī)游戲無法合理有效的滿足用戶的需求。針對上述的諸多問題，我們要本著從實際出發(fā)的原則進(jìn)行

5、手機(jī)游戲開發(fā)，其中我們要考慮到多方面的因素來開發(fā)一個五子棋手機(jī)游戲系統(tǒng)。在游戲系統(tǒng)中主要能夠?qū)崿F(xiàn)五子棋的基本對戰(zhàn)功能，其中包括人機(jī)對戰(zhàn)功能、人人對戰(zhàn)功能、基本的設(shè)置功能，本著這三個功能需求來進(jìn)行系統(tǒng)的開發(fā)設(shè)計。主游戲功能由人機(jī)對戰(zhàn)功能和人人對戰(zhàn)功能組成。人機(jī)對戰(zhàn)功能的實現(xiàn)可以讓用戶在一個人的時候進(jìn)行游戲，單人與系統(tǒng)進(jìn)行五子棋游戲的對戰(zhàn)。經(jīng)過人機(jī)雙方對戰(zhàn)之后，根據(jù)兩方的實際對戰(zhàn)情況，系統(tǒng)自動判斷雙方哪一方獲勝、哪一方失敗或者是否打平這三種情況，最終給出人機(jī)對戰(zhàn)的結(jié)果。人人對戰(zhàn)功能的實現(xiàn)可以讓兩位用戶進(jìn)行游戲，兩位用戶同時在一臺設(shè)備上進(jìn)行五子棋游戲的對戰(zhàn)。經(jīng)過兩位用戶輪流下棋，根據(jù)兩方的實際對戰(zhàn)情

6、況，系統(tǒng)自動判斷兩位用戶之間哪一方獲勝、哪一方失敗或者是否打平這三種情況，最終給出人人對戰(zhàn)的結(jié)果。這樣，通過實現(xiàn)人機(jī)對戰(zhàn)與人人對戰(zhàn)兩個功能，能夠使用戶在手機(jī)上進(jìn)行游戲，完成最基本也是最關(guān)鍵的五子棋游戲功能。對于五子棋手機(jī)游戲的開發(fā)，我們不僅要對各各功能的設(shè)計進(jìn)行合理高效的規(guī)劃，更重要的是選擇適合的手機(jī)游戲平臺。例如Android操作平臺，通過智能手機(jī)上的Android操作系統(tǒng)實現(xiàn)五子棋游戲。充分利用Android平臺的特性，借鑒眾多優(yōu)秀的開發(fā)經(jīng)驗與資源，可以對現(xiàn)存的客戶群需求進(jìn)行系統(tǒng)的分析，從而使自己開發(fā)的手機(jī)游戲系統(tǒng)更容易達(dá)到客戶的需求預(yù)期，同時對潛在客戶群進(jìn)行挖掘、讓系統(tǒng)軟件可持續(xù)性發(fā)展，

7、到達(dá)開發(fā)商利益的最大化。開發(fā)五子棋手機(jī)游戲軟件更需符合市場的規(guī)律和需求，面對用戶越來越多、越來越新穎的需求，就使得開發(fā)商在完成以往基本功能之后，更具備創(chuàng)新意識。依托現(xiàn)有的Android平臺開發(fā)實現(xiàn)更多的用戶需求，更多的在細(xì)節(jié)處完善系統(tǒng)軟件產(chǎn)品，通過更多、更細(xì)致的功能設(shè)置來吸引客戶。因此，根據(jù)目前五子棋手機(jī)游戲的現(xiàn)狀，故選擇開發(fā)基于Android平臺的五子棋游戲，滿足大眾使用Android手機(jī)進(jìn)行游戲娛樂的需求。1.緒論1.1課題研究背景能夠運行于手機(jī)上的游戲軟件叫做手機(jī)游戲。手機(jī)游戲需要具備一定硬件環(huán)境和一定系統(tǒng)級程序作為運行基礎(chǔ)，用來編寫手機(jī)游戲程序的開發(fā)語言也是種類繁多。隨著技術(shù)的不斷進(jìn)步

8、，現(xiàn)在手機(jī)的功能越來越多，也越來越強(qiáng)大。而手機(jī)游戲也已不是我們印象中畫面簡陋，規(guī)則簡單的游戲的樣子，而是依托現(xiàn)今強(qiáng)大的移動設(shè)備平臺，進(jìn)而向掌上游戲機(jī)、甚至是PC機(jī)方向發(fā)展。在保持了自身移動便捷的特點的同時，向具有更強(qiáng)的娛樂性和交互性的復(fù)雜形態(tài)融合。但是手機(jī)游戲的開發(fā)也面臨著一些問題，入門門檻低、市場競爭更加激烈，開發(fā)商對于市場宣傳和推廣經(jīng)驗不足、對產(chǎn)品的后續(xù)服務(wù)不夠重視，產(chǎn)品創(chuàng)新意識不足、沒有很強(qiáng)的知識產(chǎn)權(quán)意識等因素還影響著手機(jī)游戲的發(fā)展。雖然還存在著這樣或那樣的一些問題，但手機(jī)游戲已經(jīng)足夠滿足我們大部分的娛樂需要了。當(dāng)今智能手機(jī)已經(jīng)成為大眾不可替代的隨身工具。手機(jī)游戲已逐漸成為一種普遍的娛樂

9、方式。其便攜性與移動性迎合了人們快節(jié)奏的生活方式，能夠讓用戶隨時隨地的體驗游戲，不受環(huán)境的限制，凸顯了手機(jī)游戲碎片化的特性。同時會形成龐大的潛在用戶群，所以手機(jī)游戲潛在的市場更是無法估量。在實際開發(fā)中，利用智能手機(jī)可支持網(wǎng)絡(luò)的利好條件可更好的增加用戶的體驗感，同時結(jié)合手機(jī)游戲益智、趣味和休閑的特點迎合了消費者的娛樂需求。在游戲軟件產(chǎn)業(yè)價值不斷提升的大背景下，手機(jī)游戲成為手機(jī)的一種高附加值操作軟件，游戲編程是手機(jī)軟件編程的重要組成，同時也持續(xù)推動手機(jī)軟件技術(shù)升級進(jìn)步。隨著Android手機(jī)終端的熱銷，基于Android所開發(fā)的手機(jī)游戲擁有巨大潛力已成為行業(yè)共識。棋牌類游戲作為眾多游戲中益智性較強(qiáng)

10、的一類，有著廣泛的市場空間和一定的娛樂價值。五子棋因其可玩性強(qiáng)和操作簡單等特點，成為棋牌類游戲中最受歡迎的游戲之一。五子棋游戲編程對于計算機(jī)行業(yè)來說已經(jīng)不是一個新鮮詞語，各種優(yōu)秀的設(shè)計充斥于已有的市場平臺。大多數(shù)軟件對于基本功能和算法都有比較不錯的實現(xiàn)，用戶也對基于Android平臺的五子棋游戲有了一定的認(rèn)識與體驗，同時對于不同風(fēng)格作品的受眾也有了基本的劃分。介于當(dāng)下用戶的不同需求，所以對現(xiàn)今基于Android平臺開發(fā)的五子棋手機(jī)游戲也提出了更高的要求。因此，綜合本課題的多方面背景，開發(fā)基于Android平臺的五子棋手機(jī)游戲，最終在Android系統(tǒng)平臺的手機(jī)上運行，滿足用戶在Android手

11、機(jī)上進(jìn)行五子棋游戲娛樂的需求。1.2課題意義與目的本項目名稱為基于Android平臺的五子棋游戲的設(shè)計與實現(xiàn)，設(shè)計與開發(fā)一套基于Android平臺的五子棋游戲，該系統(tǒng)可應(yīng)用于Android系統(tǒng)手機(jī)。它通過Android平臺和智能手機(jī)相結(jié)合，開發(fā)基于Android平臺的五子棋游戲，使用戶可以通過智能手機(jī)進(jìn)行休閑娛樂。進(jìn)而通過五子棋這款益智游戲，以歡樂輕松的方式讓用戶在娛樂中學(xué)習(xí)，在學(xué)習(xí)中娛樂，在愉快的氛圍中達(dá)到寓教于樂的目的。另一方面，隨著移動互聯(lián)技術(shù)的發(fā)展，特別是智能手機(jī)已經(jīng)深入到大眾的工作和生活的各個方面，逐漸成為人們休閑娛樂的一種重要方式?，F(xiàn)今人們的工作壓力日益增大，生活節(jié)奏不斷加快，需要

12、更好的勞逸結(jié)合才能達(dá)到更高的工作效率，在工作之余的休閑放松對人們來說更是必不可少的。所以通過日趨成熟完善的Android平臺開發(fā)的五子棋游戲，可以隨時隨地的增加生活中的趣味性和消遣性，拉近了人與人的距離，從而成為人們休閑娛樂的不錯選擇。在移動通信技術(shù)飛速發(fā)展的今天，每一次的技術(shù)變革都可能對我們的生產(chǎn)生活產(chǎn)生影響。移動通信設(shè)備，尤其是手機(jī)設(shè)備更加人性化、智能化、多樣化，往往現(xiàn)在的一個設(shè)備可以實現(xiàn)以前幾個設(shè)備所能實現(xiàn)的功能。只有這樣才能滿足用戶不斷變化個需求，但同樣也對開發(fā)商的研發(fā)提出了更高的要求。所以，在開發(fā)過程中開發(fā)商借鑒了不少PC機(jī)上研發(fā)、運營游戲的經(jīng)驗，更是有很多成功將PC機(jī)上游戲移植到智

13、能手機(jī)上的成功案例。這樣，在賦予這款軟件系統(tǒng)新的意義的同時，更是開拓了更大、更有潛力的市場。但若要將市場價值最大化，不是生搬硬套就可以完成的，要根據(jù)手機(jī)硬件便捷、簡單、有局限性和軟件Android系統(tǒng)平臺開放、多元的特性進(jìn)行研發(fā)。所以五子棋這類游戲與我們的開發(fā)條件是有契合點的，其游戲本身容易上手、老少皆宜、鍛煉思維、寓教于樂的特點可以在Android平臺上很好的呈現(xiàn)，也可實現(xiàn)一定的商業(yè)價值。對于五子棋這個有著悠久歷史的游戲來說，其本身深厚的內(nèi)涵、完善的規(guī)則、多樣的博弈過程都可以通過現(xiàn)代計算機(jī)技術(shù)來實現(xiàn)和完善。在研發(fā)設(shè)計手機(jī)五子棋這樣一個益智性極強(qiáng)的游戲過程中，將涉及到計算機(jī)技術(shù)中人工智能這一領(lǐng)

14、域。博弈是人工智能的一個主要分支，它涉及人工智能算法中的決策規(guī)劃、推理技術(shù)和搜索方法。本文運用這些知識技術(shù)，設(shè)計一個基于Android平臺的五子棋手機(jī)游戲，實現(xiàn)其中的人機(jī)對戰(zhàn)與人人對戰(zhàn)功能。五子棋博弈問題作為五子棋游戲研發(fā)當(dāng)中人工智能算法的關(guān)鍵，研究如何使電腦AI通過設(shè)計的算法進(jìn)行分析、邏輯推理、統(tǒng)籌規(guī)劃來解決面臨的種種實際問題。以此在完成五子棋游戲功能的基礎(chǔ)上，對博弈過程中涉及到的算法進(jìn)行深入淺出的學(xué)習(xí)與研究。1.3五子棋簡介五子棋是一種兩人對弈的純策略型棋類游戲，起源可以追溯到上古時期, 主要流行于華人和漢字文化圈的國家以及歐美一些地區(qū)。通常雙方分別使用黑白兩色的棋子，落子順序是黑先白后，

15、輪流下棋，棋子下在棋盤直線與橫線的交叉點上，直到分出勝負(fù)。五子棋這個名字簡單明了的告訴我們了五子棋勝負(fù)判定的方法，即橫向，縱向，斜向45度與反斜向45度有連續(xù)單一顏色棋子相連就可以判定游戲結(jié)束。游戲規(guī)則簡單，容易上手，老少皆宜，不僅能增強(qiáng)思維能力，提高智力，而且富含哲理，有助于修身養(yǎng)性，已在各個游戲平臺有應(yīng)用。因此，這注定是一款老少皆宜的棋類游戲。五子棋，日文亦有“連五子、五子連、串珠、五目、五目碰、五格、五石、五法、五聯(lián)、京棋”等多種稱謂，英文則稱之為“FIR（Five In A Row的縮寫）、Gomoku（日語“五目”的羅馬拼音）、Gobang等。標(biāo)準(zhǔn)的現(xiàn)代五子棋的棋盤是橫豎各15條直線

16、垂直相交而成的，即15*15，共225個交點。棋盤大小是根據(jù)長期實踐得出的比較均衡的結(jié)果。五子棋棋盤越大，先手的優(yōu)勢越大。如果棋盤縱橫在10*10以下的話，高手相遇就誰也無法取勝了。Louis Victor Allis 在計算機(jī)上的模擬連珠時計算表明，15*15的標(biāo)準(zhǔn)棋盤下，存在先手不負(fù)的著法，前提是沒有引入其他禁手或交換規(guī)則。而且普遍相信，很可能在更大的棋盤上也存在類似著法。連珠在沒有附加規(guī)則的版本，存在完美對策使得后手不可能獲勝。1.4 Android操作系統(tǒng)簡介Android是專門為移動設(shè)備開發(fā)的基于Linux內(nèi)核的移動平臺，該平臺包含操作系統(tǒng)、中間件、用戶界面和應(yīng)用軟件，是一個真正開放

17、的移動開發(fā)平臺。Android操作系統(tǒng)在移動設(shè)備上有廣泛應(yīng)用，如智能手機(jī)和平板電腦。Android操作系統(tǒng)由Google公司和開放手機(jī)聯(lián)盟領(lǐng)導(dǎo)及開發(fā)，尚未有統(tǒng)一中文名稱，中國大陸地區(qū)較多人翻譯為“安卓”。Android操作系統(tǒng)最初由Andy Rubin開發(fā)，主要支持手機(jī)。2005年8月由Google收購注資。2007年11月，Google與84家硬件制造商、軟件開發(fā)商及電信營運商組建開放手機(jī)聯(lián)盟共同研發(fā)改良Android系統(tǒng)。隨后Google以Apache開源許可證的授權(quán)方式，發(fā)布了Android的源代碼。第一部Android智能手機(jī)發(fā)布于2008年10月。2011年第一季度，Android在

18、全球的市場份額首次超過塞班系統(tǒng)，躍居全球第一。 2013年的第四季度，Android平臺手機(jī)的全球市場份額已經(jīng)達(dá)到78.1%。2013年09月24日Google開發(fā)的操作系統(tǒng)Android在迎來了5歲生日，全世界采用這款系統(tǒng)的設(shè)備數(shù)量已經(jīng)達(dá)到10億臺。Android發(fā)布以來，其開源操作系統(tǒng)的特性，使得越來越多的人關(guān)注Android的發(fā)展。Android平臺其具備的開放、平等、無界、方便、豐富的特性也讓更多的開發(fā)人員能夠在這個標(biāo)準(zhǔn)化、開放式的移動平臺上進(jìn)行開發(fā)，這也將為Android平臺帶來更豐富的軟件資源，進(jìn)而使得Android受到越來越多的人青睞。Android平臺的體系架構(gòu)從軟件分層的角度

19、來說，主要由APPLICATIONS、APPLICATION FRAMEWORK、LIBRARIES和LINUX KENRNEL這幾部分構(gòu)成，如圖1-4所示：圖1-4 Android體系結(jié)構(gòu)圖(1). APPLICATIONS（應(yīng)用程序?qū)樱?yīng)用程序?qū)佣际怯肑ava語言編寫的運行在Android平臺上的程序，一般情況下，大多數(shù)應(yīng)用程序都是在同一系列的核心應(yīng)用程序包中一起發(fā)布的，如瀏覽器、播放器、日歷、撥號程序及通訊錄等程序。該層的程序是完全平等的，Android開發(fā)人員通常需要做的就是編寫在應(yīng)用層上運行的應(yīng)用程序。(2). APPLICATION FRAMEWORK（應(yīng)用程序框架層）該應(yīng)用程序的

20、框架設(shè)計簡化了組件的重用，并且其中任何一個應(yīng)用程序都可以發(fā)布自身的功能來供其他應(yīng)用程序調(diào)用，這樣也使用戶很方便地替換程序的組件而不影響其他模塊的使用。這種替換需要遵循框架的安全性限制。(3). LIBRARIES（Android運行時庫）該層由兩部分構(gòu)成，程序庫及Android運行時庫。程序庫為一些C或者C+庫，這些庫能夠被Android系統(tǒng)中不同的應(yīng)用程序調(diào)用，并通過應(yīng)用程序框架為開發(fā)者提供服務(wù)。而Android運行時庫包含了Java編程語言核心庫的大部分功能，提供了程序運行時所需調(diào)用的功能函數(shù)。(4). LINUX KENRNEL（Linux內(nèi)核）Android平臺中操作系統(tǒng)是基于Linu

21、x內(nèi)核的，如安全性、內(nèi)存管理、進(jìn)程管理、網(wǎng)絡(luò)協(xié)議棧和驅(qū)動模型等都依賴于該內(nèi)核。該層為軟件與硬件之間增加了一層抽象層，使開發(fā)過程中不必時時考慮底層硬件細(xì)節(jié)。1.5論文主要工作本論文以軟件系統(tǒng)的實際應(yīng)用為開發(fā)的最終目標(biāo)，設(shè)計實現(xiàn)一套基于Android平臺的五子棋游戲，該系統(tǒng)可應(yīng)用于Android系統(tǒng)手機(jī)。論文按照軟件工程的工作流程對開發(fā)平臺與五子棋游戲本身進(jìn)行了廣泛的調(diào)研和細(xì)致的分析，采用面向?qū)ο蟮木幊趟枷脒M(jìn)行程序系統(tǒng)的類結(jié)構(gòu)設(shè)計以及代碼的實現(xiàn)。本文的主要工作是基于Android平臺對五子棋游戲進(jìn)行設(shè)計實現(xiàn)的。五子棋游戲本身作為一款大眾所熟知的棋類游戲，有廣泛的群眾基礎(chǔ)。但在其簡單、易上手的同時，

22、也有精深的棋型、棋勢變化，專業(yè)的禁手規(guī)則、復(fù)雜的棋譜算法分析等不為大眾所了解的一面。所以我在完成一般玩家用戶人機(jī)對戰(zhàn)、人人對戰(zhàn)需求的同時，增加了各種游戲功能設(shè)置，增加了游戲的趣味性和娛樂性，而并沒有對專業(yè)的算法及規(guī)則進(jìn)行深入的研究。完成這樣的一個基于Android平臺的五子棋游戲，讓用戶可以在手機(jī)上進(jìn)行休閑娛樂，基于此類用戶群定位自身系統(tǒng)軟件及市場價值。滿足當(dāng)下用戶更新更高的娛樂休閑要求。系統(tǒng)設(shè)計實現(xiàn)的主要內(nèi)容包括：如何設(shè)置整個游戲的界面，實現(xiàn)人機(jī)對戰(zhàn)與人人對戰(zhàn)，拓展功能的設(shè)置，如何控制五子棋游戲中棋子的擺放，算法的研究，如何判斷游戲是否結(jié)束以及輸贏問題等。實現(xiàn)上述操作的可用性及高性能運行。最

23、終提交一套基于Android平臺的五子棋游戲運行程序。在Android五子棋游戲的專業(yè)性與娛樂性之間找到一個更好的平衡點，完成一個風(fēng)格獨樹一幟的作品。2 需求分析2.1 系統(tǒng)需求分析1. 基于PC的虛擬移動終端環(huán)境的搭建：智能終端的操作系統(tǒng)各異，本次設(shè)計選擇在PC上虛擬移動終端環(huán)境，選擇了應(yīng)用廣泛、用戶眾多的Android平臺。2. 虛擬平臺開發(fā)環(huán)境的選?。何覀冊谔摂M環(huán)境中選取對Java、Android語言支持較好的IDE，選擇使用Eclipse進(jìn)行設(shè)計實現(xiàn)。 3. 游戲?qū)崿F(xiàn)中的資源約束考慮：移動終端由于受其本身資源（主要包括處理器、存儲器、網(wǎng)絡(luò)帶寬等）的約束，對應(yīng)用程序的支持與PC環(huán)境差異較

24、大，對數(shù)據(jù)結(jié)構(gòu)和算法等要求較高，所以有效的算法模型的提取對應(yīng)用程序的效率至關(guān)重要。2.2 用戶需求分析娛樂生活在社會多元化的今天，成為了大多數(shù)人生活中不可或缺的一部分。隨著移動互聯(lián)技術(shù)的發(fā)展，手機(jī)游戲更是在快節(jié)奏生活的今天成為了人們休閑消遣的新選擇。面對市面上種類繁多的手機(jī)游戲，要想占有一席之地更要從用戶的實際需求出發(fā)。五子棋作為一款受眾面廣、群眾基礎(chǔ)好的游戲是一個很有價值的研發(fā)課題。想要比市場上的同類產(chǎn)品更有競爭力，要開發(fā)更友好的界面、基本功能更清晰易懂。五子棋手機(jī)游戲能夠保證良好的用戶使用時間，讓用戶在使用中放松心情、消遣休閑。對于青少年用戶還能以歡樂輕松的方式讓用戶在娛樂中學(xué)習(xí)，在學(xué)習(xí)中

25、娛樂，有著寓教于樂了的教育意義從而到達(dá)擴(kuò)大產(chǎn)品影響力的效果。對于工作人群來說壓力日益增大，生活節(jié)奏不斷加快，在工作之余的休閑放松對人們來說更是必不可少的，所以五子棋手機(jī)游戲可以起到更好的勞逸結(jié)合作用。在實際應(yīng)用中還可利用五子棋游戲的本身特性，拉近人與人之間的關(guān)系，在用戶使用過程中潛移默化的推廣產(chǎn)品、開拓市場，同時增加游戲的可玩性和生命力。相信通過日趨成熟完善的Android平臺開發(fā)的五子棋游戲，可以隨時隨地的增加生活中的趣味性和消遣性，從而成為人們休閑娛樂的不錯選擇。基于Android平臺的五子棋游戲包括：人機(jī)對戰(zhàn)功能、人人對戰(zhàn)功能、設(shè)置功能、幫助功能。人機(jī)對戰(zhàn)功能是為了滿足單人用戶的游戲需求

26、，用戶可以與電腦AI進(jìn)行對戰(zhàn)來完成游戲。人人對戰(zhàn)功能是為了滿足兩位用戶的游戲需求，兩位用戶可以在同一臺設(shè)備上進(jìn)行對戰(zhàn)來完成游戲。設(shè)置功能是為了滿足用戶對游戲多樣化的需求，用戶可以通過設(shè)置功能對游戲進(jìn)行各方面的設(shè)置。幫助功能是為了滿足用戶對游戲認(rèn)知使用的需求，用戶可以通過設(shè)置功能了解游戲如何操作使用、反饋用戶信息。2.3 功能需求分析手機(jī)屏幕尺寸分為物理尺寸和顯示分辨率兩個概念。物理尺寸是指屏幕的實際大小。一般來說，大的屏幕就要配備高的分辨率，顯示分辨率就是在這個尺寸下可以顯示多少個像素，顯示的像素越多，可以表現(xiàn)的余地自然就越大?，F(xiàn)在手機(jī)行業(yè)發(fā)展迅速，手機(jī)屏幕的大小也是各有不同，鑒于不同手機(jī)屏幕

27、尺寸不同，在設(shè)計游戲的時候必須考慮到設(shè)計的手機(jī)游戲能否適應(yīng)各種尺寸的手機(jī)屏幕和不同的顯示分辨率，并且要讓軟件的界面簡潔明了，操作簡單容易。游戲軟件在使用中需要極快的反應(yīng)速度，所以軟件具有的人工智能算法原理要簡單并且運行要快速，手機(jī)處理器的頻率直接要求需要使用簡單實用的智能算法，充分體現(xiàn)其軟件系統(tǒng)本身的靈活性和適應(yīng)性。在設(shè)計本游戲時考慮到用戶需要的是一個操作簡便、界面精致的五子棋游戲軟件。同時要提供人機(jī)對戰(zhàn)和人人對戰(zhàn)兩個游戲模式。特別是人機(jī)對戰(zhàn)功能，要考慮到此軟件是在手機(jī)上運行，手機(jī)的性能與PC機(jī)有很大差距，因此在人工智能算法的設(shè)計上應(yīng)該盡可能的縮短系統(tǒng)搜索、運算的時間，同時還要保證有一定的智能

28、水平，否則對玩家來說喪失了一定的挑戰(zhàn)性，可玩性大大降低，也就缺少了對用戶的吸引力。此外，通過對軟件功能的分析以及對五子棋愛好者的需求調(diào)研，得出還有如下需求信息：具有重新開始功能；具有音樂、音效開啟關(guān)閉功能；具有幫助功能；具有返回功能；具有設(shè)置棋盤功能；具有退出游戲功能；具有判斷勝負(fù)功能。2.4 系統(tǒng)用例圖根據(jù)對系統(tǒng)、用戶、功能的需求分析，確定了用戶與AI兩個主角，通過用例圖說明它們與功能模塊之間的需求關(guān)系，基于Android的五子棋游戲的用例圖模型如圖2-5所示： 人機(jī)對戰(zhàn) 人人對戰(zhàn) 棋盤設(shè)置 幫助功能 用戶 重新開始 聲音設(shè)置 棋盤繪制 棋勢掃描 棋勢排序 棋勢評估 AI 擇位落子 判斷勝負(fù)

29、圖2-5 基于Android的五子棋游戲的用例圖模型1.人機(jī)對戰(zhàn)用例應(yīng)用范圍：用戶；參與者：用戶；用例類型：用戶目標(biāo)；用例描述：用戶與電腦AI進(jìn)行對戰(zhàn)。2.人人對戰(zhàn)用例應(yīng)用范圍：用戶；參與者：用戶；用例類型：用戶目標(biāo)；用例描述：用戶與用戶進(jìn)行對戰(zhàn)。3.棋盤設(shè)置用例應(yīng)用范圍：人機(jī)對戰(zhàn)、人人對戰(zhàn)；參與者：用戶；用例類型：用戶目標(biāo)；用例描述：對游戲中棋盤大小進(jìn)行設(shè)置。4.幫助功能用例應(yīng)用范圍：用戶；參與者：用戶；用例類型：用戶目標(biāo)；用例描述：幫助用戶了解游戲內(nèi)容、規(guī)則，游戲的使用方法，反饋用戶信息。5.重新開始用例應(yīng)用范圍：人機(jī)對戰(zhàn)、人人對戰(zhàn)；參與者：用戶；用例類型：用戶目標(biāo)；用例描述：在人機(jī)對戰(zhàn)、

30、人人對戰(zhàn)中重新開始棋局。6.聲音設(shè)置用例應(yīng)用范圍：人機(jī)對戰(zhàn)、人人對戰(zhàn)；參與者：用戶；用例類型：用戶目標(biāo)；用例描述：在人機(jī)對戰(zhàn)、人人對戰(zhàn)中設(shè)置背景音樂、音效，實現(xiàn)開啟關(guān)閉音樂。7.棋盤繪制用例應(yīng)用范圍：人機(jī)對戰(zhàn)、人人對戰(zhàn)；參與者：電腦AI；用例類型：AI目標(biāo)；用例描述：繪制15*15的棋盤以及相關(guān)選項和背景，并負(fù)責(zé)用戶、電腦AI落子后棋子的繪制。8.棋勢掃描用例應(yīng)用范圍：人機(jī)對戰(zhàn)、人人對戰(zhàn)；參與者：電腦AI；用例類型：AI目標(biāo)；用例描述：根據(jù)棋盤上的實際情況掃描搜索落子位置，獲取當(dāng)下這個棋局的棋型棋勢。9.棋勢排序用例應(yīng)用范圍：人機(jī)對戰(zhàn)；參與者：電腦AI；用例類型：AI目標(biāo)；用例描述：根據(jù)編寫的

31、算法程序?qū)Ξ?dāng)下棋勢進(jìn)行排序，便于進(jìn)行接下來的棋勢評估。10.棋勢評估用例應(yīng)用范圍：人機(jī)對戰(zhàn)；參與者：電腦AI；用例類型：AI目標(biāo)；用例描述：根據(jù)編寫的算法程序，分別對玩家和電腦AI的棋型棋勢進(jìn)行評估，量化棋勢以便分析運算。11.擇位落子用例應(yīng)用范圍：人機(jī)對戰(zhàn)；參與者：電腦AI；用例類型：AI目標(biāo)；用例描述：結(jié)合對玩家和電腦AI的棋勢分析，選取最優(yōu)的下棋策略。若棋勢有利于玩家，則采取“防守”策略，若棋勢有利于電腦AI，則采取“進(jìn)攻”策略。12.判斷勝負(fù)用例應(yīng)用范圍：人機(jī)對戰(zhàn)、人人對戰(zhàn)；參與者：電腦AI；用例類型：AI目標(biāo)；用例描述：每次玩家或者電腦AI落子之后，都進(jìn)行勝負(fù)判斷。若出現(xiàn)“五子連珠”

32、的情況，則“五子連珠”一方獲勝、另一方失敗，并給出判定結(jié)果，此局游戲結(jié)束。3 系統(tǒng)開發(fā)環(huán)境3.1 開發(fā)環(huán)境操作系統(tǒng)：Windows 8（64位）開發(fā)軟件：Eclipse 3.8JDK：jdk 1.6.0_37Android SDK：SDK Platform Android 4.2, API 173.2 開發(fā)環(huán)境的配置本系統(tǒng)設(shè)計與實現(xiàn)是基于PC操作系統(tǒng)下的虛擬移動終端之上的，開發(fā)環(huán)境的搭建主要包括JDK的配置、Android SDK的配置、Android開發(fā)插件ADT的安裝、AVD模擬器的創(chuàng)建等。3.2.1 JDK的配置安裝好下載的JDK文件，之后在系統(tǒng)的環(huán)境變量中進(jìn)行配置。右鍵計算機(jī)->

33、屬性->高級系統(tǒng)設(shè)置，單擊“環(huán)境變量”，在彈出對話框中單擊“系統(tǒng)變量”欄中的“新建”按鈕，創(chuàng)建新的系統(tǒng)變量。在變量名處輸入 “JAVA_HOME”、在變量值處輸入JDK安裝路徑。之后在“環(huán)境變量”對話框中雙擊Path變量對其進(jìn)行修改，在原變量值最前端添加“.;%JAVA_ HOME%bin;”變量值，最后需在控制臺中輸入javac命令，若輸出修改命令的語法和參數(shù)選項等信息，說明JDK環(huán)境搭建成功。3.2.2 AVD模擬器的創(chuàng)建AVD（Android Virtual Device）即Android模擬器，它是Android官方提供的一個可以運行Android程序的虛擬機(jī)，在運行Androi

34、d程序之前，首先需要創(chuàng)建一個AVD模擬器。啟動Eclipse，單擊工具欄中的Android Virtual Device Manager按鈕，在彈出窗口中單擊New按鈕。彈出 Create new Android Virtual Device（AVD）對話框，在該對話框中輸入要創(chuàng)建的AVD名稱、選擇屏幕樣式及AVD模擬器版本、設(shè)置SD卡內(nèi)存大小，如圖3-2-2-1所示：圖3-2-2-1 設(shè)置AVD模擬器這樣就創(chuàng)建好了一個AVD模擬器。選擇該模擬器，可以通過單擊右側(cè)的Edit、Delete、Details和Start按鈕，分別對其進(jìn)行編輯、刪除、查看和啟動操作，如圖3-2-2-2所示：圖3-2-

35、2-2 創(chuàng)建完成AVD模擬器4.總體設(shè)計4.1系統(tǒng)功能劃分基于Android的五子棋游戲主要包括人機(jī)對戰(zhàn)功能、人人對戰(zhàn)功能、游戲設(shè)置功能、游戲幫助功能，系統(tǒng)功能模塊圖如圖4-1所示基于Android平臺的五子棋游戲游戲開始界面模塊 人機(jī)對戰(zhàn)人人對戰(zhàn)游戲幫助游戲退出 游戲設(shè)置設(shè)置重玩、音樂、音效、幫助、返回主頁退出棋盤設(shè)置 圖4-1 系統(tǒng)功能模塊圖功能實現(xiàn)方面，通過這幾個模塊的切換，實現(xiàn)不同需求的滿足，最終達(dá)到：友好的歡迎界面，增加游戲的興趣；開始游戲主菜單選擇游戲中不同的功能，清晰明了的了解游戲的模式；選擇人機(jī)游戲?qū)?zhàn)，可與電腦AI進(jìn)行人機(jī)對決；選擇人人游戲?qū)?zhàn)，可兩人之間在一臺設(shè)備上進(jìn)行人人

36、比賽；通過設(shè)置功能，可對游戲的音樂、棋盤設(shè)置等基本游戲元素進(jìn)行相應(yīng)的設(shè)置。4.2系統(tǒng)模塊結(jié)構(gòu)設(shè)計4.2.1 游戲開始界面模塊游戲開始界面是用戶進(jìn)入游戲后最先看到的，它給用戶的第一印象至關(guān)重要，會影響到接下來的體驗感受。游戲的主要功能都呈現(xiàn)在游戲開始界面上，游戲開始界面包括兩種游戲模式的選擇、游戲的設(shè)置、游戲的幫助以及退出游戲。游戲開始界面要給用戶最簡便、最直觀的使用體驗，方便用戶操作。同時游戲開始界面需要美觀、精致，在背景圖片上以五個按鈕的形式體現(xiàn)出人機(jī)對戰(zhàn)、人人對戰(zhàn)、游戲設(shè)置、游戲幫助、游戲退出這五個功能模塊，分別點擊五個按鈕就可以進(jìn)入其功能模塊，實現(xiàn)其功能。4.2.2 人機(jī)對戰(zhàn)模塊人機(jī)對戰(zhàn)

37、是系統(tǒng)兩種游戲模式之一，是游戲的核心功能模塊。進(jìn)入此模塊后，便是五子棋游戲的主游戲界面。在繪制的背景、棋盤上與電腦AI進(jìn)行對戰(zhàn)，用戶先下棋，由電腦AI進(jìn)行勝負(fù)判斷。主游戲界面作為游戲的核心，是雙方對弈的界面，設(shè)計實現(xiàn)中除了要遵循五子棋游戲本身的規(guī)則標(biāo)準(zhǔn)外，還要讓用戶感到界面美觀、清晰，因為此界面是用戶游戲過程中使用時間最長的界面。在此界面中除實現(xiàn)對弈功能區(qū)，還要運用“MENU”功能鍵實現(xiàn)部分游戲元素的設(shè)置，包括重玩、音樂、音效、關(guān)于和主頁五個設(shè)置功能模塊，分別以五個按鈕的方式實現(xiàn)。點擊“重玩”按鈕可以實現(xiàn)棋局重置，以重新開始游戲。點擊“音樂”按鈕，彈出設(shè)置對話框，對背景音樂的開啟、關(guān)閉進(jìn)行設(shè)置

38、。點擊“音效”按鈕，彈出設(shè)置對話框，對游戲中諸如落子等音效進(jìn)行開啟、關(guān)閉設(shè)置。點擊“關(guān)于”按鈕，進(jìn)入幫助頁面，介紹游戲的簡介、規(guī)則等信息以及提供用戶反饋信息的方式。點擊“主頁”按鈕，返回游戲開始主頁界面。4.2.3 人人對戰(zhàn)模塊人人對戰(zhàn)是系統(tǒng)兩種游戲模式之一，是游戲的核心功能模塊，此功能模塊在同一臺設(shè)備上實現(xiàn)。進(jìn)入此模塊后，便是五子棋游戲的主游戲界面。在繪制的背景、棋盤上兩位用戶間進(jìn)行對戰(zhàn)，兩位用戶輪流下棋，由電腦AI進(jìn)行勝負(fù)判斷。主游戲界面作為游戲的核心，是雙方對弈的界面，設(shè)計實現(xiàn)中除了要遵循五子棋游戲本身的規(guī)則標(biāo)準(zhǔn)外，還要讓用戶感到界面美觀、清晰，因為此界面是用戶游戲過程中使用時間最長的界

39、面。在此界面中除實現(xiàn)對弈功能區(qū)，還要運用“MENU”功能鍵實現(xiàn)部分游戲元素的設(shè)置，包括重玩、音樂、音效、關(guān)于和主頁五個設(shè)置功能模塊，分別以五個按鈕的方式實現(xiàn)。點擊“重玩”按鈕可以實現(xiàn)棋局重置，以重新開始游戲。點擊“音樂”按鈕，彈出設(shè)置對話框，對背景音樂的開啟、關(guān)閉進(jìn)行設(shè)置。點擊“音效”按鈕，彈出設(shè)置對話框，對游戲中諸如落子等音效進(jìn)行開啟、關(guān)閉設(shè)置。點擊“關(guān)于”按鈕，進(jìn)入幫助頁面，介紹游戲的簡介、規(guī)則等信息以及提供用戶反饋信息的方式。點擊“主頁”按鈕，返回游戲開始主頁界面。4.2.4 游戲設(shè)置模塊游戲設(shè)置模塊可以幫助用戶在游戲前對游戲進(jìn)行設(shè)置。進(jìn)入游戲設(shè)置模塊對話框，可以選擇棋盤大小。棋盤設(shè)置分

40、為三檔：小格棋盤、中等棋盤、大格棋盤，其中小格棋盤為五子棋標(biāo)準(zhǔn)棋盤15*15規(guī)格。三檔棋盤的橫縱格數(shù)依次遞減，實現(xiàn)繪制出大小不同規(guī)格的棋盤，在設(shè)置后開始游戲?qū)⒗L制所選擇的棋盤規(guī)格，滿足不同層次用戶的需求。4.2.5 游戲幫助模塊游戲幫助模塊幫助用戶了解游戲內(nèi)容、操作等信息。進(jìn)入游戲幫助界面后用戶可以了解游戲的簡介、基本規(guī)則以及提供關(guān)于軟件使用后意見和建議的反饋渠道。4.2.6 游戲退出模塊游戲退出模塊實現(xiàn)退出系統(tǒng)軟件的功能。點擊“游戲退出”結(jié)束五子棋游戲系統(tǒng)，關(guān)閉應(yīng)用軟件。5 詳細(xì)設(shè)計5.1 系統(tǒng)主流程根據(jù)各個模塊功能和需求的不同，游戲系統(tǒng)有初始化模塊、主控制模塊、人工智能模塊、落子模塊、判斷

41、勝負(fù)模塊。所畫出的系統(tǒng)主流程圖,如圖5-1所示：游戲界面初始化游戲模式游戲主界面主循環(huán)控人機(jī)對戰(zhàn)主循環(huán)控人人對戰(zhàn)玩家1落子玩家2落子玩家落子分析棋盤得出最佳落子位置 AI落子判斷勝負(fù)判斷勝負(fù)重新開始游戲幫助游戲設(shè)置結(jié)束否某方勝利某方勝利否某方退出某方退出 圖5-1 基于Android平臺的五子棋游戲系統(tǒng)主流程圖游戲界面初始化模塊：載入背景圖片，繪制棋盤、棋子，刷新棋盤，清空游戲雙方落子集合等功能。主循環(huán)控制模塊：負(fù)責(zé)控制下棋順序，當(dāng)輪到某一方下棋時，將程序流程轉(zhuǎn)到相應(yīng)的模塊中，主要擔(dān)當(dāng)一個調(diào)度者的角色。玩家落子模塊：用戶在指定落子區(qū)域單擊觸摸后，程序進(jìn)行響應(yīng)并計算該子坐標(biāo)，在相應(yīng)的位置繪制出相

42、應(yīng)的棋子。分析棋盤得出最佳落子位置模塊：是人機(jī)對戰(zhàn)功能的核心，也是本系統(tǒng)軟件的核心。通過程序設(shè)定的分析、運算方法，電腦AI進(jìn)行棋型棋勢分析，即人工智能模塊。AI落子模塊：通過分析、運算，電腦AI在最優(yōu)的位置上繪制相應(yīng)的棋子。判斷勝負(fù)模塊：根據(jù)編寫程序的分析、運算規(guī)則，對人機(jī)雙方或者人人雙方進(jìn)行游戲勝負(fù)的判定。5.2 建立模型棋子和棋盤是五子棋游戲的兩大基本要素，棋子分為黑白兩色，棋盤我們采用標(biāo)準(zhǔn)的15*15規(guī)格。五子棋游戲的棋子、棋盤模型建立流程如圖5-2所示：把棋子數(shù)據(jù)載入設(shè)置好的點模型建立完成根據(jù)橫縱坐標(biāo)產(chǎn)生棋盤上的線設(shè)置棋盤每個點大小游戲界面上的橫縱坐標(biāo)根據(jù)點大小計算圖5-2 模型建立流

43、程圖標(biāo)準(zhǔn)的五子棋棋盤是15*15規(guī)格的，本系統(tǒng)中可以對棋盤大小進(jìn)行設(shè)置。棋盤由背景圖片和線條組成，背景圖片為系統(tǒng)加載，而線條是在進(jìn)入主游戲界面的同時用相關(guān)函數(shù)畫出來的。所以需設(shè)置棋盤上每個點的大小，從而計算出游戲界面上的橫縱坐標(biāo)。繪制出棋盤的框架，根據(jù)計算出的橫縱坐標(biāo)，繪制棋盤上的所有線，這樣棋盤模型就建立好了。棋子的繪制是運用繪制方法與設(shè)置好的點對應(yīng)，通過對點的屬性修改載入的相應(yīng)棋子模型，這樣棋子模型就建立好了。5.3 控制模塊設(shè)計控制模塊分為主控制模塊、判斷勝負(fù)模塊、落子模塊中的處理分析部分?？刂颇K如圖5-3所示：主控制模塊落子模塊 控制模塊判斷勝負(fù)模塊圖5-3 控制模塊圖主控制模塊的作

44、用是轉(zhuǎn)換下棋順序，當(dāng)輪到某一方下棋的時候，主控制模塊把整個數(shù)據(jù)和流程轉(zhuǎn)到相對應(yīng)的模塊里。落子模塊是接收并處理分析用戶點擊界面的事件，面向的對象時玩家與電腦AI落子模塊的處理分析。判斷勝負(fù)模塊是根據(jù)編寫的程序規(guī)則進(jìn)行分析、運算，給出勝負(fù)結(jié)果。5.4 顯示模塊設(shè)計游戲顯示模塊包括游戲界面初始化模塊，落子模塊中的接收點功能與顯示棋子功能。顯示模塊設(shè)計如圖5-4所示：游戲開始顯示游戲界面讀取控制模塊計算出的數(shù)據(jù) 顯示棋子接收用戶觸摸信息計算棋子位置向控制模塊匯報刷新棋盤圖5-4 顯示模塊設(shè)計圖開始游戲后用戶進(jìn)入游戲主界面，首先初始化模塊運行，用戶將看到游戲主界面上的游戲模式選擇等按鈕，選擇游戲模式進(jìn)入

45、對弈界面，將顯示棋盤等主游戲區(qū)，可以開始進(jìn)行游戲。落子模塊接受用戶的觸摸響應(yīng)，并在棋盤上對應(yīng)的位置顯示出所下棋子。游戲分出勝負(fù)后在主游戲界面上顯示勝負(fù)結(jié)果，再次觸摸刷新棋盤，開始新一局游戲。5.5 AI算法的分析人工智能是一門新的技術(shù)科學(xué)，是計算機(jī)科學(xué)的一個分支。它能產(chǎn)生模擬人類智能的反應(yīng)，根據(jù)不同算法把各種人類模擬完善。在人工智能算法方面，一般有極大極小樹、深度優(yōu)先搜索、剪枝這三種方法。目前大部分博弈類游戲中的人工算法都采用極大極小樹這種方法。假設(shè)己方為MAX點，對方則為MIN點。如果當(dāng)層的節(jié)點為奇數(shù)時那么就為MAX層，為偶數(shù)時就為MIN層。當(dāng)在MAX層時，該層的值就應(yīng)該為下一個MIN層中的

46、最大一個的值。當(dāng)在MIN層是，該層的值就應(yīng)該為它子層MAX的最小的一個。深度優(yōu)先搜索與廣度優(yōu)先搜索的區(qū)別在于下一個節(jié)點的選擇。DFS先選擇好節(jié)點，如果下個節(jié)點不存在或都已經(jīng)遍歷過了，就向上返回到上一個節(jié)點，再遍歷其它的未被訪問過的點，這要用到堆棧結(jié)構(gòu)，使用一個遞歸來實現(xiàn)。BFS則是逐個的遍歷它的聯(lián)接接點，將已經(jīng)訪問過的點放入隊列中，然后再依次取出繼續(xù)這個過程。不必要的節(jié)點可以被Alpha-Beta剪枝去除，并且去除了這些節(jié)點也不會影響結(jié)果。5.5.1 極大極小樹搜索算法五子棋雙方對戰(zhàn)，將其中一方叫做A方，另一方叫做B方。假設(shè)現(xiàn)在A走，那么他有15*15種走法（無論優(yōu)劣），而B也有與之相對應(yīng)的若

47、干種走法，之后又輪到A走如此往復(fù)?？梢杂靡粋€博弈樹來表示五子棋游戲的這個過程，如圖5-5-1-1所示，圖中省略號表示游戲過程中的大量分枝。開局黑子先行白方下子白方下子15*15-1種黑15*15-2黑依次遞推，直到棋子充滿棋盤或者某一方獲勝，游戲結(jié)束15*15-2圖5-5-1-1 五子棋游戲的完整博弈樹從圖5-5-1中可以看出，從游戲開局默認(rèn)黑子先行的情況下，第一步走法的可能性等于棋盤的大小15*15（不考慮禁手，默認(rèn)空白點都是可以落子的點），第二步白子則有15*15-1種走法，如此往復(fù)，直到棋子下滿棋盤或者某一方獲勝。通過五子棋游戲的博弈樹圖，可以看出這是一個十分復(fù)雜的分析運算過程。對于大多

48、數(shù)棋類游戲來說都是無法建立完整的博弈樹的，因為很多情形根本無法到達(dá)葉子節(jié)點，即使能夠建立完整的博弈搜索樹其計算的工作量更是極為巨大，大多數(shù)情況很難完成。也就是說完成博弈算法需要一個更加切合實際的方法。極大極小算法（Minimax Algorithm）是比較適合當(dāng)前這種局面的算法。 在上面的博弈樹中，設(shè)置A勝的分值為1，B勝的分值為-1，和局的分值為0。因此每當(dāng)輪到A下棋的時候均會選擇分值最大的點，反之B每次下棋定會選擇分值最小的點。由此可以得出中間節(jié)點落子的一種計算方法：若該節(jié)點層次時該A落子，則此處的分值將是同層次中最大的，若該B落子時，則其分值必是同層節(jié)點中最小的。對于博弈樹來說雖然只是形

49、式上的變化，并未觸及其本質(zhì)，但與解決實際情況更進(jìn)了一步。綜上所述，建立一顆完整的搜索樹基本上是不可行的了，那么通過建立少量的搜索為當(dāng)前局面選擇一個好的落子點，是一個更為實際有效的方法。在實際的游戲過程中，對于局勢的好壞并不僅僅只是如上述那般簡單。也就是說可以使用更加細(xì)致的方法來評比局面而不是如前面所說的使用“1”，“-1”，“0”來比較。假設(shè)我們有一個函數(shù)，可以使A勝利取值為正的無窮大，B勝利取負(fù)的無窮大，和局為0，那么對于其余的局面就可以用兩者之間的數(shù)字來表示，如果這樣的話，就可以建立一個固定層數(shù)的搜索樹，這個函數(shù)被稱作靜態(tài)評值函數(shù)，用以取代超出固定深度的搜索，這樣做雖然沒有完全搜索那么精確

50、但是勝在這樣可以降低實現(xiàn)的難度。本設(shè)計中運用到的極大極小方法就是基于這種有限深度的靜態(tài)評值函數(shù)來實現(xiàn)的。在運用極大極小方法進(jìn)行搜索時，需要注意的是應(yīng)當(dāng)選擇深度優(yōu)先的搜索方法，這樣可以只搜索整棵樹的一部分，搜索過的節(jié)點立即刪去，從而節(jié)約了大量的內(nèi)存并且極大的提高了運行速度。深度優(yōu)先搜索極大極小樹的方法可以表示為遞歸的形式。如圖5-5-1-2所示： 1 2 3 4 5 6 7圖5-5-1-2 深度優(yōu)先搜索遞歸示例圖中2，3，4三個節(jié)點為1號的子節(jié)點，5，6，7三個節(jié)點為2號的子節(jié)點，運用深度優(yōu)先的方法進(jìn)入1號節(jié)點生成2號節(jié)點，遍歷2號子節(jié)點生成其第一個子節(jié)點5號，5號將評值返回2號節(jié)點，然后刪除5

51、號、6號與7號同樣如此，最后2號從返回值之中選擇極小值返回給1號。同樣方法遍歷3號，4號極其子節(jié)點。最終1號在三個子節(jié)點的返回值中取極大值，這樣擁有極大值的子節(jié)點就是下一步的落子方向。在這個例子中可以看出，在搜索過程中任何時候只需保存與其層數(shù)相同個數(shù)的節(jié)點，上面的例子中就只需要保存3個節(jié)點就可以了。上述算法已經(jīng)可以完成設(shè)計的基本要求了。5.5.2 核心算法人機(jī)對戰(zhàn)模塊的算法是本次設(shè)計的核心。主體思想分為以下三個步驟：（1）根據(jù)對弈雙方當(dāng)前的形勢循環(huán)假設(shè)性的分別給我方和對方在某個范圍內(nèi)下一子，并判斷此棋子能帶來的形勢上的變化，如能不能沖4，能不能形成我方或敵方雙3等絕殺棋子；（2）根據(jù)上一步結(jié)果

52、，組合每一步棋子所帶來的所有結(jié)果，如對弈雙方某一步棋子可能形成我方1個活3，1個沖4等；（3）根據(jù)用戶給的規(guī)則對上一步結(jié)果進(jìn)行排序分析，并選擇防守或者進(jìn)攻，在最優(yōu)位置落子。算法分析流程如圖5-5-2-1所示：開始游戲在制造活4處落子，不繼續(xù)分析第二次搜索 第一次搜索掃描所以空白點拋棄該點落第一個子計算搜索范圍清空上一輪搜索結(jié)果是否在搜索范圍內(nèi)，是否能連成五子，是否為活1，半活2是否有一方即將勝利是否有一方能制造活4 找出最佳落子位置整理出能制造活3，半活4等棋型的位置第三次搜索在即將勝利位置落子，不繼續(xù)分析否是否是否圖5-2-2-1 算法分析流程圖人機(jī)對戰(zhàn)中電腦AI的算法主要分為三次搜索分析，

53、根據(jù)設(shè)計中代碼的實例對三大步驟進(jìn)行分析說明：第一次搜索分析：首先需初始化搜索分析的運算范圍，如果選擇對整個棋盤進(jìn)行計算，會大大降低運算效率，所以在選定搜索分析運算范圍時，根據(jù)已下的棋子對其邊界值加1。之后對已下黑白棋子分別進(jìn)行遍歷，若棋子在搜索范圍內(nèi)，則當(dāng)前搜索分析范圍不變，若棋子不在搜索范圍內(nèi)，就需對當(dāng)前搜索分析范圍進(jìn)行修改使搜索棋子在當(dāng)前搜索分析范圍內(nèi)。在搜索分析范圍內(nèi)掃描空白點，搜尋可以形成五子連珠的空白點，若不能形成五子連珠則搜索分析對手落子，能否形成活4、活3、半活4等絕殺棋子。即對弈雙方是否有形成勝利的落子位置，若有則在此點落子，否則繼續(xù)搜索分析。同時分析每一步棋在各個方向上的可連

54、續(xù)數(shù)和狀態(tài)，即一頭通還是兩頭通。最后把此步棋的各個方向會形成的結(jié)果生成相應(yīng)對象。在此部分系統(tǒng)對分開分析黑白雙方的第一次搜索結(jié)果，以便減少搜索時間、提高系統(tǒng)效率。第一次搜索分析流程如圖5-5-2-2所示：記錄一個點坐標(biāo)假設(shè)電腦下棋橫向縱向斜向反斜向成5返回結(jié)果YYYYNNN回到原坐標(biāo)點假設(shè)玩家下棋無返回結(jié)果第一次分析圖5-5-2-2 第一次搜索分析流程圖第二次搜索分析：對第一次搜索結(jié)果進(jìn)行分析，把第一次搜索分析生成的四個對象組合在一起，生成一個對象。具體方法是搜索分析雙方能否制造出絕殺棋子。搜索對弈雙方能否制造出活4，若有一方能制造出活4，則在能制造出活4位置落子，不繼續(xù)搜索分析。若沒有此情況，

55、則退而求其次搜索出對弈雙方可以制造出活3、半活4、雙活3、半活3、雙活2、活2的點的位置。第三次搜索分析：進(jìn)行到第三次搜索分析說明前兩次雙方都沒有形成五子連珠、活4等絕殺棋型。第三次搜索分析利用第二次搜索分析的結(jié)果進(jìn)行分析比較，在選擇最佳落子位置時，首先進(jìn)行防守判斷。判斷玩家的棋型、棋勢能否對電腦AI造成威脅，例如制造絕殺棋等情況。具體判斷順序為玩家是否有活4，玩家是否有雙活3，玩家是否有沖4，玩家是否有沖雙活3。若判斷玩家的棋局不會對電腦造成威脅，則不需要進(jìn)行防守，轉(zhuǎn)而尋求進(jìn)攻。具體方法為先找電腦AI能否制造活4，不能制造活4就找能否制造雙活3，不能制造雙活3就找能否制造沖4，不能制造沖4就

56、找能否制造單活3，不能制造單活3就找能否制造雙活2，不能制造雙活2的話就只能找能否制造單活2了。這個過程是是選擇一個對玩家威脅較大的位置進(jìn)行落子。第三次搜索分析的核心是優(yōu)先選擇防守，若搜索分析后玩家不對電腦AI具有威脅，則選擇最優(yōu)位置下棋開始進(jìn)攻。人工智能流程如圖5-2-2-3所示：是否有沖4對弈開始是否有活4防守是否有沖雙活3能否制造單活2是是否有雙活3進(jìn)攻電腦AI落子能否制造活4能否制造雙活3都否制造沖4能否制造單活3能否制造雙活2是是是是否否否否否否否否否是是是是圖5-2-2-3 人工智能流程圖完成三次搜索分析后，電腦落子控制的分析和運算就基本完成了。AI算法流程如圖5-5-2-4所示 AA成5A落子A勝游戲結(jié)束B成5NYWin（）A落子無返回，假設(shè)輪到B落子，B落一子Win（）B活3A落子Win（）A落子A為電腦AI，B為玩家圖 5-5-2-4 AI算法流程示意圖5.5.3 主控制模塊游戲中雙方下棋順序