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

秒懂算法│博弈论

图片

         博弈论是二人或多人在平等的对局中各自利用对方的策略变换自己的对抗策略,达到取胜目标的理论。博弈论是研究互动决策的理论。博弈可以分析自己与对手的利弊关系,从而确立自己在博弈中的优势,因此有不少博弈理论,可以帮助对弈者分析局势,从而采取相应策略,最终达到取胜的目的。

 

01、最小最大问题

最小最大问题( minimax ):用于确定计算机玩家在诸如井字游戏、跳棋、奥赛罗和国际象棋中的哪一步。这类游戏被称为完美信息游戏,因为它可以看到所有可能的动作。拼字游戏并不是一个完美信息的游戏,因为你看不到对手的手,所以无法预测对手的动作。

可以把这个算法想象成人类的思维过程:如果我做这个动作,那么我的对手只能做两个动作,每个动作都会让我赢。所以这是正确的选择。

用博弈树数据结构表示井字游戏如图 1 所示。

图片

■ 图1   用博弈树数据结构表示井字游戏

如果你认为所谓最小最大就是穷举过程中找到的最差走法和最佳走法那就错了,既然是对立的概念,当然是两个对象,这里的最小最大是当前轮到 AI 走了, AI 进行穷举并选择一条对于 AI 来说最佳而对于人来说最差的走法,但是再考虑一下,机器也是有限的,对于象棋这样棋盘较大的游戏,穷举完博弈树在当前科技下不可能,因此我们的最小最大算法需要一个深度,即向前走几步,计算机就能在这个指定的比较小的整数下完成对博弈树的穷举。

当遍历若干树枝后不可能就结束了,如果在游戏没有结束的情况下我们还需要一个评价启发函数,这个函数用于判断当前策略的价值,如果使用某走法能赢,就返回一个大的正数;如果这种走法会输,就返回一个大的负值;如果走法会产生和局,就返回一个 0 左右的数;如果由于当前博弈树深度没办法判断局面,那么评价函数就会返回一个启发值。

参考程序:

#include<cstdio>
int MaxMin(int depth,int player mode)
{
int best = INFINITY(player mode);
//player mode 是参照物,如果当前落子是人,则返回一个很小的值,反之返回一个很大的值
if (depth <= 0) //当前以局面为博弈树的根
return Evaluate() ; //估值函数
}    
GenerateLegalMoves () ;//生成当前所有走法
while (MovesLeft () ) //遍历每一个走法
{
MakeNextMove () ;//实施走法
val = -MaxMin(depth - 1);//换位思考
UnmakeMove() ;//撤销走法
if (val > best)
best = val;
return best;
}    

 02、巴什博弈

A和B一块报数,每人每次最少报1个,最多报4个,看谁先报到30。这应该是最古老的关于巴什博弈(Bash game)的游戏了。

其实如果知道原理,这个游戏一点运气成分都没有,只和先手、后手有关,比如第一次报数,A报k个数,那么B报5-k个数,那么B报数之后问题就变为,A和B一起报数,看谁先报到25了,进而变为20,15,10,5,当到5的时候,不管A怎么报数,最后一个数肯定是B报的,可以看出,作为后手的B在个游戏中是不会输的。

那么如果要报n个数,每次最少报1个,最多报m个,我们可以找到这么一个整数k和r,使n=k*(m+1)+r,代入上面的例子可以知道,如果r=0,那么先手必败;否则先手必胜。

巴什博弈: 有n个物品,两个人轮流从中取物,规定每次最少取1个,最多取m个,最后取光者为胜。

参考程序:

#include <iostream>
using namespace std;
int main()
int n,m;
while(cin>>n>>m)
cout<<"后手必胜“< <endl;if(n%(m+1)==0)else cout<<"先手必胜"< <endl;
return 0;

例题如下。

题目大意: 小唐和小红轮流写数字,小唐先写,每次写的数x满足1≤x≤k,小红每次写的数y满足1≤y-x≤k,谁先写到不小于n的数算输。

结论: r=(n-1)%(k+1),r=0时小红胜,否则小唐胜。

详解:

