基于c語言的井字棋設(shè)計(jì)

基于c語言的井字棋設(shè)計(jì)

c-語言通常是計(jì)算機(jī)和計(jì)算機(jī)的第一門編程語言。這是對計(jì)算機(jī)課程的補(bǔ)充。學(xué)生的掌握直接影響到后續(xù)課程的學(xué)習(xí)。受到語言特點(diǎn)和程度深淺的限制，學(xué)生往往對教材上字符界面的習(xí)題提不起興趣，再加上初學(xué)者對于語言本身的接受需要一個(gè)較長的過程，導(dǎo)致很多學(xué)生在學(xué)習(xí)過程中感覺C語言的學(xué)習(xí)枯燥，學(xué)習(xí)效果不佳。為了提高學(xué)生的學(xué)習(xí)興趣，并使他們掌握一些編程方法，作者用C語言設(shè)計(jì)了一個(gè)簡單的井字棋游戲，希望能使廣大初學(xué)者掌握一些編程方法并提高程序設(shè)計(jì)興趣。1.基于不同顏色的上最優(yōu)氫規(guī)則井字棋是一款常見的兩人對戰(zhàn)的小游戲，玩法簡單。設(shè)有九個(gè)空格，由MAX,MIN二人對弈，兩玩家分別執(zhí)不同顏色的棋子，輪流放入在3×3的棋盤中，一個(gè)格子只能放一個(gè)棋子，誰先使自己的棋子構(gòu)成“三子成一線”(同一行或列或?qū)蔷€全是某人的棋子)，就可以判定為獲勝。2.．空著性條件評估函數(shù)主要用來在游戲搜索算法中對當(dāng)前局面的優(yōu)劣程度進(jìn)行估值，確定評估函數(shù)值所依據(jù)的知識(shí)通常是該游戲領(lǐng)域的經(jīng)驗(yàn)值和直觀判斷的知識(shí)。在游戲搜索算法中，評估函數(shù)是一個(gè)核心函數(shù)，該函數(shù)的好壞直接影響到程序的搜索速度和人工智能水平的高低。井字棋中，用叉號(hào)表示MAX，用圓圈代表MIN。比如圖1中就是MIN取勝的棋局。估價(jià)函數(shù)定義如下：設(shè)棋局為P，估價(jià)函數(shù)為e(P)。(1)若P對任何一方來說都不是獲勝的位置，則e(P)=e(那些仍為MAX空著的完全的行、列或?qū)蔷€的總數(shù))-e(那些仍為MIN空著的完全的行、列或?qū)蔷€的總數(shù))(2)若P是MAX必勝的棋局，則e(P)=+∞。(3)若P是MIN必勝的棋局，則e(P)=-∞。對于MAX來說，e(P)值越大則對自己最有利，對MIN最不利，所以簡單地說，計(jì)算機(jī)棋手做判斷的依據(jù)就是評估函數(shù)的值，尋找最大的那個(gè)。3.生成節(jié)點(diǎn)評估函數(shù)為了獲得最優(yōu)的落子位置，在算法中首先要生成搜索樹。作者把States作為樹根節(jié)點(diǎn)，根節(jié)點(diǎn)所在的層是極大層（MAX層），然后通過向棋盤中沒有落子的空格添一個(gè)對方的棋子生成下一層（極小層，MIN層）的樹節(jié)點(diǎn)，如果當(dāng)前樹的高度大于等于TREE＿DEPTH（>=1）全局變量，則停止生成節(jié)點(diǎn)，否則則繼續(xù)生成下一層節(jié)點(diǎn)（如果當(dāng)前節(jié)點(diǎn)層為MIN層，則下一層為MAX層，否則，則下一層為MIN層）。生成每一層時(shí)可為每一層的屬性（MAX或MIN）做標(biāo)記，生成每個(gè)節(jié)點(diǎn)時(shí)，應(yīng)計(jì)算這個(gè)節(jié)點(diǎn)的評估函數(shù)值，并將其保存在狀態(tài)節(jié)點(diǎn)的e域中。因?yàn)閷哟伪闅v會(huì)修改非葉節(jié)點(diǎn)的極大極小值，而且非葉節(jié)點(diǎn)原來的極大極小值會(huì)對其來自其子女節(jié)點(diǎn)的極大極小值產(chǎn)生影響（比如，如果一個(gè)非葉節(jié)點(diǎn)的極大極小值大于或小于其子女節(jié)點(diǎn)中的最大者或小于其中的最小者，則導(dǎo)致其評估函數(shù)值無法更新）。所以非葉節(jié)點(diǎn)沒有必要也不能保存。然后，通過層次遍歷獲得每個(gè)非葉節(jié)點(diǎn)的評估函數(shù)值，同時(shí)將非葉節(jié)點(diǎn)的bestChild域指向最佳子女，從而形成一條從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的最佳解路徑。最后，將當(dāng)前的棋局更新為其最優(yōu)子女節(jié)點(diǎn)的棋局，并獲得落子的位置。4.狀態(tài)節(jié)點(diǎn)的生成由于本程序采用的核心算法是極大極小分析法，所以，在實(shí)現(xiàn)算法之前，必須定義一些數(shù)據(jù)結(jié)構(gòu)來保存生成的狀態(tài)節(jié)點(diǎn)。因此，作者定義了State結(jié)構(gòu)：作者使用了States[MAX＿NUM]數(shù)組來保存生成的狀態(tài)節(jié)點(diǎn)，通過State結(jié)構(gòu)中的parent、child域構(gòu)成了一個(gè)搜索樹，并通過bestChild域保存了一條從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的最優(yōu)解路徑。特別的，States作為根節(jié)點(diǎn)保存了當(dāng)前的棋局狀態(tài)。為了保存當(dāng)前對弈過程的狀態(tài)信息，作者定義了以下常量：以下常量表示棋局當(dāng)前的狀態(tài)同時(shí)，作者還定義了兩個(gè)3×3的二維數(shù)組，Computer＿move函數(shù)中要用到其中的一個(gè)來保存臨時(shí)的棋盤格局，另一個(gè)則是用來保存上一步的棋盤格局。5.落子的發(fā)現(xiàn)和展示程序經(jīng)過編譯執(zhí)行后，將會(huì)顯示初始棋盤，由9個(gè)“0”組成，程序會(huì)詢問你是否愿意先走棋，選擇先走，輸入“y”；選擇后走，輸入“n”。選擇先走后，程序會(huì)提醒你將要落子的位置，用坐標(biāo)（xy）表示。圖2表示將在（2,2）落子。當(dāng)輸入落子的位置后，程序會(huì)顯示你落子后的棋盤，其中人的棋子用“-1”表示，計(jì)算機(jī)的棋子用“1”表示。然后輪到計(jì)算機(jī)走棋。計(jì)算機(jī)走棋后，程序?qū)@示此時(shí)棋盤的情況，并提醒用戶落子。若干回合后，程序?qū)?huì)根據(jù)勝負(fù)情況輸出比賽的結(jié)果。圖3顯示的是計(jì)算機(jī)取勝的信息。6.利