丘卡的秘密小屋
国际象棋 Demo 实现
编辑
2024-10-24
个人项目
00
请注意，本文编写于 121 天前，最后修改于 100 天前，其中某些信息可能已经过时。

目录

象棋算法
象棋规则与着法生成
实现下棋 AI
极小化极大算法
Alpha-Beta 剪枝
技术栈
环境配置
Webpack 配置
TypeScript 配置
迁移工作
chessboardjs 迁移到 chessboard2
多线程迁移
程序编写
游戏循环
chessboard2 类与 chess 的对接
防抖
总结

之前为 Polyethylene Server 做了一个国际象棋小游戏，现将其迁移出来作为自己的一个小项目。

实际上已经有一个很好的参考仓库了 lhartikk/simple-chess-ai: A simple chess AI (github.com)。我在这个的基础上进行了一些修改，打了一些补丁。

花的时间有点长了，所以有些功能并没有迁移出来。

相关信息

仓库地址：https://github.com/ZerolAcqua/simple-chess

体验地址：https://vanblog.zerolacqua.top/c/chess/

象棋算法

象棋规则与着法生成

直接使用现有的 chess.js 库，完成符合规则的着法生成和棋局结束的判断。

关于如何自己完成这个库的功能，可以参考这两个专栏：

  • 国际象棋程序设计

    • 这个专栏讲解了 AI 象棋程序编写的重要知识，包括棋盘的表示方法、着法的产生，同时也包含了搜索技巧与评价局面的内容
      • 位棋盘、置换表、历史表和预处理数据库
      • 朝前裁剪、产生全部着法、一次只产生一步棋着法排序
      • 极大极小算法、Alpha-Beta 剪枝、杀手启发、迭代加深、空着启发、静态搜索、期望搜索、MTD(f) 搜索、单步延伸
      • 子力平衡、机动性和对棋盘的控制、局势发展、兵形、王的安全和取向、确定权重

  • FireMonkey3D之中国象棋程序

    • 这个虽然是中国象棋的程序，但是有很多值得参考的地方。
    • 而且他在开局库、PVS主要变例搜索方面的讲解也比较多

实现下棋 AI

预计目标：

  • 极小极大算法
  • Alpha-beta 剪枝

可能尝试的内容（咕咕咕）：

  • 置换表
  • 主要变例搜索
  • MTD(f) 搜索

极小化极大算法

参考资料

Alpha-Beta 剪枝

参考资料

技术栈

原参考仓库是单个 html 文件加上 js 和 css 组成的，我在此基础上硬凑了使用了

  • 使用 Webpack 进行项目打包
  • 使用 Bootstrap 编写界面
  • 使用 npm 管理包
    • 移除了 jquery 依赖
    • 换用 chessboard2 代替 chessboard.js 完成棋盘渲染和交互
  • 使用 TypeScript、Pug 和 SASS 生成 js、html 和 css

环境配置

Webpack 配置

生产环境与环境环境采用不同的配置，将共同的配置提取在 webpack.common.js 中。开发环境在 webpack.dev.js 中，而生产环境在 webpack.prod.js 中。使用 webpack-merge 将 webpack.common.js 合并入相关的环境中。

在 webpack.common.js 中设置入口文件和输出路径，在每次构建时清空，并配置解析的相关信息。

js
module.exports = {
  entry: {
    index: {
      import: './src/index.ts',
    },
  },
  output: {
    filename: 'static/js/[name].[contenthash].js',
    path: path.resolve(__dirname, 'dist'),
    clean: true,
  },
  resolve: {
    modules: [path.resolve('node_modules')],
    extensions: ['.tsx', '.ts', '.js'],
  },
  module: {
    rules: [
      {
        test: /\.tsx?$/,
        use: 'ts-loader',
        exclude: /node_modules/,
      },
      {
        test: /\.pug$/,
        loader: 'pug-loader',
        exclude: /(node_modules|bower_components)/,
       },
    ],
  },
}