巴什博弈: 同余理论。

从n个物品中两人轮流取,每次取1~m个,最后取完者为胜。

比如10个物品,每次只能取1~5个,则先手方必赢。

(1) 面对[1…m]个局面,必胜。

(2) 面对m+1个局面,必输。

(3) 如果可以使对手面临必输局面,那么是必赢局面。

(4) 如果不能使对手面临必输局面,那么是必输局面。

基础: 1, 2,…, m是必赢局面,m+1是必输局面。

递推: m+2,m+3,…,2m+1是必赢局面,2m+2是必输局面。

k(m+1)是必输局面,应该允许k=0,因为0显然也是必输局面。

在必输局和必赢局中,赢的一方的策略是: 拿掉部分物品,使对方面临k(m+1)的局面。

例如,上例中10个物品,只能拿1~5个,先手方拿4个即可,对手无论拿多少个,你下次总能拿完。

从另一个角度思考这个问题,如果物品数量随机,那么先手方胜利的概率是m/(m+1),后手方胜利的概率是1/(m+1)。

03、斐波那契博弈

两人轮流从一堆物品中取物品,先手最少取一个,至多无上限,但不能把物品取完,之后每次取的物品数不能超过上次取的物品数的二倍且至少为一件,取走最后一件物品的人获胜。

结论:先手胜当且仅当 n 不是斐波那契数(n 为物品总数)。

# include <iostream>
# include <string.h>
# include <stdio.h>
using namespace std;
const int N = 55;
int f[N];
void Init()
{
f[O] = f[1] = 1;
for(int i=2;i<N;i++)
f[i] = f[i-1] + f[i-2];
}
int main()
{
Init();
int n;
while(cin>>n)
if(n == 0) break;
bool flag = 0;
for(int i=0;i<N;i++)
{
if(f[i] == n)
{
flag = 1;
break;
}
if(flag) puts("Second win") ;
else
puts("First win");
R
}
return 0;
}

相关文章:

秒懂算法│博弈论

博弈论是二人或多人在平等的对局中各自利用对方的策略变换自己的对抗策略,达到取胜目标的理论。博弈论是研究互动决策的理论。博弈可以分析自己与对手的利弊关系,从而确立自己在博弈中的优势,因此有不少博弈理论,可以帮助对弈者分析局势,从而采取相应策略,最终达到取胜的目的。…...

Springboot整合RabbitMQ消息中间件

spring-boot-rabbitmq–消息中间件整合 前言&#xff1a;RabbitMQ的各种交换机说明 1、直连交换机 生产者发布消息时必须带着routing-key&#xff0c;队列绑定到交换机时必须指定binding-key ,且routing-key和binding-key必须完全相同&#xff0c;如此才能将消息路由到队列中…...

基于springboot+vue的食材商城(前后端分离)

博主主页&#xff1a;猫头鹰源码 博主简介&#xff1a;Java领域优质创作者、CSDN博客专家、公司架构师、全网粉丝5万、专注Java技术领域和毕业设计项目实战 主要内容&#xff1a;毕业设计(Javaweb项目|小程序等)、简历模板、学习资料、面试题库、技术咨询 文末联系获取 项目介绍…...

Maven解析

目录 Maven的概念 Pom 项目坐标 仓库 Maven环境搭建 安装jdk 配置maven 配置本地仓库地址 配置阿里云 maven 镜像仓库&#xff0c;下载速度更快 在idea中配置maven ​编辑 pom中名词解释 Maven命令 Maven的概念 Maven 是 Apache 软件基金会的一个开源项目,是一个…...

如何使用数学将 NumPy 函数的性能提高 50%

一、说明 2D 傅里叶变换是本世纪最重要的计算机科学算法之一。它已在我们的日常生活中得到应用&#xff0c;从Instagram过滤器到MP3文件的处理。 普通用户最常用的实现&#xff0c;有时甚至是在不知不觉中&#xff0c;是 NumPy 的改编。然而&#xff0c;尽管它很受欢迎&#xf…...

群狼调研(长沙政策第三方评估)| 社情民意调查的内容

