背景

​ 小时候在FC上玩过象棋游戏，印象最深的就是那个老头，每次走棋贼慢同时棋力也特高。一直想了解下人机对弈的算法，看了几篇文章后，发现基本的套路都是一样的，自己写了一个小时候玩的两口吃一口的小游戏。

---

棋类AI基本步骤(以下都是基于两口吃一口这个小游戏)

• 局面生成：棋子种类、开局位置

  // 5x5 棋盘，黑方和白方初始时都有5颗棋子
  /*
    0 1 2 3 4
   ┌─────────┐
  0│○─○─○─○─○│
  1│├─┼─┼─┼─┤│
  2│├─┼─┼─┼─┤│
  3│├─┼─┼─┼─┤│
  4│●─●─●─●─●│
   └─────────┘
   */
  std::string GenBoard(int row, int col, int colNum, int rowNum, std::map<std::pair<int, int>, int> board)
  {
  	std::string str;
  	auto it = board.find(std::make_pair(row, col));
  
  	if (it != board.end()) {
  		if (it->second == WHITE) {
  			return "○";
  		}
  		if (it->second == BLACK) {
  			return "●";
  		}
  	}
  
  	if (row == 0 && col == 0) {
  		str = "┌";
  	}
  	else if (row == 0 && col == colNum - 1) {
  		str = "┐";
  	}
  	else if (row == rowNum - 1 && col == 0) {
  		str = "└";
  	}
  	else if (row == rowNum - 1 && col == colNum - 1) {
  		str = "┘";
  	}
  	else if (row == 0) {
  		str = "┬";
  	}
  	else if (col == colNum - 1) {
  		str = "┤";
  	}
  	else if (col == 0) {
  		str = "├";
  	}
  	else if (row == rowNum - 1) {
  		str = "┴";
  	}
  	else {
  		str = "┼";
  	}
  	
  	return str;
  }
  // 棋盘绘制
  void DrawBoard()
  {
  	std::string posCol;
  	std::string topBorderLine;
  	std::string bottomBorderLine;
  
  	posCol += "  ";
  	for (int i = 0; i < g_colNum; i++) {
  		posCol += std::to_string(i) + " ";
  	}
  
  	GenBorderLine(topBorderLine, bottomBorderLine, g_colNum);
  	std::cout << posCol << std::endl;
  	std::cout << topBorderLine << std::endl;
  	for (int rowIdx = 0; rowIdx < g_rowNum; rowIdx++) {
  		std::cout << std::to_string(rowIdx) << "│";
  		for (int colIdx = 0; colIdx < g_colNum; colIdx++) {
  			std::cout << GenBoard(rowIdx, colIdx, g_rowNum, g_colNum, g_board);
  			if (colIdx != g_colNum - 1) {
  				std::cout << "─";
  			}
  		}
  		std::cout << "│" << std::endl;
  	}
  	std::cout << bottomBorderLine << std::endl;
  }
  