在 webpack.dev.js 中，设置调试时 webpack serve 的端口，并使用热更新。在开发环境中使用 style-loader 直接加载 css。

js
module.exports = merge(common, {
  mode: 'development',
  devtool: 'inline-source-map',
  devServer: {
    static: path.resolve(__dirname, 'dist'),
    port: 8080,
    hot: true
  },
  module: {
    rules: [
      {
        test: /\.(css|scss)$/i,
        use: [
          'style-loader',
          'css-loader',
          {
            // Loader for webpack to process CSS with PostCSS
            loader: 'postcss-loader',
            options: {
              postcssOptions: {
                plugins: [
                  autoprefixer
                ]
              }
            }
          },
          {
            // Loads a SASS/SCSS file and compiles it to CSS
            loader: 'sass-loader'
          },
        ],
      },
    ],
  },  
  plugins: [
    new HtmlWebpackPlugin({
      // 指定Pug模板
      template: './src/index.pug',
      filename: 'index.html',
      minify: false, // 禁用压缩
    }),
  ],
});

在 webpack.prod.js 中，则使用 mini-css-extract-plugin 提取 css 并进行压缩。输出文件命名直接使用 [contenthash] 不再包含 [name]。html-webpack-plugin 启用压缩，配置 splitChunks 进行重复代码提取和分割。terser-webpack-plugin 负责移除调试相关的信息，删除注释。

js
module.exports = merge(common, {
  mode: 'production',
  output: {
    filename: 'static/js/[contenthash].js',
    path: path.resolve(__dirname, 'dist'),
    clean: true,
  },
  module: {
    rules: [
      {
        test: /\.(css|scss)$/i,
        use: [
          MiniCssExtractPlugin.loader,
          'css-loader',
          {
            // Loader for webpack to process CSS with PostCSS
            loader: 'postcss-loader',
            options: {
              postcssOptions: {
                plugins: [
                  autoprefixer
                ]
              }
            }
          },
          {
            // Loads a SASS/SCSS file and compiles it to CSS
            loader: 'sass-loader'
          },
        ],
      },
    ],
  },
  plugins: [
    new MiniCssExtractPlugin({
      filename: 'static/css/[contenthash].css',
    }),
    new CssMinimizerPlugin(),
    // 创建实例 (第二步)
    new HtmlWebpackPlugin({
      // 指定Pug模板
      template: './src/index.pug',
      filename: 'index.html',
      minify: true, // 启用压缩
    }),
  ],
  optimization: {
    runtimeChunk: 'single',
    splitChunks: {
      chunks: 'all',
    },
    minimizer: [
      new TerserPlugin({
        parallel: true, // 使用多进程并发运行以提高构建速度 Boolean|Number 默认值： true
        terserOptions: {
          compress: {
            drop_console: true, // 移除所有console相关代码；
            drop_debugger: true, // 移除自动断点功能；
            pure_funcs: ["console.log", "console.error"], // 配置移除指定的指令，如console.log,alert等
          },
          format: {
            comments: false, // 删除注释
          },
        },
        extractComments: false, // 是否将注释剥离到单独的文件中
      })
    ]
  },
});

将配置文件按生产环境和开发环境分离，可参考 https://juejin.cn/post/7212893989033443387

TypeScript 配置

tsconfig.json 文件如下

json
{
	"compilerOptions": {
		"outDir": "./dist/",
		"noImplicitAny": true,
		"sourceMap": true,
		"module": "ES2020",
		"target": "ES2020",
		"jsx": "react",
		"allowJs": true,
		"moduleResolution": "node",
		"typeRoots": [
			"./node_modules/@types",
			"./src/types"
		],
	}
}

对于使用的 js代码也要转换成 ts 风格，注意添加库的类型声明。

迁移工作

chessboardjs 迁移到 chessboard2

参考仓库 lhartikk/simple-chess-ai: A simple chess AI (github.com) 中，使用的是 chessboardjs 棋盘库。

chessboardjs 它内部依赖 jquery，在我的工作流中需要暴力地通过

