科大訊飛 ai算法挑戰賽

by Ben Carp

通過本·卡爾普

為井字游戲挑戰構建AI算法 (Building an AI algorithm for the Tic-Tac-Toe challenge)

As part of the freeCodeCamp curriculum, I was challenged build a Tic-Tac-Toe web app. It was a real pleasure.

作為freeCodeCamp課程的一部分，我遇到了構建Tic-Tac-Toe網絡應用程序的挑戰。 真的很高興。

The app includes an ultimate computer player. It can optimize any given situation on the Tic-Tac-Toe board. The outcome surprised me.

該應用程序包括一個終極的計算機播放器。 它可以優化井字游戲板上的任何給定情況。 結果使我感到驚訝。

Even in such a simple game, the computer player taught me some new moves. As for the code I wrote, it is somewhat unique and interesting to explore.

即使在這樣簡單的游戲中，計算機玩家也會教給我一些新的動作。 至于我編寫的代碼，它有些獨特且有趣。

看看這個 (Check it out)

Visit this link and choose to play against the computer. I challenge you to win. You might find…that you can’t.

訪問此鏈接，然后選擇與計算機對戰。 我挑戰你贏 。 您可能會發現……您做不到。

Yet, if you are hard on the defense, you might find out that the computer is not able to win either. I learned by experience that Tic-Tac-Toe has a simple non-lose strategy.

但是，如果您在防御上很努力，則可能會發現計算機也無法獲勝。 我從經驗中學到，井字游戲有一個簡單的不輸球策略。

This means that if you manage to get a tie you are making the right defensive choices. The computer still optimizes its’ moves. So, the best result it can achieve against a player such as yourself might only be a tie.

這意味著，如果您設法獲得平局，那么您將做出正確的防守選擇。 電腦仍在優化其動作。 因此，對您這樣的玩家所能達到的最佳結果可能只是平局。

主要解決方案步驟 (Main Solution steps)

1.板子數據結構 (1. board data structure)

_gameBoard: [[“”, “”, “”],[“”, “”, “”],[“”, “”, “”]]

The board Array contains 3 arrays, each representing a row.Each row array contains 3 character or string elements.

板子數組包含3個數組，每個數組代表一行。每個行數組包含3個字符或字符串元素。

These elements are either:

這些元素是：

• “ ” as an empty string, representing an empty cell
  “”為空字符串，表示一個空單元格
• “X” representing the X player
  代表X播放器的“ X”
• “O” representing the O player
  代表O玩家的“ O”

2. getResult函數 (2. getResult function)

Begins at Line 59

從第59行開始

At any given state, the board will be in one and one only of these possible states:

在任何給定狀態下，董事會將處于以下一種或一種可能的狀態：

• Incomplete
  不完整
• player X won
  玩家X贏了
• Player O won
  玩家O贏了
• or a tie
  或領帶

The getResult function receives a board array, iterates over all the rows, through all the columns and across both diagonals. It checks the succession of symbols. Then it lets us know the current state of that board.

getResult函數接收一個board數組，遍歷所有行，所有列以及兩個對角線。 它檢查符號的連續性。 然后，它讓我們知道該板的當前狀態。

3. getBestMove函數 (3. getBestMove Function)

Here it gets more difficult. When the board is empty it is very difficult to identify the best possible move. Take a look at this board.

在這里變得更加困難。 當木板為空時，很難確定最佳移動方式。 看一下這個板子。

Which is the best possible possible move?

哪個可能是最好的舉動？

When the board becomes populated, the best possible move pops out to our eyes.

當木板裝滿時，最好的動作突然出現在我們眼前。

Let’s use this populated board as our starting point. Lets decide that the next move is ours, and that our symbol is an “X”.

讓我們以填充的木板為起點。 讓我們決定下一步是我們的行動，我們的符號是“ X”。

Let’s try to identify the best possible move with the tools we already have. There are 3 empty cells that correspond with 3 possible moves. Lets check the result for each of these options.

讓我們嘗試使用我們現有的工具來確定最佳的移動方式。 有3個空單元格，它們對應3種可能的移動。 讓我們檢查每個選項的結果。

We can do this by iterating over the possible moves, and for each of them:

我們可以通過迭代可能的移動來實現此目的，對于每個移動：

• Create a new board
  創建一個新板
• Add our symbol to the corresponding empty cell
  將我們的符號添加到相應的空單元格中

• Send this board to the getResult function

  將該板發送到getResult函數