本文由群狼调研(长沙社会舆情调查)出品&#xff0c;欢迎转载&#xff0c;请注明出处。社情民意调查旨在捕捉公众对各种社会问题的态度、意见和看法&#xff0c;社情民意调查的内容通常包括以下几个方面&#xff1a; 1. 社会热点问题&#xff1a;针对当前社会热点问题进行调查&…...

【三维重建】【深度学习】NeuS代码Pytorch实现--测试阶段代码解析(上)

【三维重建】【深度学习】NeuS代码Pytorch实现–测试阶段代码解析(上) 论文提出了一种新颖的神经表面重建方法&#xff0c;称为NeuS&#xff0c;用于从2D图像输入以高保真度重建对象和场景。在NeuS中建议将曲面表示为有符号距离函数(SDF)的零级集&#xff0c;并开发一种新的体绘…...

day-24 代码随想录算法训练营(19)回溯part01

77.组合 思路一&#xff1a;回溯相当于枚举&#xff0c;所以我们遍历1-n的每一个数字&#xff0c;然后在遍历第i位的同时递归出第i1~n位的组合结果&#xff0c;跟树的形式相似。 如上图所示&#xff0c;当长度为k时&#xff0c;即退出递归可对遍历到第i位以及剩下位数与k进行比…...

Redis之SYNC与PSYNC命令

一、复制SYNC与PSYNC 在Redis主从架构中&#xff0c;主要有以下两种情形需要进行数据同步 &#xff08;1&#xff09;当新的服务器执行slave of 命令&#xff0c;成为主服务器的从服务器。这时候从服务器会向主服务器发送SYNC命令&#xff0c;请求全量同步数据&#xff0c;主服…...

共创无线物联网数字化新模式|协创数据×企企通采购与供应链管理平台项目成功上线

近日&#xff0c;全球无线物联网领先者『协创数据技术股份有限公司』&#xff08;以下简称“协创数据”&#xff09;SRM采购与供应链项目全面上线&#xff0c;并于近日与企企通召开成功召开项目上线总结会。 基于双方资源和优势&#xff0c;共同打造了物联网特色的数字化采购供…...

【深入理解jvm读书笔记】jvm如何进行内存分配

jvm如何进行内存分配 内存分配方式内存分配方式的选择并发场景下的内存分配内存空间的初始化构造函数 内存分配方式 指针碰撞空闲列表 指针碰撞法&#xff1a; 假设Java堆中内存是绝对规整的&#xff0c;所有被使用过的内存都被放在一边&#xff0c;空闲的内存被放在另一边&a…...

OpenCV使用CMake和MinGW-w64的编译安装

OpenCV使用CMake和MinGW-w64的编译安装中的问题 问题&#xff1a;gcc: error: long: No such file or directory** C:\PROGRA~2\Dev-Cpp\MinGW64\bin\windres.exe: preprocessing failed. modules\core\CMakeFiles\opencv_core.dir\build.make:1420: recipe for target ‘modul…...

亚马逊买家怎么留评

亚马逊买家可以按照以下步骤在购买后留下产品评价&#xff1a; 1、登录亚马逊账户&#xff1a;首先&#xff0c;在网页浏览器中打开亚马逊网站&#xff0c;登录你的亚马逊账户。 2、找到订单&#xff1a;在页面上找到并点击你购买过的商品的"我的订单"或"订单…...

并查集 size 的优化(并查集 size 的优化)

目录 并查集 size 的优化 Java 实例代码 UnionFind3.java 文件代码&#xff1a; 并查集 size 的优化 按照上一小节的思路&#xff0c;我们把如下图所示的并查集&#xff0c;进行 union(4,9) 操作。 合并操作后的结构为&#xff1a; 可以发现&#xff0c;这个结构的树的层相对…...

Qt关于hex转double,或者QByteArray转double