js
 window['jQuery'] = $; 
 window.ChessBoard('board', cfg);

来引入。

chessboard2 没有其他依赖，但是源码只有压缩和混淆过的，可读性很差，由于库还在开发中，因此有些函数还是无效的（名称改动，文档未修改之类的）。比如：

  • dropOffBoard 文档与示例的函数名不一致
    • onMouseoutSquare 重命名为 onMouseleaveSquare
    • onMouseoverSquare 重命名为 onMouseenterSquare
  • onChange 参数传入方式不统一

而且没有已经写好的 @types 类型可以使用，所以我参考 @types/chessboardjs 自己本地抄抄改改整了个堪用的。

ts
declare module '@chrisoakman/chessboard2/dist/chessboard2.min.mjs' {
	export enum Square {
		//...
		offboard = "off-board",	// by Acqua
	}

	export enum Piece {
		bK = "bK",
                //...
		wP = "wP"
	}

	export type BoardPositionType = {
		[P in Square]?: Piece;
	};

	export type PositionType = "start" | string | BoardPositionType;
	export type PositionFenType = "fen";
	export type SpeedType = "slow" | "fast";
	export type ErrorType = "console" | "alert";
	export type ErrorCallback = (errCode: number, errStr: string, errData?: object) => void;
	export type OrientationFlipType = "flip";
	export type OrientationType = "white" | "black";
	export type DropOffBoardType = "snapback" | "trash";
	// export type Callback = (...args: any[]) => any;

	// 如果 T 是数组，展开成多个参数，否则当对象作为一个参数处理
	export type Callback<T = any> = (...args: T extends any[] ? T : [T]) => string | boolean | void;

	type PieceMoveData = {
		source?: Square,
		target?: Square,
		piece?: Piece
	};
	type BoardData = {
		position?: BoardPositionType,
		orientation?: OrientationType,
	}
	type ChangeData = [
		oldPos?: BoardPositionType,
		newPos?: BoardPositionType
	];
	type MouseMoveData = {
		piece?: Piece | null
		square?: Square,
		toSquare?: Square,
		fromSquare?: Square
	}
	type ChooseData = {
		piece?: Piece,
		square?: Square
	}
	type coodinate = {
		x?: number,
		y?: number
	}

	export type OnDropCallback = Callback<BoardData & PieceMoveData & coodinate>;
	export type OnChangeCallback = Callback<ChangeData>;
	export type OnDragStartCallback = Callback<BoardData & ChooseData>;
	export type OnMousedownSquareCallback = Callback<BoardData & ChooseData>;
	export type OnMouseupSquareCallback = Callback<BoardData & ChooseData>;
	export type OnMouseenterSquareCallback = Callback<BoardData & MouseMoveData>;
	export type OnMouseleaveSquareCallback = Callback<BoardData & MouseMoveData>;

	export interface BoardConfig {

		draggable?: boolean | undefined;
		onDrop?: OnDropCallback | undefined;
		onChange?: OnChangeCallback | undefined;
		onDragStart?: OnDragStartCallback | undefined;

		onMouseleaveSquare?: OnMouseleaveSquareCallback | undefined;
		onMouseenterSquare?: OnMouseenterSquareCallback | undefined;
		onMousedownSquare?: OnMousedownSquareCallback | undefined;
		onMouseupSquare?: OnMouseupSquareCallback | undefined;

		orientation?: OrientationType | undefined;

		position?: PositionType;

		// === fail to work in Doc === 
		// onDragMove?: Callback | undefined;
		// onMoveEnd?: Callback | undefined;
		// onSnapbackEnd?: Callback | undefined;
		// pieceTheme?: string | ((piece: Piece) => string);
		// showNotation?: boolean | undefined;
		// sparePieces?: boolean | undefined;