From the 3 boards in the figure above, when we send the second board to the getResult function, we will receive our trophy.

從上圖中的3個板中，當我們將第二個板發送到getResult函數時，我們將獲得獎杯。

Please concentrate for the next essential steps:

請集中精力進行以下基本步驟：

1. We need to grade the possible moves so we can compare them. Let’s decide that if a move yields a winning board we will grade it 1. If it yields a losing board it will receive the grade of -1. A tie will receive a grade of 0.
   我們需要對可能的移動進行分級，以便可以對其進行比較。 讓我們決定，如果一個舉動產生一個獲勝的棋盤，我們將其評分為1。如果它產生一個失敗的棋盤，則其評分將為-1。 平局得分為0。
2. Move 2 will receive a grade of 1. When we find a move graded with 1 we can ignore all other possible moves. There is no other better possible move than a definite victory.
   動作2的等級為1。當我們找到等級為1的動作時，我們可以忽略所有其他可能的動作。 沒有比確定的勝利更好的舉動了。
3. But for the sake of understanding, how would we grade moves 1 or 3, or any other move with an incomplete result?
   但是為了理解，我們將如何對第1或第3步或任何其他結果不完整的步進行評分？

Let’s Focus on move 3. The solution is to send the corresponding board recursively to the getBestMove function.

讓我們關注移動3。解決方案是將相應的板遞歸發送到getBestMove函數。

You might be thinking, “But wait! Our opponent plays the next move.” That’s right. Let’s find out what grade our opponent gets for his best future move.

您可能會想，“但是等等！ 我們的對手下一個動作。” 那就對了。 讓我們找出對手最好的未來舉動所獲得的等級。

Our opponent has only two possible moves:

我們的對手只有兩個可能的舉動：

Move 3–1 will win the game in favor of our opponent. Since we are using the exact same getBestMove function, Move 3–1 will receive a grade of 1.

3–1的舉動將贏得我們對手的勝利。 由于我們使用的是完全相同的getBestMove函數，因此Move 3–1的等級為1。

This might be a bit confusing as both our victory and our loss will receive grades of 1. We need to remember that this function call belongs to our opponent, and his victory is our loss and vice versa.

這可能有點令人困惑，因為我們的勝利和失敗都將得到1級。我們需要記住，此函數調用屬于我們的對手，而他的勝利就是我們的失敗，反之亦然。

We must negate any grade returned to the getBestMove function by the getBestMove function.

我們必須取消由getBestMove函數返回給getBestMove函數的任何成績。

Move 3–1 receives a grade of 1. The getBestMove function returns a grade of 1, and we can grade Move 3 with a -1.

移動3-1的等級為getBestMove函數返回的等級為1，我們可以將移動3的等級getBestMove -1。

In this manner, the getBestMove function continues to explore moves and consequent moves. This process will continue until:

以這種方式， getBestMove函數繼續探索移動以及隨后的移動。 該過程將持續到：

1. It finds a move graded with 1, in which case it will return the move immediately
   它會找到等級為1的移動，在這種情況下，它將立即返回該移動
2. It will continue until each possible move has a grade. The possible moves (with grades 0 and -1) are stored in an array
   它將繼續，直到每個可能的動作都得到評分。 可能的移動(等級0和-1)存儲在數組中

3. The array will then be:

   該數組將是：

   [a] randomized

   [a]隨機

   [b] sorted from high to low

   [b]從高到低排序

   [c] the first element will be returned

   [c]第一個元素將被返回

These steps guarantee that:

這些步驟保證：

1. A losing move will be avoided unless it’s the only option
   除非是唯一的選擇，否則將避免失敗。
2. The computer player can play diversely
   電腦播放器可以玩多種游戲

尾注： (End Notes:)

1. There are strong legitimate concerns over the risks Artificial Intelligence (AI) brings with it.

   人們對人工智能(AI)帶來的風險有強烈的正當擔憂。

   Lets use AI for the benefit of all.

   讓AI造福所有人。

   The best possible AI software is that which can prevent us from misusing AI.

   最好的AI軟件是可以防止我們濫用AI的軟件。

2. I consulted Assaf Weinberg in the process of writing the app

   在編寫應用程序的過程中，我咨詢了阿薩夫·溫伯格 ( Assaf Weinberg)

See my code on GitHub.

在GitHub上查看我的代碼 。

翻譯自: https://www.freecodecamp.org/news/building-an-ai-algorithm-for-the-tic-tac-toe-challenge-29d4d5adee07/

科大訊飛 ai算法挑戰賽