井字棋/三子棋的偽人工智能演算法的實作

一、Abstract

本演算法用于實作井字棋游戲電腦先手情況下的智能落子

二、Introduction

關于井字棋的模塊的搭建，分為棋盤的初始化、棋盤的展示、電腦落子、玩家落子、判斷輸/贏/平局/繼續游戲這5個模塊，

其中，我們著重介紹一下電腦落子的具體演算法，本演算法可以使得玩家永遠贏不了棋局，（輸/平局）

本演算法的核心思想為 暴力列舉 和 迫使玩家進行指定位置的落子
注：

1. 本棋盤為3*3的大小
2. 電腦先手
3. 以下用形如(2,1)的形式表示落子的坐標
4. 用“#”表示電腦的棋子，用“*”表示玩家的棋子
5. 代碼部分使用C語言進行實作

三、Algorithm

Step1

電腦的第一步永遠落于(1,1)

Step2

接下來，玩家落子一共有8個點可供選擇，根據對稱性，我們可以將其分分成5組，它們分別是：

1. (1,2)或(2.1)
2. (1,3)或(3,1)
3. (2,3)或(3,2)
4. (2,2)
5. (3,3)

以下對于每一類情況進行分組討論，每組以其中一種情況進行舉例
藍色的數字表示落子的順序

A.(1,2)

上圖表示玩家第一手落于(1,2)的情況，此時，顯然玩家必輸，
同理，玩家落子于(2,1)，顯然必輸，

B. (1,3)

上圖表示玩家第一手落于(1,3)的情況，此時，顯然玩家必輸，
同理，玩家落子于(3,1)，顯然必輸，

C.(2,3)

上圖表示玩家第一手落于(2,3)的情況，此時，顯然玩家必輸，
同理，玩家落子于(3,2)，顯然必輸，

D.(3,3)

上圖表示玩家第一手落于(3,3)的情況，此時，顯然玩家必輸，

E.(2,2)

上圖表示玩家第一手落于(2,2)的情況，此時，顯然最終雙方會握手言和，

Step3

以下展示電腦落子的代碼

首先需定義棋盤大小

#define ROW 3
#define COL 3

首先創建一個3*3的二維陣列

char board[3][3]={0};

并將二維陣列中每一個元素使用初始化模塊初始化為’ ’ ，也就是空格，此處省略

我們另需封裝一個CountNum函式用來統計棋盤中的9個格子已經有幾個格子上落了子

int CountNum(char board[ROW][COL], int row, int col)
{
	int count = 0;
	int i = 0;
	int j = 0;
	for (i = 0; i < row; i++)
	{
		for (j = 0; j < col; j++)
		{
			if (board[i][j] != ' ')
				count++;
		}
	}
	return count;
}

以下代碼為具體的電腦落子智能演算法，其中引數board表示用來表示棋盤的二維陣列的地址，row為ROW（3），col為COL（3）