		// === not sure ===
		// onSnapEnd?: Callback | undefined;
		// showErrors?: false | ErrorType | ErrorCallback;
		// moveSpeed?: number | SpeedType | undefined;
		// snapSpeed?: number | SpeedType | undefined;
		// trashSpeed?: number | SpeedType | undefined;
		// appearSpeed?: number | SpeedType | undefined;
		// snapbackSpeed?: number | SpeedType | undefined;
		// dropOffBoard?: DropOffBoardType | undefined;
	}

	// ...
}

多线程迁移

在迁移前的程序中，我们使用了 nodejs 的 worker_threads 进行多线程操作。然而，我们的迁移出的子程序不是在 nodejs 环境下运行的，因此需要采用其它的多线程实现。（nodejs 的大概可以理解为在服务端运行的多线程？我们需要的是运行在客户端的多线程）

Web Worker 为 Web 内容在后台线程中运行脚本提供了一种简单的方法。线程可以执行任务而不干扰用户界面。

主线程的变化，主要是函数名和函数参数需要改动。

diff
-import { Worker } from 'worker_threads'
-let worker = new Worker(path);
+let worker = new Worker(new URL('./chessBotWorker.ts', import.meta.url));

-worker.on('message', (data: { id: number, move: Move }) => {
+worker.onmessage = (event: WorkerMessageEvent) => {
+    let data = event.data;
    botQueueLength--;
    if (data.id === chessID) {
+       console.log('[worker onmessage]', data.move);
        botNextMove = data.move;
-	play();
+       step();
    }
};

为了找到工作线程所需的代码，还需要对路径名进行调整。ES2020 才能使用 import.meta.url

工作线程的变化，主要是函数名和函数参数需要改动

diff
-parentPort?.on('message', (data: { id: number, fen?: string, pgn?: string }) => {
+self.onmessage = (event: WorkerMessageEvent) => {
+
+	let data = event.data;
+
 	// reset chessID
 	if (data.pgn === undefined && data.fen === undefined) {
 		chessID = data.id;
                		return;
	}
	if (chessID === data.id) {
		// no validation
		if (data.fen !== undefined) {
			let chess = new Chess(data.fen);
			let move = getBestMove(chess, 3);
			self.postMessage({ id: chessID, move: move });
		} else if (data.pgn !== undefined) {
			let chess = new Chess();
			chess.loadPgn(data.pgn);
			// Threefold repetition is meaningful
			// only if chess is initialized with PGN
			let move = getBestMove(chess, 3, { testTFR: true });
			self.postMessage({ id: chessID, move: move });
		}
	}
};

程序编写

国际象棋的界面和核心库都是现成的，机器人算法则已经在前面的部分讨论过了。这里主要是介绍游戏的执行流程和其他细节

游戏循环

在我的直觉上，我觉得我需要一个状态机来管理象棋游戏的循环，但是最后我还是采用了无脑的 switch 结构（其实与其说用状态机，不如说用状态模式更贴切）。

考虑到 player 和 bot 都各自需要一个状态管理部分。游戏的不同阶段，主要是移动和升变，还有机器人走子时三个阶段。player 和 bot 在对应阶段的行为是不同的，暂时没想好怎么合并在一起（也许策略模式+状态模式可以）。

相关信息

也许之后会补个状态转移的图

游戏循环并不是一直调用一个主循环，而是被动地调用一个 step 函数，step 函数每次执行当前状态下对应的操作，如果需要继续执行后面的步骤，则在操作中会再调用 step 函数（如双方走子后需要切换回合，此时还有其他操作需要完成，因此调用 step 函数）。同样，玩家的交互操作（移动完棋子）和机器人计算结束需要走子时，也会调用 step 函数。

其中，玩家的核心函数如下：

ts
 switch (gameState) {
        case GameState.init:
        case GameState.startTurn:
        case GameState.move: {
            gameState = GameState.move;
            console.log('[playerPlay]', playerNextMove);
            // player move
            if (playerNextMove) {
                let moves = chess.moves({ square: playerNextMove.from, verbose: true });

                let moveIndex = moves.map(move => move.to).indexOf(playerNextMove.to);
                if (moveIndex === -1) {
                    console.error('[playerPlay move]', 'Invalid move:', playerNextMove);
                    return false;
                } else {
                    let moveFlag = moves[moveIndex].flags;
                    // no promotion move
                    if (!moveFlag.includes('p')) {
                        chess.move(playerNextMove);
                        // MUST clear playerNextMove before switchTurn()
                        playerNextMove = undefined;
                        switchTurn();
                    }
                    else {
                        // promotion move
                        gameState = GameState.promote;
                        // show promotion dialog
                        promoteChoose(playerNextMove.to);
                    }
                }
            }
            break;
        }
        case GameState.promote: {
            if (promoteMove?.promotion === undefined) return;
            chess.move(promoteMove);
            // MUST clear promoteMove before switchTurn()
            promoteMove = undefined;
            removePromoteChoose();
            switchTurn();
            break;
        }
        case GameState.gameover: {
            break;
        }
        case GameState.botThinking: {
            break;
        }
        default: {
            throw new Error('Invalid game state');
        }
    }
}

由于玩家在升变的过程中，棋盘处于一个中间态（pawn 到了底线且未升变）。这时的 move 着法信息是不能直接给 chess 类使用的，需要由玩家选择升变类型，补全 move 信息，然后能同步给 chess 类，结束移动。

在 GameState.move 时，如果计算出玩家走了一步升变的着法，并且升变是可行的，那么就会委托给 promoteChoose() 函数，让玩家选择升变类型。同时，将游戏阶段切换到 GameState.promote 拦截一切的 step() 调用（不完成升变离开 GameState.promote 状态，重复调用 step() 函数也不会有任何响应）。升变完成后，会回到正常的游戏流程。

chessboard2 类与 chess 的对接

核心函数是 onDragStart 和 onDrop 回调函数。

onDragStart 函数根据当前状态决定是否允许玩家拖动棋子。如机器人在计算思考的时候，玩家不应该拖动。同时，玩家也不应该拖动不属于自己的棋子。

onDrop 函数则为 step 函数提供玩家走子的信息，并在走子不合理的情况下将棋子自动 snapback 回之前的状态。

防抖

机器人计算是需要一定时间的，当搜索深度为 3 时，有时就已经会需要几秒的时间了。如果短时间内重新开始的次数过多，就会导致机器人 worker 里无效的着法计算过多，从而让游戏迟迟无法开始。具体来说，每次重新开始都会更新棋局 id，上一局计算的着法传到主线程中会被丢弃，然而最需要计算的本局的着法在队尾，这些计算时间被白白浪费了。

  • 限制重新开始的频率
  • 用一个变量计算机器人队列里已有的计算请求
  • 优化 worker 线程，使其能跳过无效的计算请求（我写了一点点，但嫌麻烦不整了）

总结

这个简单的项目中，我尝试了 Webpack 打包流程，将 js 项目改成了 ts 项目，简单学习了 pug 和 SASS 的语法。也试着用 Bootstrip 将界面美化（虽然内容十分贫瘠就是了）。

一开始其实计划了不少东西的（有些甚至是以前就写过只需要迁移的），但因为战线拖得太长了，就只好暂时告一段落了，或许以后还会有机会吧。

  • Cli
  • Webpack 打包、配置分离
  • 象棋算法
  • 极小极大算法
  • Alpha-beta 剪枝
  • 置换表
  • 主要变例搜索
  • MTD(f) 搜索
  • 象棋功能
  • 支持自主选择对战双方是玩家或是机器人
  • 支持弱升变
  • 界面功能
  • 简单的界面
  • 简单的升变选择
  • 导航栏菜单
  • 历史记录栏，点击某一步可查看历史盘面
  • 使用网格或者响应式布局
  • 更好看的设置界面
  • 更好的升变选择界面（类似 chess.com 那样的在 pawn 的位置弹出一个窗口）
  • 盘面提示
  • 棋子可行走法提示
  • 对手走子提示

本文作者:Zerol Acqua

本文链接:

版权声明:本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！