• 走法生成：走棋规则、吃子规则、胜利规则

  // 上下左右不超出棋盘并且目标位置没有棋子
  void GenMoveWays(int player, std::vector<std::tuple<int, int, int, int>>& ways)
  {
  	int direct[4][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
  
  	for (auto &i : g_board) {
  		if (i.second != player) {
  			continue;
  		}
  		for (int k = 0; k < 4; k++) {
  			int nextRow = i.first.first + direct[k][0];
  			int nextCol = i.first.second + direct[k][1];
  
  			if (CheckPostion(nextRow, nextCol)) {
  				continue;
  			}
  			auto nextIt = g_board.find(std::make_pair(nextRow, nextCol));
  			if (nextIt != g_board.end()) {
  				continue;
  			}
  			ways.push_back(std::make_tuple(i.first.first, i.first.second, nextRow, nextCol));
  		}
  	}
  }
  /* 一行或者一列两个连续己方棋子可以吃对方一个棋子
   _○○●_：OK
   ○○●__：OK
   __○○●：OK
   ○○●_●：这种情况不能吃子
   ○○○●_：这种情况不能吃子
   _○○○●：这种情况不能吃子
   _●○○●：这种情况不能吃子
   ●○○●_：这种情况不能吃子
  */
  int GetPieceNumByDirect(int row, int col, int direct[2])
  {
  	int pieceNum = 0;
  
  	if (direct[0] != 0 && direct[1] != 0) {
  		std::cout << "错误的方向" << std::endl;
  		assert(0);
  		return 0;
  	}
  
  	if (direct[0] != 0) {
  		for (int i = 0; i < g_rowNum; i++) {
  			auto it = g_board.find(std::make_pair(i, col));
  			if (it != g_board.end()) {
  				pieceNum++;
  			}
  		}
  		return pieceNum;
  	}
  
  	for (int i = 0; i < g_colNum; i++) {
  		auto it = g_board.find(std::make_pair(row, i));
  		if (it != g_board.end()) {
  			pieceNum++;
  		}
  	}
  	return pieceNum;
  }
  
  // 当前走棋方棋子数量小于2，则为失败（连续两个棋子才能吃对方一个棋子）
  bool IsCurrentPlayLose()
  {	
  	return GetPieceNum(g_currentPlayer) < 2;
  }
  

• 局面评估：这部分其实是大多棋类AI的关键，别看我写的局面评估只有一个语句

  // 己方棋子越多，对自己越有利
  int EvaluatePosition()
  {
  	return GetPieceNum(WHITE) - GetPieceNum(BLACK);
  }
  

• 局面搜索：搜索算法要和评估函数结合，通过好的剪枝算法会大大提高AI的智慧，我这里就是一个简单极大极小值深度优先搜索

  int GenOneStep(int fromRow, int fromCol, int toRow, int toCol, std::vector<std::pair<int, int>> &eats)
  {
  	std::set<std::tuple<int, int, int, int>> ways;
  
  	if (!IsVaildPiece(fromRow, fromCol, toRow, toCol, g_currentPlayer)) {
  		return -1;
  	}
  
  	// 走一步棋
  	DeletePiece(fromRow, fromCol, g_currentPlayer);
  	AddPiece(toRow, toCol, g_currentPlayer);
  	
  	// 吃子
  	EatPiece(toRow, toCol, g_currentPlayer, eats);
  
  	// 交换走棋方
  	ChangePlayer();
  
  	//DrawBoard();
  	return 0;
  }
  
  void UndoOneStep(int fromRow, int fromCol, int toRow, int toCol, std::vector<std::pair<int, int>>& eats)
  {
  	// 还原被吃掉的对方棋子
  	for (auto& i : eats) {
  		AddPiece(i.first, i.second, g_currentPlayer); // 当前走棋方为对方
  	}
  	eats.clear();
  
  	// 交换走棋方
  	ChangePlayer();
  	
  	// 撤销上一步棋
  	DeletePiece(toRow, toCol, g_currentPlayer);
  	AddPiece(fromRow, fromCol, g_currentPlayer);
  }
  
  int Search(int depth, int& fromRow, int& fromCol, int &toRow, int &toCol)
  {
  	int bestValue;
  	int value;
  	if (depth == 0) {
  		return EvaluatePosition();
  	}
  
  	if (g_currentPlayer == BLACK) {
  		bestValue = INFINITY_VALUE;  // bestValue越小对黑方越有利
  	}
  	else {
  		bestValue = -INFINITY_VALUE; // bestValue越大对白方越有利
  	}
  
  	std::vector<std::tuple<int, int, int, int>> ways;
  	std::vector<std::pair<int, int>> eats;
  
  	GenMoveWays(g_currentPlayer, ways);
  	for (auto& i : ways) {
  		if (GenOneStep(std::get<0>(i), std::get<1>(i), std::get<2>(i), std::get<3>(i), eats)) {
  			continue;
  		}
  		value = Search(depth - 1, fromRow, fromCol, toRow, toCol);
  		UndoOneStep(std::get<0>(i), std::get<1>(i), std::get<2>(i), std::get<3>(i), eats);
  		if (g_currentPlayer == BLACK) {
  			if (value < bestValue) {
  				bestValue = value;
  				if (depth == MAX_SEARCH_DEPTH) {
  					fromRow = std::get<0>(i);
  					fromCol = std::get<1>(i);
  					toRow = std::get<2>(i);
  					toCol = std::get<3>(i);
  				}
  			}
  		}
  		else {
  			if (value > bestValue) {
  				bestValue = value;
  				if (depth == MAX_SEARCH_DEPTH) {
  					fromRow = std::get<0>(i);
  					fromCol = std::get<1>(i);
  					toRow = std::get<2>(i);
  					toCol = std::get<3>(i);
  				}
  			}
  		}
  	}
  
  	// 当前方已经无棋可走了
  	if (g_currentPlayer == BLACK && bestValue == INFINITY_VALUE) {
  		// 黑方value越小越好，即搜索深度越深到达无路可走越好
  		return INFINITY_VALUE - (MAX_SEARCH_DEPTH - depth);
  	}
  
  	if (g_currentPlayer == WHITE && bestValue == -INFINITY_VALUE) {
  		return (MAX_SEARCH_DEPTH - depth) - INFINITY_VALUE;
  	}
  
  	return bestValue;
  }
  
  void ComputerOneStep()
  {
  	int fromRow;
  	int fromCol;
  	int toRow; 
  	int toCol;
  
  	std::vector<std::pair<int, int>> eats;
  
  	Search(MAX_SEARCH_DEPTH, fromRow, fromCol, toRow, toCol);
  
  	GenOneStep(fromRow, fromCol, toRow, toCol, eats);
  }
  

---

项目链接

https://github.com/xy007man/2KouChiYiKou

---

参考链接

• https://www.zhihu.com/question/34816738

• https://www.xqbase.com/computer.htm

• https://www.zhihu.com/question/29472711/answer/45436565