汽修網(wǎng)站建設(shè)免費(fèi)推廣營(yíng)銷(xiāo)平臺(tái)
井字游戲
EE-551 Python 項(xiàng)目
客觀(guān)的:
這個(gè) EE-551 項(xiàng)目旨在使用 python 開(kāi)發(fā)一個(gè) Tic Tac Toe 游戲。它主要包括開(kāi)發(fā)和實(shí)現(xiàn)一個(gè)計(jì)算機(jī)程序,該程序可以與另一個(gè)玩家玩 Tic Tac Toe。
為了了解什么是井字游戲以及如何玩游戲,以下是說(shuō)明。
游戲說(shuō)明:
Tic Tac Toe 是一種兩人游戲(其中一個(gè)由計(jì)算機(jī)或人類(lèi)玩)。在這個(gè)游戲中,有一個(gè) 3 x 3 方格的棋盤(pán)。
兩名玩家輪流在 3x3 棋盤(pán)上打分。Tic Tac Toe 游戲的目標(biāo)是成為在 3 x 3 網(wǎng)格上水平、垂直或?qū)蔷€(xiàn)獲得三個(gè)相同符號(hào)的玩家之一。最先獲得 3 個(gè)他/她的符號(hào)(標(biāo)記)的玩家 - 垂直、水平或?qū)蔷€(xiàn)贏得游戲,另一個(gè)玩家輸?shù)粲螒?。游戲可以由兩個(gè)玩家玩。玩家有兩種選擇:(a) 人類(lèi) (b) 計(jì)算機(jī)
游戲規(guī)則:
玩家可以與對(duì)手在兩個(gè)符號(hào)之間進(jìn)行選擇,通常的游戲使用“X”和“O”。
-
先上場(chǎng)的玩家將獲得“X”標(biāo)記(我們稱(chēng)他/她的玩家為 1),第二位上場(chǎng)的玩家將獲得“O”標(biāo)記(我們稱(chēng)他/她為玩家 2)。
-
玩家 1 和 2 輪流走棋,玩家 1 玩標(biāo)記“X”,玩家 2 玩標(biāo)記“O”。
-
玩家用他的標(biāo)記(“X”或“O”)標(biāo)記任何 3x3 方格,他們的目標(biāo)是創(chuàng)建一條水平、垂直或?qū)蔷€(xiàn)的直線(xiàn),有兩個(gè)意圖:
a.?一名玩家連續(xù)獲得三個(gè)他/她的分?jǐn)?shù)(垂直、水平或?qū)蔷€(xiàn)),即該玩家贏得游戲。
灣?如果沒(méi)有人可以用自己的標(biāo)記創(chuàng)建一條直線(xiàn),并且棋盤(pán)上的所有位置都被占用,則游戲以平局/平局結(jié)束。
實(shí)施計(jì)劃:
本項(xiàng)目的實(shí)施工作流程如下:
為了可視化定義的游戲規(guī)則和描述,游戲如下圖所示。
首先,游戲?qū)目掌灞P(pán)開(kāi)始。
然后玩家 1 將通過(guò)在該板上打標(biāo)記“X”來(lái)移動(dòng)。然后玩家 2 將通過(guò)在該板上打標(biāo)記“O”來(lái)移動(dòng)。這將繼續(xù)下去,直到棋盤(pán)上滿(mǎn)是分?jǐn)?shù)。
然后程序?qū)z查是“X”的玩家 1 獲勝還是“O”的玩家 2 獲勝,并且該場(chǎng)景將如下:(可以是垂直、水平或?qū)蔷€(xiàn))。
如果沒(méi)有玩家獲勝,程序?qū)z查平局。
所有這些決策都是通過(guò)使用 Minimax 算法完成的。
極大極小算法
Minimax 是一種應(yīng)用于兩人 Tic Tac Toe 游戲的人工智能算法。這種游戲被稱(chēng)為零和游戲,因?yàn)樵跀?shù)學(xué)表示中:一個(gè)玩家贏(+1),另一個(gè)玩家輸(-1)或兩個(gè)人都輸(0)。
Minimax 是一種遞歸算法,用于選擇導(dǎo)致 Max 玩家贏或不輸(平局)的最佳移動(dòng)。它考慮游戲的當(dāng)前狀態(tài)和該狀態(tài)下的可用移動(dòng),然后對(duì)于它播放的每個(gè)有效移動(dòng)(交替最小和最大),直到找到最終狀態(tài) - 贏、平或輸。
它的目標(biāo)是最小化最大損失,即最小化最壞情況。
舉例說(shuō)明
為了應(yīng)用這一點(diǎn),讓我們舉一個(gè)游戲快結(jié)束時(shí)的例子,輪到我了。我是 X。顯然,我在這里的目標(biāo)是最大化我的最終游戲得分。
如果這張圖片的頂部代表輪到我時(shí)的游戲狀態(tài),那么我有一些選擇,我可以玩三個(gè)地方,其中一個(gè)明顯導(dǎo)致我獲勝并獲得 10 分。如果我不這樣做,O 很容易獲勝。而且我不希望 O 贏,所以我在這里的目標(biāo),作為第一個(gè)球員,應(yīng)該是選擇最大的得分動(dòng)作。
但是O呢?
我們應(yīng)該假設(shè) O 也在玩贏得這場(chǎng)比賽,但相對(duì)于我們,第一個(gè)玩家,O 想要選擇給我們帶來(lái)最差分?jǐn)?shù)的移動(dòng),它想要選擇一個(gè)可以最小化我們最終的移動(dòng)分?jǐn)?shù)。讓我們從 O 的角度來(lái)看事情,從上面的另外兩個(gè)游戲狀態(tài)開(kāi)始,我們不會(huì)立即獲勝。
選擇很明確,O 會(huì)選擇任何導(dǎo)致得分為 -10 的動(dòng)作。
描述極小極大
Minimax 算法的關(guān)鍵是兩個(gè)玩家之間的來(lái)回,其中“輪到它”的玩家希望選擇得分最高的移動(dòng)。反過(guò)來(lái),每個(gè)可用移動(dòng)的分?jǐn)?shù)由對(duì)方玩家決定其可用移動(dòng)中的哪個(gè)具有最低分?jǐn)?shù)來(lái)確定。對(duì)手玩家移動(dòng)的分?jǐn)?shù)再次由試圖最大化其分?jǐn)?shù)的輪流玩家決定,依此類(lèi)推,一直到移動(dòng)樹(shù)到結(jié)束狀態(tài)。
算法的描述,假設(shè) X 是輪到玩家:
- 如果游戲結(jié)束,從 X 的角度返回分?jǐn)?shù)。
- 否則,獲取每個(gè)可能移動(dòng)的新游戲狀態(tài)列表。
- 創(chuàng)建分?jǐn)?shù)列表。
- 對(duì)于這些狀態(tài)中的每一個(gè),將該狀態(tài)的極小極大結(jié)果添加到分?jǐn)?shù)列表中。
- 如果輪到 X,則返回分?jǐn)?shù)列表中的最高分?jǐn)?shù)。
- 如果輪到 O,則返回分?jǐn)?shù)列表中的最低分?jǐn)?shù)。
讓我們用完整的走法樹(shù)來(lái)看看算法的執(zhí)行過(guò)程,并從算法上看,如何選擇即時(shí)獲勝的走法:
- 輪到 X 進(jìn)入狀態(tài) 1。X 生成狀態(tài) 2、3 和 4,并在這些狀態(tài)上調(diào)用 minimax。
- 狀態(tài) 2 將 +10 的分?jǐn)?shù)推送到狀態(tài) 1 的分?jǐn)?shù)列表,因?yàn)橛螒蛱幱诮Y(jié)束狀態(tài)。
- 狀態(tài) 3 和 4 不在結(jié)束狀態(tài),因此 3 生成狀態(tài) 5 和 6 并對(duì)其調(diào)用 minimax,而狀態(tài) 4 生成狀態(tài) 7 和 8 并對(duì)其調(diào)用 minimax。
- 狀態(tài) 5 將 -10 的分?jǐn)?shù)推送到狀態(tài) 3 的分?jǐn)?shù)列表,而狀態(tài) 7 也會(huì)發(fā)生同樣的情況,將 -10 的分?jǐn)?shù)推送到狀態(tài) 4 的分?jǐn)?shù)列表。
- 狀態(tài) 6 和 8 生成唯一可用的移動(dòng),即結(jié)束狀態(tài),因此它們都將 +10 的分?jǐn)?shù)添加到狀態(tài) 3 和 4 的移動(dòng)列表中。
- 因?yàn)樵跔顟B(tài) 3 和狀態(tài) 4 中輪到 O,所以 O 將尋求找到最小分?jǐn)?shù),并且在 -10 和 +10 之間進(jìn)行選擇時(shí),狀態(tài) 3 和 4 都將產(chǎn)生 -10。
- 最后,狀態(tài) 2、3 和 4 的得分列表分別用 +10、-10 和 -10 填充,尋求最大化得分的狀態(tài) 1 將選擇得分為 +10 的獲勝棋步,狀態(tài) 2。
讓我們通過(guò)查看可能的移動(dòng)樹(shù)來(lái)看看這里發(fā)生了什么:
- 給定棋盤(pán)狀態(tài) 1,其中兩個(gè)玩家都玩得很完美,而 O 是計(jì)算機(jī)玩家。O 在狀態(tài) 5 中選擇了移動(dòng),然后當(dāng) X 在狀態(tài) 9 中獲勝時(shí)立即失敗。
- 但是如果 O 像狀態(tài) 3 那樣阻止 X 的勝利,那么 X 顯然會(huì)阻止 O 的潛在勝利,如狀態(tài) 7 所示。
- 如狀態(tài) 10 和 11 所示,這為 X 帶來(lái)了兩次確定的勝利,因此無(wú)論 O 在狀態(tài) 7 中選擇哪一步,X 最終都會(huì)獲勝。
該算法的另一個(gè)重要因素是深度。
該算法的關(guān)鍵改進(jìn)是考慮到游戲結(jié)束的“深度”或回合數(shù),無(wú)論棋盤(pán)安排如何,完美的玩家都會(huì)完美地玩?;旧贤昝赖那騿T應(yīng)該完美地打球,但盡可能地延長(zhǎng)比賽時(shí)間。
所以每次我們調(diào)用 minimax 時(shí),深度都會(huì)增加 1,當(dāng)最終計(jì)算結(jié)束游戲狀態(tài)時(shí),分?jǐn)?shù)會(huì)根據(jù)深度進(jìn)行調(diào)整。
由于這是一個(gè)非常復(fù)雜的算法,我們有一臺(tái)計(jì)算機(jī)來(lái)執(zhí)行這個(gè)算法。
代碼實(shí)施
-
為了運(yùn)行此代碼,需要安裝 pygame 庫(kù)。要安裝它,請(qǐng)打開(kāi)命令提示符并鍵入“pip install pygame”。
-
運(yùn)行完整代碼 TicTacToeGame.ipynb。
-
運(yùn)行代碼后,屏幕上將顯示以下窗口(空板):
-
游戲包含兩個(gè)按鈕 - vs Human 和 vs AI,以便我們可以選擇我們的對(duì)手。一旦我們點(diǎn)擊按鈕,通過(guò)點(diǎn)擊游戲板開(kāi)始玩游戲。由于我們先玩,我們將被定義為玩家 X。
-
游戲結(jié)束后,游戲屏幕上將顯示獲勝者姓名(X 或 O)或抽獎(jiǎng)游戲的消息。