正常的00 ae 02 33这种类型的hex数据类型可以直接通过以下代码进行转换 double QDataConversion::hexToDouble(QByteArray p_buf) {double retValue 0;if(p_buf.size()>4){QString str1 byteArrayToHexStr(p_buf.mid(0,1));QString str2 byteArrayToHexStr(p_buf.mid(1,…...

Java“牵手”根据关键词搜索(分类搜索)拼多多商品列表页面数据获取方法,拼多多API实现批量商品数据抓取示例

拼多多商城是一个网上购物平台&#xff0c;售卖各类商品&#xff0c;包括服装、鞋类、家居用品、美妆产品、电子产品等。要获取拼多多商品列表和商品详情页面数据&#xff0c;您可以通过开放平台的接口或者直接访问拼多多商城的网页来获取商品列表和详情信息。以下是两种常用方…...

Linux相关知识点

Linux是什么&#xff1f; Linux是一套免费使用和自由传播的类Unix操作系统&#xff0c;是一个基于POSIX和UNIX的多用户、多任务、支持多线程和多CPU的操作系统。它能运行主要的UNIX工具软件、应用程序和网络协议。它支持32位和64位硬件。 Linux内核 是一个Linux系统的内核&…...

常见的的数据结构

数组&#xff08;Array&#xff09;&#xff1a;一组按顺序排列的元素的集合&#xff0c;可以通过索引访问和修改元素。 链表&#xff08;Linked List&#xff09;&#xff1a;由一系列节点组成的数据结构&#xff0c;每个节点包含数据和指向下一个节点的指针。 栈&#xff0…...

专业心理咨询师助你轻装上阵,向内耗说不!

引言 身为技术人&#xff0c;你是否经常感觉自己被掏空了精力&#xff0c;行动力不佳&#xff1f;又或者觉得自己的工作没有成就和意义&#xff0c;工作状态持续不佳&#xff1f;你是否总有一种无法消除的疲惫&#xff1f;即使没有学习、工作&#xff0c;而是选择看剧、刷短视频…...

Ubuntu安装mysql5.7

目录 1. 更新系统软件包2. 安装MySQL 5.73. 启动MySQL 服务4. 设置MySQL root 密码5. 验证MySQL 安装6. 启用远程访问7. 创建新用户8. 为新用户授予权限9. mysql命令 以Ubuntu 18.04系统为例&#xff0c;安装MySQL 5.7。操作步骤如下&#xff1a; 1. 更新系统软件包 sudo apt…...

Java 语言特性(面试系列2)

一、SQL 基础 1. 复杂查询 &#xff08;1&#xff09;连接查询&#xff08;JOIN&#xff09; 内连接&#xff08;INNER JOIN&#xff09;&#xff1a;返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...

React Native 开发环境搭建(全平台详解)

React Native 开发环境搭建&#xff08;全平台详解&#xff09; 在开始使用 React Native 开发移动应用之前&#xff0c;正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南&#xff0c;涵盖 macOS 和 Windows 平台的配置步骤&#xff0c;如何在 Android 和 iOS…...

Cesium1.95中高性能加载1500个点

一、基本方式&#xff1a; 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...

【位运算】消失的两个数字(hard)

消失的两个数字&#xff08;hard&#xff09; 题⽬描述&#xff1a;解法&#xff08;位运算&#xff09;&#xff1a;Java 算法代码&#xff1a;更简便代码 题⽬链接&#xff1a;⾯试题 17.19. 消失的两个数字 题⽬描述&#xff1a; 给定⼀个数组&#xff0c;包含从 1 到 N 所有…...

YSYX学习记录(八)

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

【第二十一章 SDIO接口(SDIO)】

第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...

微服务商城-商品微服务

数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...

Rust 异步编程

Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...

AI编程--插件对比分析:CodeRider、GitHub Copilot及其他

AI编程插件对比分析&#xff1a;CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展&#xff0c;AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者&#xff0c;分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...

SQL Server 触发器调用存储过程实现发送 HTTP 请求

文章目录 需求分析解决第 1 步:前置条件,启用 OLE 自动化方式 1:使用 SQL 实现启用 OLE 自动化方式 2:Sql Server 2005启动OLE自动化方式 3:Sql Server 2008启动OLE自动化第 2 步:创建存储过程第 3 步:创建触发器扩展 - 如何调试?第 1 步:登录 SQL Server 2008第 2 步…...