当前位置: 首页 > news >正文

基于博弈树的开源五子棋AI教程[1 位棋盘]

0 引子

常见的五子棋棋盘大小为15x15,最直观的表示就是一个二维数据。本文为了易于拓展一开始使用的是QVector<QVector>的数据,但是在分支因子为10的情况下只能搜索到4层左右,后面深度加深,搜索时间呈指数倍数增长。这种实现方式下,六层搜索深度下搜索时间大于1min。
接着使用二维数组(int[][])来表示一个搜索状态,搜索速度略有加快,时间大约在2倍左右(记忆模糊了)。
目前实现方式中使用的位棋盘,这样可以有效的减少寻址时间,取出一行或者一列只需要从内存中取出一个int32(考虑到17x17或者19x19)。有些读者可能想问一个格子有三种状态(黑/白/空),bool又能如何表示呢?答案就是使用两个int32数组表示,一个数组表示是否有子,另一个表示黑子还是白子。

1 15X15棋盘

1 定义

一般而言一组二维数组就可以充分的表示棋盘信息,但是在后续棋盘静态评估的需求中发现,本文需要对棋盘的四个方向上评估出基础棋型。因而从不同角度冗余的描述棋盘信息就是必要的。

//棋子值的定义[保证0 1为黑子或者白子]
#define PLAYER_BLACK 0
#define PLAYER_WHITE 1
#define PLAYER_NONE  2
//四方向
#define MMainDiagonal 0 //主对角线
#define MSubDiagonal  1 //副对角线
#define MHorizontal   2 //水平
#define MVertical     3 //竖直

这里也简单给出棋盘信息完备表示,为了简化搜索过程的的边界处理,对所有棋盘加墙(白棋搜索时,墙就是黑子)。对角线上只保留了可以构成连五的线。

    //定义含有边界所有连线上的棋子,用于更新棋型int searchBoard[boardSize+2];int searchBoardMask[boardSize+2];int searchBoardVertical[boardSize+2];int searchBoardVerticalMask[boardSize+2];int searchBoardMainDiag[2*boardSize - 9];int searchBoardMainDiagMask[2*boardSize - 9];int searchBoardSubDiag[2*boardSize - 9];int searchBoardSubDiagMask[2*boardSize - 9];

2 实现

有了棋盘信息的表示,就需要实现如何更新棋盘信息。这里实现可能略微复杂,没有做代码的精简。在象棋百科中有通过棋盘旋转的方式来获取不同方向的信息,那里是使用通过和一个魔法数位运算来实现的,理论上这里也是可以的。
这里具体实现时需要注意三点:一是边界点的判定,二是位运算如何某数位置0或者置1,,三是位移量的求解。

