当前位置: 首页 > 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…...

Leetcode 3577. Count the Number of Computer Unlocking Permutations

Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接&#xff1a;3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯&#xff0c;要想要能够将所有的电脑解锁&#x…...

NFT模式:数字资产确权与链游经济系统构建

NFT模式&#xff1a;数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新&#xff1a;构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议&#xff1a;基于LayerZero协议实现以太坊、Solana等公链资产互通&#xff0c;通过零知…...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

什么是Ansible Jinja2

理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具&#xff0c;可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板&#xff0c;允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板&#xff0c;并通…...

2023赣州旅游投资集团

单选题 1.“不登高山&#xff0c;不知天之高也&#xff1b;不临深溪&#xff0c;不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...

Docker 本地安装 mysql 数据库

Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker &#xff1b;并安装。 基础操作不再赘述。 打开 macOS 终端&#xff0c;开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...

PAN/FPN

import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...

人工智能(大型语言模型 LLMs)对不同学科的影响以及由此产生的新学习方式

今天是关于AI如何在教学中增强学生的学习体验&#xff0c;我把重要信息标红了。人文学科的价值被低估了 ⬇️ 转型与必要性 人工智能正在深刻地改变教育&#xff0c;这并非炒作&#xff0c;而是已经发生的巨大变革。教育机构和教育者不能忽视它&#xff0c;试图简单地禁止学生使…...

JS手写代码篇----使用Promise封装AJAX请求

15、使用Promise封装AJAX请求 promise就有reject和resolve了&#xff0c;就不必写成功和失败的回调函数了 const BASEURL ./手写ajax/test.jsonfunction promiseAjax() {return new Promise((resolve, reject) > {const xhr new XMLHttpRequest();xhr.open("get&quo…...

Rust 开发环境搭建

环境搭建 1、开发工具RustRover 或者vs code 2、Cygwin64 安装 https://cygwin.com/install.html 在工具终端执行&#xff1a; rustup toolchain install stable-x86_64-pc-windows-gnu rustup default stable-x86_64-pc-windows-gnu ​ 2、Hello World fn main() { println…...