基于Android的五子棋游戲的算法分析

鄒元杰

【摘要】五子棋起源于中國(guó)古代的傳統(tǒng)黑白棋種之一，它不僅能增強(qiáng)思維能力 提高智力，而且富含哲理，有助于修身養(yǎng)性。本文主要闡述以eclipse為開(kāi)發(fā)工具， 基于智能手機(jī)Android設(shè)計(jì)一個(gè)五子棋游戲，并對(duì)其中相關(guān)算法進(jìn)行研究。

【關(guān)鍵詞】Android 五子棋 算法

一、Android開(kāi)發(fā)環(huán)境介紹

Android的上層應(yīng)用程序是使用的Java語(yǔ)言開(kāi)發(fā)，同時(shí)還需要基于Dalvik虛擬機(jī)。所以，Google公司推薦使用主流的Java去繼承開(kāi)發(fā)環(huán)境Eclipse。不過(guò)只有Eclipse還是遠(yuǎn)遠(yuǎn)不夠的，因?yàn)槭鞘褂肑ava語(yǔ)言進(jìn)行開(kāi)發(fā)，所以這部分還應(yīng)該有由SUN公司提供的Java SDK（其中包括JRE：Java Runtime Environment）。此外，Android的應(yīng)用程序開(kāi)發(fā)和Java開(kāi)發(fā)有較大區(qū)別的，所以還需要有Google提供的Android SDK。在Eclipse上安裝一個(gè)AVD的虛擬機(jī)也是必要的。同時(shí)，還需要在Eclipse安裝ADT，使得在有更新程序的時(shí)候可以能夠?yàn)锳ndroid開(kāi)發(fā)提供開(kāi)發(fā)工具的升級(jí)或者變更，也是Eclipse下開(kāi)發(fā)工具的升級(jí)下載的工具。

二、Android應(yīng)用程序組件

Android的一個(gè)主要特點(diǎn)是，一個(gè)應(yīng)用程序可以利用其他應(yīng)用程序的元素（假設(shè)這些應(yīng)用程序允許的話）。例如，如果你的應(yīng)用程序需要顯示一個(gè)圖像的滾動(dòng)列表，且其他應(yīng)用程序已經(jīng)開(kāi)發(fā)了一個(gè)合適的滾動(dòng)條并可以提供給別的應(yīng)用程序用，你可以調(diào)用這個(gè)滾動(dòng)條來(lái)工作，而不用自己開(kāi)發(fā)一個(gè)。你的應(yīng)用程序不用并入其他應(yīng)用程序的代碼或鏈接到它。相反，當(dāng)需求產(chǎn)生時(shí)它只是啟動(dòng)其他應(yīng)用程序塊。

對(duì)于這個(gè)工作，當(dāng)應(yīng)用程序的任何部分被請(qǐng)求時(shí)，系統(tǒng)必須能夠啟動(dòng)一個(gè)應(yīng)用程序的進(jìn)程，并實(shí)例化該部分的Java對(duì)象。因此，不像其他大多數(shù)系統(tǒng)的應(yīng)用程序，Android應(yīng)用程序沒(méi)有一個(gè)單一的入口點(diǎn)（例如，沒(méi)有main（）函數(shù)）。相反，系統(tǒng)能夠?qū)嵗瓦\(yùn)行需要幾個(gè)必要的組件。有四種類型的組件：活動(dòng)（Activities）、服務(wù)（Services）、廣播接收者（Broadcast receivers）、內(nèi)容提供者（Content providers）。

然而，并不是所有的應(yīng)用程序都必須包含上面的四個(gè)部分，你的應(yīng)用程序可以由上面的一個(gè)或幾個(gè)來(lái)組建。當(dāng)你決定使用以上哪些組件來(lái)構(gòu)建Android應(yīng)用程序時(shí)，你應(yīng)該將它們列在AndroidManifest.xml文件中，在這個(gè)文件中你可以聲明應(yīng)用程序組件以及它們的特性和要求。

三、設(shè)計(jì)思路

此游戲主要是采用Android的View框架編寫，部分框架運(yùn)用Android中的其他組件。主要運(yùn)用了算法來(lái)實(shí)現(xiàn)對(duì)棋局的分析，棋盤輸贏的判定。

UI方面：此游戲當(dāng)進(jìn)入游戲的界面時(shí)，調(diào)用的是一個(gè)用相對(duì)布局-AbsoluteLayout的XML布局文件。其中包括了一個(gè)IamgeView和4個(gè)Button.分別實(shí)現(xiàn)了不同的功能。第一個(gè)Button是進(jìn)入新游戲，點(diǎn)擊按鈕進(jìn)入新游戲，來(lái)選擇對(duì)手。第二個(gè)Button是幫助，用了一個(gè)TextView來(lái)說(shuō)明怎樣來(lái)進(jìn)行游戲。第三個(gè)Button是游戲的關(guān)于，用了一個(gè)AlertDialog來(lái)介紹了一下游戲的這個(gè)游戲的好處。第四個(gè)Button是游戲的退出按鈕。在游戲中，用畫線來(lái)布滿了整個(gè)的手機(jī)屏幕，在上面用了TextView來(lái)進(jìn)行了文字的說(shuō)明和提示。

四、相關(guān)的算法研究

關(guān)于盤面情況的表示，首先得到屏幕的大小，然后根據(jù)所畫棋子的大小來(lái)確定下一條棋盤的畫線。產(chǎn)生棋盤上所有的線。分析規(guī)則中，判斷各個(gè)四個(gè)方向的棋子：在某個(gè)方向（八個(gè)中的一個(gè)）可下多少棋子，判斷是否還能下到滿5個(gè)棋子，最核心的應(yīng)該是勝負(fù)判斷，實(shí)際上，是根據(jù)當(dāng)前最后一個(gè)落子的情況來(lái)判斷勝負(fù)的。需要從四個(gè)位置判斷，以該子為出發(fā)點(diǎn)的水平，豎直和兩條分別為 45度角和135度角的線，目的是看在這四個(gè)方向是否最后落子的一方構(gòu)成連續(xù)五個(gè)的棋子，如果是的話，就表示該盤棋局已經(jīng)分出勝負(fù)。部分核心算法實(shí)現(xiàn)如下：

開(kāi)始分析，掃描所有空白點(diǎn)，形成第一次分析結(jié)果；

第二次分析，分析第一次形成的結(jié)果，第一次分析結(jié)果會(huì)把一步棋在四個(gè)方向上可形成的結(jié)果生成最多四個(gè)FirstAnalysisResult對(duì)象（敵我各四）；

第三次分析，雙方都不可以制造活4，找雙活3棋子，不行就找半活4，再不行就找單活3，雙活2；endprint