void GameBoard::setSearchBoardPiece(const MPoint &position, MPlayerType player)
{int row = position.x();int col = position.y();if(!isValidSearchPosition(row,col)) return ;if(player == PLAYER_WHITE){//player == white(1)searchBoard[row] |= (1 << col);searchBoardMask[row] |= (1 << col);searchBoardVertical[col] |= (1 << row);searchBoardVerticalMask[col] |= (1<<row);//主对角线[右下]if(abs(col-row)<=boardSize-5){if(row>col){searchBoardMainDiag[boardSize- 5 - row + col] |=(1 << col);searchBoardMainDiagMask[boardSize- 5 - row + col] |=(1 << col);}else{searchBoardMainDiag[boardSize- 5 + col - row] |= (1 << row);searchBoardMainDiagMask[boardSize- 5 + col - row] |= (1 << row);}}//副对角线[右上]if(row+col>=6 && row+col<= boardSize*2-4){if(col < boardSize -row  + 1){searchBoardSubDiag[row + col - 6] |= (1 << col);searchBoardSubDiagMask[row + col - 6] |= (1 << col);}else{searchBoardSubDiag[row+col-6] |= (1 << (boardSize+1-row));searchBoardSubDiagMask[row+col-6] |= (1 << (boardSize+1-row));}}}else if(player == PLAYER_BLACK){//player == black(0)searchBoard[row] &= ~(1 << col);searchBoardMask[row] |= (1 << col);searchBoardVertical[col] &= ~(1 << row);searchBoardVerticalMask[col] |= (1<<row);//主对角线if(abs(col-row)<=boardSize-5){if(row>col){searchBoardMainDiag[boardSize- 5 - row + col] &= ~(1 << col);searchBoardMainDiagMask[boardSize- 5 - row + col] |=(1 << col);}else{searchBoardMainDiag[boardSize- 5 + col - row] &= ~(1 << row);searchBoardMainDiagMask[boardSize- 5 + col - row] |= (1 << row);}}//副对角线if(row+col>=6){if(col < boardSize -row  + 1){searchBoardSubDiag[row + col - 6] &= ~(1 << col);searchBoardSubDiagMask[row + col - 6] |= (1 << col);}else{searchBoardSubDiag[row+col-6] &= ~(1 << (boardSize+1-row));searchBoardSubDiagMask[row+col-6] |= (1 << (boardSize+1-row));}}}else{//player==none(2)searchBoardMask[row] &= ~(1 << col);searchBoardVerticalMask[col] &= ~(1 << row);searchBoard[row] &= ~(1 << col);searchBoardVertical[col] &= ~(1 << row);//主对角线if(abs(col-row)<=10){if(row>col){searchBoardMainDiagMask[boardSize- 5 - row + col] &= ~(1 << col);searchBoardMainDiag[boardSize- 5 - row + col] &= ~(1 << col);}else{searchBoardMainDiagMask[boardSize- 5 + col - row] &= ~(1 << row);searchBoardMainDiag[boardSize- 5 + col - row] &= ~(1 << row);}}//副对角线if(row+col>=6){if(col < boardSize -row  + 1){searchBoardSubDiagMask[row + col - 6] &= ~(1 << col);searchBoardSubDiag[row + col - 6] &= ~(1 << col);}else{searchBoardSubDiagMask[row+col-6] &= ~(1 << (boardSize+1-row));searchBoardSubDiag[row+col-6] &= ~(1 << (boardSize+1-row));}}}
}

相关文章:

基于博弈树的开源五子棋AI教程[1 位棋盘]

0 引子 常见的五子棋棋盘大小为15x15&#xff0c;最直观的表示就是一个二维数据。本文为了易于拓展一开始使用的是QVector<QVector>的数据&#xff0c;但是在分支因子为10的情况下只能搜索到4层左右&#xff0c;后面深度加深&#xff0c;搜索时间呈指数倍数增长。这种实…...

Java Catching and Handling Exceptions(二)

一、Try with resources语句 try with resources语句是声明一个或多个资源的try语句。资源是程序使用完后必须关闭的对象。try with resources语句确保在语句末尾关闭每个资源。任何实现java.lang.AutoCloseable的对象&#xff08;包括实现java.io.Closeable的所有对象&#x…...

【HarmonyOS开发】ArkTs关系型和非关系型数据库的存储封装

前面使用了首选项的存储方式&#xff0c;因此将其他的两种存储方式&#xff08;键值型数据库和关系型数据库&#xff09;也学习一下&#xff0c;简单记录一下&#xff0c;并进行封装&#xff0c;方便后续使用。 1、效果预览 2、使用条件 2.1 键值型数据库 键值型数据库实现数据…...

Latex编译出来的pdf文件缺少参考文献和交叉引用

参考文件通常需要在首次编译后&#xff0c;再次编译添加 依次执行下面的命令即可&#xff1a; xelatex main.tex main.tex为需要编译的主tex文件 biber mainxelatex main.tex 如果编译过程中遇到错误&#xff0c;请删除所有辅助文件和已打开的pdf文件后重试 辅助文件包括&#…...

sql_lab靶场搭建以及存在的一些问题

sql_lab靶场搭建问题 首先检查小皮版本 把小皮改到5.3.29版本如果没有可以直接点击更多版本进行选择安装 当版本不对时则会暴出这种错误 SETTING UP THE DATABASE SCHEMA AND POPULATING DATA IN TABLES: Fatal error: Uncaught Error: Call to undefined function mysql_co…...

Https接口调用问题

使用场景: 因为项目需要爬点接口数据, 接口是https, 在网上找的笔记整理了一下. 仅供参考 1. 调用Https的Get方法 /*** 只需要url** param url* return*/public static String doGetForHTML(String url) {return doGetForHTML(url, null);}/*** param url 请求地址* para…...

CSS自适应分辨率 amfe-flexible 和 postcss-pxtorem:大屏高宽自适应问题

前言 继上篇《CSS自适应分辨率 amfe-flexible 和 postcss-pxtorem》。 发现一个有趣的问题&#xff0c;文件 rem.js 中按照宽度设置自适应&#xff0c;适用于大多数页面&#xff0c;但当遇到大屏就不那么合适了。 问题 使用宽度&#xff0c;注意代码第2 和 4 行&#xff1a;…...

SQL面试题挑战01:打折日期交叉问题

目录 问题&#xff1a;SQL解答&#xff1a;第一种方式&#xff1a;第二种方式&#xff1a; 问题&#xff1a; 如下为某平台的商品促销数据&#xff0c;字段含义分别为品牌名称、打折开始日期、打折结束日期&#xff0c;现在要计算每个品牌的打折销售天数&#xff08;注意其中的…...

三大主流前端框架介绍及选型

在前端项目中&#xff0c;可以借助某些框架&#xff08;如React、Vue、Angular等&#xff09;来实现组件化开发&#xff0c;使代码更容易复用。此时&#xff0c;一个网页不再是由一个个独立的HTML、CSS和JavaScript文件组成&#xff0c;而是按照组件的思想将网页划分成一个个组…...

云原生消息流系统 Apache Pulsar 在腾讯云的大规模生产实践

导语 由 InfoQ 主办的 Qcon 全球软件开发者大会北京站上周已精彩落幕&#xff0c;腾讯云中间件团队的冉小龙参与了《云原生机构设计与音视频技术应用》专题&#xff0c;带来了以《云原生消息流系统 Apache Pulsar 在腾讯云的大规模生产实践》为主题的精彩演讲&#xff0c;在本…...

【LeetCode刷题】--245.最短单词距离III

245.最短单词距离III class Solution {public int shortestWordDistance(String[] wordsDict, String word1, String word2) {int len wordsDict.length;int ans len;if(word1.equals(word2)){int prev -1;for(int i 0;i<len;i){String word wordsDict[i];if(word.equa…...

数字化时代的智能支持:亚马逊云科技轻量应用服务器技术领先

轻量应用服务器是一种简化运维、门槛低的弹性服务器&#xff0c;它的"轻"主要体现在几个方面&#xff1a;开箱即用、应用优质、上手简洁、投入划算、运维简便以及稳定可靠。相较于普通的云服务器&#xff0c;轻量应用服务器简化了云服务的操作难度、使用和管理流程&a…...

【智慧之窗】AI驱动产品探索

一.初识 ChatGPT ChatGPT 是由 OpenAI 开发的自然语言处理&#xff08;NLP&#xff09;模型&#xff0c;基于 GPT&#xff08;Generative Pre-trained Transformer&#xff09;架构。GPT 系列的模型旨在理解和生成自然语言文本。ChatGPT 专注于支持对话性任务&#xff0c;即与…...

BBS项目--登录

BBS阶段性测试总要求 django登录报错 Error: [WinError 10013] 以一种访问权限不允许的方式做了一个访问套接字的尝试。 原因分析&#xff1a;出现这种情况在Windows中很常见&#xff0c;就是端口被占用 解决措施&#xff1a;这时我们只需改一下端口便可以了 登录前端页面(HTML…...

Python---TCP服务端程序开发

1. 开发 TCP 服务端程序开发步骤回顾 创建服务端端套接字对象绑定端口号设置监听等待接受客户端的连接请求接收数据发送数据关闭套接字 2. socket 类的介绍 导入 socket 模块import socket 创建服务端 socket 对象socket.socket(AddressFamily, Type) 参数说明: AddressF…...

回归预测 | MATLAB实现GWO-DHKELM基于灰狼算法优化深度混合核极限学习机的数据回归预测 (多指标,多图)

回归预测 | MATLAB实现GWO-DHKELM基于灰狼算法优化深度混合核极限学习机的数据回归预测 &#xff08;多指标&#xff0c;多图&#xff09; 目录 回归预测 | MATLAB实现GWO-DHKELM基于灰狼算法优化深度混合核极限学习机的数据回归预测 &#xff08;多指标&#xff0c;多图&#…...

听GPT 讲Rust源代码--src/tools(15)

File: rust/src/tools/rust-analyzer/crates/mbe/src/token_map.rs 在Rust源代码中&#xff0c;rust/src/tools/rust-analyzer/crates/mbe/src/token_map.rs文件的作用是实现了一个能够将输入的文本映射为标记的结构。具体来说&#xff0c;它定义和实现了几个结构体&#xff08…...

python可以做小程序研发嘛,python能做微信小程序吗

大家好&#xff0c;给大家分享一下python可以做微信小程序开发吗&#xff0c;很多人还不知道这一点。下面详细解释一下。现在让我们来看看&#xff01; 大家好&#xff0c;给大家分享一下用python编写一个小程序&#xff0c;很多人还不知道这一点。下面详细解释一下用python代码…...

创建型模式 | 单例模式

一、单例模式 单例模式(Singleton Pattern)&#xff0c;使用最广泛的设计模式之一。其意图是保证一个类仅有一个实例被构造&#xff0c;并提供一个访问它的全局访问接口&#xff0c;该实例被程序的所有模块共享。 1、饿汉式 1.1、基础版本 在程序启动后立刻构造单例&#xff0…...

【无标题】欢迎使用Markdown编辑器

这里写自定义目录标题 欢迎使用Markdown编辑器新的改变功能快捷键合理的创建标题&#xff0c;有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右SmartyPants 创建一个自定义列表如何创建一个…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

React hook之useRef

React useRef 详解 useRef 是 React 提供的一个 Hook&#xff0c;用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途&#xff0c;下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用

1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...

Rapidio门铃消息FIFO溢出机制

关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系&#xff0c;以下是深入解析&#xff1a; 门铃FIFO溢出的本质 在RapidIO系统中&#xff0c;门铃消息FIFO是硬件控制器内部的缓冲区&#xff0c;用于临时存储接收到的门铃消息&#xff08;Doorbell Message&#xff09;。…...

CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)

漏洞概览 漏洞名称&#xff1a;Apache Flink REST API 任意文件读取漏洞CVE编号&#xff1a;CVE-2020-17519CVSS评分&#xff1a;7.5影响版本&#xff1a;Apache Flink 1.11.0、1.11.1、1.11.2修复版本&#xff1a;≥ 1.11.3 或 ≥ 1.12.0漏洞类型&#xff1a;路径遍历&#x…...

【C++特殊工具与技术】优化内存分配(一):C++中的内存分配

目录 一、C 内存的基本概念​ 1.1 内存的物理与逻辑结构​ 1.2 C 程序的内存区域划分​ 二、栈内存分配​ 2.1 栈内存的特点​ 2.2 栈内存分配示例​ 三、堆内存分配​ 3.1 new和delete操作符​ 4.2 内存泄漏与悬空指针问题​ 4.3 new和delete的重载​ 四、智能指针…...

LabVIEW双光子成像系统技术

双光子成像技术的核心特性 双光子成像通过双低能量光子协同激发机制&#xff0c;展现出显著的技术优势&#xff1a; 深层组织穿透能力&#xff1a;适用于活体组织深度成像 高分辨率观测性能&#xff1a;满足微观结构的精细研究需求 低光毒性特点&#xff1a;减少对样本的损伤…...

Qt 事件处理中 return 的深入解析

Qt 事件处理中 return 的深入解析 在 Qt 事件处理中&#xff0c;return 语句的使用是另一个关键概念&#xff0c;它与 event->accept()/event->ignore() 密切相关但作用不同。让我们详细分析一下它们之间的关系和工作原理。 核心区别&#xff1a;不同层级的事件处理 方…...

WEB3全栈开发——面试专业技能点P7前端与链上集成

一、Next.js技术栈 ✅ 概念介绍 Next.js 是一个基于 React 的 服务端渲染&#xff08;SSR&#xff09;与静态网站生成&#xff08;SSG&#xff09; 框架&#xff0c;由 Vercel 开发。它简化了构建生产级 React 应用的过程&#xff0c;并内置了很多特性&#xff1a; ✅ 文件系…...