void ComputerMove(char board[ROW][COL], int row, int col)
{
	int x = 0;
	int y = 0;
	if (CountNum(board, ROW, COL) == 0)
	{
		board[0][0] = '#';
	}
	if (CountNum(board, ROW, COL) == 2)
	{

		//5 types , 8 situations

		// 1
		if (board[0][1] == '*')
		{
			board[2][0] = '#';
		}
		// 2
		if (board[1][0] == '*')
		{
			board[0][2] = '#';
		}
		// 3 
		if (board[0][2] == '*')
		{
			board[2][2] = '#';
		}
		// 4
		if (board[2][0] == '*')
		{
			board[2][2] = '#';
		}
		// 5
		if (board[2][1] == '*')
		{
			board[2][0] = '#';
		}
		// 6
		if (board[1][2] == '*')
		{
			board[0][2] = '#';
		}
		// 7
		if (board[1][1] == '*')
		{
			board[0][1] = '#';
		}
		// 8
		if (board[2][2] == '*')
		{
			board[0][2] = '#';
		}
	}
	if (CountNum(board, ROW, COL) == 4)
	{
		// 1@1
		if (board[0][1] == '*' && board[2][0] == '#')
		{
			if (board[1][0] == '*')
			{
				board[2][2] = '#';
			}
			else
			{
				board[1][0] = '#';
			}
		}
		// 2@1
		if (board[1][0] == '*' && board[0][2] == '#')
		{
			if (board[0][1] == '*')
			{
				board[2][2] = '#';
			}
			else
			{
				board[0][1] = '#';
			}
		}
		// 3@1
		if (board[0][2] == '*' && board[2][2] == '#')
		{
			if (board[1][1] == '*')
			{
				board[2][0] = '#';
			}
			else
			{
				board[1][1] = '#';
			}
		}
		// 4@1
		if (board[2][0] == '*' && board[2][2] == '#')
		{
			if (board[1][1] == '*')
			{
				board[0][2] = '#';
			}
			else
			{
				board[1][1] = '#';
			}
		}
		// 5@1
		if (board[2][1] == '*' && board[2][0] == '#')
		{
			if (board[1][0] == '*')
			{
				board[0][2] = '#';
			}
			else
			{
				board[1][0] = '#';
			}
		}
		// 6@1
		if (board[1][2] == '*' && board[0][2] == '#')
		{
			if (board[0][1] == '*')
			{
				board[2][0] = '#';
			}
			else
			{
				board[0][1] = '#';
			}
		}
		// 7@1
		if (board[1][1] == '*' && board[0][1] == '#')
		{
			if (board[0][2] == '*')
			{
				board[2][0] = '#';
			}
			else
			{
				board[0][2] = '#';
			}
		}
		// 8@1
		if (board[2][2] == '*' && board[0][2] == '#')
		{
			if (board[0][1] == '*')
			{
				board[2][0] = '#';
			}
			else
			{
				board[0][1] = '#';
			}
		}
	}
	if (CountNum(board, ROW, COL) == 6)
	{
		// 1@1@1
		if (board[0][0] == '#' && board[2][0] == '#' && board[2][2] == '#' && board[0][1] == '*' && board[1][0] == '*')
		{
			if (board[1][1] == ' ')
			{
				board[1][1] = '#';
			}
			else
			{
				board[1][1] = '#';
			}
		}
		// 2@1@1
		if (board[0][0] == '#' && board[0][2] == '#' && board[2][2] == '#' && board[0][1] == '*' && board[1][0] == '*')
		{
			if (board[1][1] == ' ')
			{
				board[1][1] = '#';
			}
			else
			{
				board[1][1] = '#';
			}
		}
		// 3@1@1
		if (board[0][0] == '#' && board[2][0] == '#' && board[2][2] == '#' && board[0][2] == '*' && board[1][1] == '*')
		{
			if (board[1][0] == ' ')
			{
				board[1][0] = '#';
			}
			else
			{
				board[2][1] = '#';
			}
		}
		// 4@1@1
		if (board[0][0] == '#' && board[0][2] == '#' && board[2][2] == '#' && board[2][0] == '*' && board[1][1] == '*')
		{
			if (board[0][1] == ' ')
			{
				board[0][1] = '#';
			}
			else
			{
				board[1][2] = '#';
			}
		}
		// 5@1@1
		if (board[0][0] == '#' && board[2][0] == '#' && board[0][2] == '#' && board[1][0] == '*' && board[2][1] == '*')
		{
			if (board[0][1] == ' ')
			{
				board[0][1] = '#';
			}
			else
			{
				board[1][1] = '#';
			}
		}
		// 6@1@1
		if (board[0][0] == '#' && board[0][2] == '#' && board[2][0] == '#' && board[0][1] == '*' && board[1][2] == '*')
		{
			if (board[1][0] == ' ')
			{
				board[1][0] = '#';
			}
			else
			{
				board[1][1] = '#';
			}
		}
		// 7@1@1
		if (board[0][0] == '#' && board[0][1] == '#' && board[2][0] == '#' && board[1][1] == '*' && board[0][2] == '*')
		{
			if (board[1][0] == '*')
			{
				board[1][2] = '#';
			}
			else
			{
				board[1][0] = '#';
			}
		}
		// 8@1@1
		if (board[0][0] == '#' && board[0][2] == '#' && board[2][0] == '#' && board[0][1] == '*' && board[2][2] == '*')
		{
			if (board[1][0] == ' ')
			{
				board[1][0] = '#';
			}
			else
			{
				board[1][1] = '#';
			}
		}
	}
	if (CountNum(board, ROW, COL) == 8)
	{
		//7@1@1@1
		if (board[0][0] == '#' && board[0][1] == '#' && board[1][2] == '#' && board[2][0] == '#' && board[0][2] == '*' && board[1][0] == '*' && board[1][1] == '*')
		{
			if (board[2][1] == '*')
			{
				board[2][2] = '#';
			}
			else
			{
				board[2][1] = '#';
			}
		}
	}
}

四、Acknowledgment

謝謝我自己能在大一下期中考前抽出半天來研究這樣一個看似挺無聊的問題

謝謝小伙伴們能夠看完這篇文章

附上GitHub完整代碼

如果想要深入了解AI對弈，可以去看看極大極小演算法（Minimax）

本人目前水平有限，如有錯誤，望指正

2021.4.24 姑蘇陰雨綿綿