井字棋

英文名：Tic-Tac-Toe
GitHub 另有视频，详见各视频平台。

规则

3 $\times$ 3 的棋盘，圈为先手，叉后手。有3个棋子连成线的一方为胜者。

设计与实现

棋盘是个3X3的二维数组，圈为 1 ，叉为 -1 ，空为 0。

游戏以竖屏形式呈现，采用经典的16:9，竖屏则将横纵比改为9:16 设计视口尺寸大小为 $486\times 864$ 。拉伸模式设置为 canvas_items

每次落子，都通过has_winner来判断有没有赢家。对于谁是赢家，则是在有赢家的情况下最后一次落子的那位。

has_winner是通过判断有没有连成3子，来返回boolean。对于平局，则是在没有赢家的情况下无法再获取空格子来判定。

其实对于井字棋，只需要数棋盘上的棋子数行了。在有赢家的情况下，当棋子数为奇数则先手的那位获胜，当棋子树维偶数时，则后手放胜利。

目录结构

$ tree
.
├── icon.svg
├── icon.svg.import
├── project.godot
├── scene
│   ├── board
│   │   ├── board.gd
│   │   ├── board.tscn
│   │   └── board_view.gd 
│   ├── main.gd
│   ├── main.tscn
│   ├── npc.gd
│   ├── piece
│   │   ├── o.tscn
│   │   ├── o_view.gd
│   │   └── x.tscn
│   ├── player.gd
│   └── ui.gd
└── script
    └── game_rule.gd

棋盘与棋子O的外观是通过覆盖 CanvaseItem._draw() 实现的。 棋子X则是两条 Line2D 交叉。 NPC 继承自 Player 实现自动落子。 main 负责游戏中大部分逻辑。

我这里为了省事，将交互事件处理直接放在了main中。

AI

AI 使用 MiniMax 算法

从minimax到alpha-beta剪枝算法(上)：minimax算法原理介绍_哔哩哔哩_bilibili

算法核心

## board_array: 二维数组型 Array[Array[int]]，为棋盘对象的副本
func alpha_beta(board_array, maximizingPlayer: bool, alpha = -INF, beta = INF) -> AlphaBetaResult:
	
	var empty_cells = GameRule.get_empty_cells(board_array)
	
	# 判断游戏是否结束
	if GameRule.has_winner(board_array):
		var winner = GameRule.get_winner(board_array)
		var score
		if winner == _type : 
			score = 1
		else: 
			score = -1
		return AlphaBetaResult.new(score)
	elif empty_cells.is_empty():
		return AlphaBetaResult.new()
		
	var best_pos : AlphaBetaResult = AlphaBetaResult.new()
	if maximizingPlayer:
		best_pos.score = -INF
		for i in empty_cells:
			board_array[i.x][i.y] = _type
			var result = alpha_beta(board_array, false, alpha, beta)
			board_array[i.x][i.y] = GameRule.PieceType.EMPTY
			result.pos.x = i.x
			result.pos.y = i.y 
			if result.score > best_pos.score:
				best_pos = result
			
			alpha = maxf(alpha, best_pos.score)
			if beta <= alpha :
				break
	else :
		best_pos.score = INF
		for i in empty_cells:
			board_array[i.x][i.y] = _type * -1
			var result = alpha_beta(board_array, true, alpha, beta)
			board_array[i.x][i.y] = GameRule.PieceType.EMPTY
			result.pos.x = i.x
			result.pos.y = i.y 
			if result.score < best_pos.score:
				best_pos = result
			
			beta = minf(beta, best_pos.score)
			if beta <= alpha :
				break
	
	return best_pos

AlphaBetaResult

class AlphaBetaResult :
	var score: float
	var pos: Vector2i
	
	func _init(_score: float = 0.0, _pos: Vector2i = Vector2i(-1, -1)):
		self.score = _score
		self.pos = _pos
		
	func _to_string() -> String:
		return "score: %s, pos: %s" % [score, pos]