井字游戲

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”。

1. 先上場(chǎng)的玩家將獲得“X”標(biāo)記（我們稱(chēng)他/她的玩家為 1），第二位上場(chǎng)的玩家將獲得“O”標(biāo)記（我們稱(chēng)他/她為玩家 2）。

2. 玩家 1 和 2 輪流走棋，玩家 1 玩標(biāo)記“X”，玩家 2 玩標(biāo)記“O”。

3. 玩家用他的標(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)游戲的消息。