臧利萍等
摘要:針對Android移動(dòng)終端人機(jī)實(shí)時(shí)交互的特點(diǎn),結(jié)合中國象棋的特點(diǎn),牽涉到Android開發(fā)和Java程序設(shè)計(jì)以及算法分析等相關(guān)知識。即勾勒了整個(gè)程序的結(jié)構(gòu)框架,又詳細(xì)分析和設(shè)計(jì)了其中的功能模塊,例如棋子繪制,局面狀態(tài)變量的意義和變化邏輯,人機(jī)交互的全過程等。全面講解了搜索算法,從棋局表示、走法生成、局面估計(jì)到搜索樹的遍歷和Alpha-Beta剪枝算法。
關(guān)鍵詞:Android;局面估值;Alpha-Beta搜索;歷史表;人機(jī)交互
中圖分類號:TP391 文獻(xiàn)標(biāo)識碼:A 文章編號:1009-3044(2014)32-7742-02
Abstract: This is the feature which is real-time human-computer interaction about android mobile terminal .Combined with the characteristics of Chinese Chess, involving many knowledge of Android development and Java program design and algorithm analysis. Draw the outline of the structure of the entire application framework, and analysis and design of the module in detail, such as chess, situation of state variables and change the meaning of logic, the whole process of human-computer interaction. There is comprehensive interpretation of the search algorithm, from chess said, move generation, situation estimate to search tree traversal and Alpha - Beta pruning algorithm.
Key words:Android; Situation to valuation; Alpha-Beta Search; History lists; Human-computer interaction
1 概述
計(jì)算機(jī)博弈是博弈游戲與計(jì)算機(jī)決策系統(tǒng)的結(jié)合,是人工智能里一個(gè)重要的研究領(lǐng)域,是機(jī)器智能、兵棋推演等領(lǐng)域的科研基礎(chǔ)。中國象棋是中國古老的游戲,邏輯性極強(qiáng),中國象棋模擬涵蓋場景建模、狀態(tài)表示、棋局分布、走法生成、搜索算法等方面,如何實(shí)現(xiàn)中國象棋的人機(jī)對弈顯得尤其重要。
隨著3G技術(shù)和android系統(tǒng)的發(fā)展,智能手機(jī)的市場占有率極高,智能手機(jī)游戲在人們生活中占有重要的位置。中國象棋以它的趣味性、邏輯性、哲理性在棋牌游戲中首屈一指,深受多數(shù)玩家的青睞和熱衷。基于此,本課題的研究和開發(fā)應(yīng)運(yùn)而生,并且更加注重人性化(例如多步悔棋、將軍等棋局狀態(tài)提示)、友好操作接口的設(shè)計(jì)和開發(fā)。程序中隨時(shí)都能進(jìn)行難度設(shè)置,符合多種玩家的技藝要求,并且可以伴隨玩家棋藝水平競相成長。總之,本課題的開發(fā),以逼真的視角,簡便的操作方式,人性化的設(shè)計(jì),生動(dòng)的下棋環(huán)境,定能讓玩家體驗(yàn)到中國象棋的智慧和樂趣。
2 需求分析與設(shè)計(jì)
2.1 歡迎界面
對事物評價(jià)的好壞,第一印象至關(guān)重要。程序是通過設(shè)置兩張精美的中國象棋圖片來啟動(dòng)的,就像放映電影一樣,使游戲更加有厚重感、故事性和趣味性,從而使玩家進(jìn)入純凈高遠(yuǎn)而且玄妙有趣的象棋世界。
2.2 游戲界面
游戲界面是玩家和計(jì)算機(jī)對弈的陣地,是程序繪制棋盤,排布棋子,并走動(dòng)棋子的界面。
游戲界面具有動(dòng)態(tài)智能性,要時(shí)刻反應(yīng)人機(jī)雙方走棋落子的信息,同時(shí)熟知走棋規(guī)則,對玩家的不合理落子予以拒絕,及時(shí)的提醒玩家將軍和被將軍等重要信息。此外還將對玩家舉棋和落子添加聲效處理,對人機(jī)雙方的走棋都標(biāo)識出走棋位置和落子位置,使整個(gè)下棋過程更逼真生動(dòng),交互更加清晰明確。
2.3菜單
菜單處于Android的系統(tǒng)級別。提供人機(jī)下棋的難度等級“容易”、“中等”和“困難”,并給以選擇提示。此外提供悔棋功能,即使在實(shí)物象棋對戰(zhàn)中,棋手們的悔棋也是不可避免的,甚至是人性化的、無可厚非的,更何況程序是通過不總是精確到像素點(diǎn)的觸屏操作呢,并且設(shè)置悔棋步數(shù)限制。玩家在有悔棋需求時(shí),點(diǎn)擊菜單選項(xiàng)中的“悔棋亦君子”來返回上一步的棋局狀態(tài),并同時(shí)計(jì)入悔棋步數(shù)中。
3 搜索算法分析
象棋搜索算法是象棋程序的靈魂,體現(xiàn)程序的健壯性和高效性,是整個(gè)程序設(shè)計(jì)和開發(fā)的關(guān)鍵。
3.1局面表示
局面表示是象棋程序的基礎(chǔ),它的好壞直接關(guān)系到走法生成、局面評估和搜索算法的效率。本象棋程序采用的是16*16的二維數(shù)組表示法。
3.2走法和全局走法生成
走法就是一個(gè)棋子按照象棋的規(guī)則從一個(gè)位置移動(dòng)到另一個(gè)位置。棋子走法所遵循的的走棋規(guī)則被邏輯映射成一個(gè)走棋方向數(shù)組,從棋子的原位置出發(fā),朝著走棋數(shù)組的值所標(biāo)識的方向前進(jìn)并得到棋子的落子位置,記錄這個(gè)走法即可。
在走法數(shù)據(jù)結(jié)構(gòu)和各種棋子走法生成的基礎(chǔ)上,遍歷整個(gè)棋盤,找出當(dāng)前走棋方的棋子,然后逐個(gè)棋子生成其所有可能的走法,全部保存下來,就得到了整個(gè)局面的全部走法。
3.3局面評估
局面評估是判斷局面對紅方(或者黑方)的優(yōu)勢,并把這個(gè)優(yōu)勢量化。目的是為了在多個(gè)局面之間進(jìn)行比較,然后選擇對應(yīng)局面的走法,從而得到有利的局面。endprint