博弈树-BIT

article/2025/10/8 19:19:47

博弈树-BIT

下棋属于一种博弈游戏，博弈过程可以用树（博弈树）来表示。假设游戏由两个人（ A 和 B ）玩，开始由某个人从根结点开始走，两个人轮流走棋，每次只能走一步， 下一步棋只能选择当前结点的孩子结点，谁先走到叶子结点为胜。例如，对于下图所示的博弈树，若 A 先走，可以选 f ， B 若选 h ，则 A 选 j 胜。

tree

编写一程序，让计算机和人下棋。当计算机走下一步时，可以根据以下情况决定下一步：
（1） 若存在可以确保取胜的一个孩子结点，则选择该结点作为下一步；
（2） 若存在多个可以确保取胜的孩子结点，则选择其中高度最小的结点作为下一步（若有多个选择，则选最左边的结点）；
（3） 若不存在可以确保取胜的一个孩子结点，则选择高度最大的孩子结点作为下一步（若有多个选择，则选最左边的结点）；

例： （下面的黑体为输入）

(a,(b,(x)),(c,(d),(e,(g),(h)),(f)))

a
b
x
c
d
e
g
h
f

Who play first(0: computer; 1: player )?
1
player:
c
computer: d
Sorry, you lost.
Continue(y/n)?
y
Who play first(0: computer; 1: player )?
1
player:
x
illegal move.
player:
b
computer: x
Sorry, you lost.
Continue(y/n)?
y
Who play first(0: computer; 1: player )?
0
computer: c
player:
f
Congratulate, you win.
Continue(y/n)?
n

大体思路：
先根据给出的广义表结构创立广义表，再根据建立的广义表创立树（这里采用了孩子兄弟表示法），关于建立广义表和根据广义表的步骤请参考《数据结构》教材，这里不加赘述。
下棋嘛，就是两个人的事，这里就是人和电脑的事。
人所下的位置是由输入决定的，对它的孩子节点进行遍历就能找到下一个位置，只要处理好非法输入的情况就好了。
而对于电脑，我们就需要做到题目要求的三点，
（1）对于电脑来说，非胜即败，通过预处理让电脑知道哪个点是必胜点，那个点是必败点，清楚了结果之后再 玩游戏，就可以开始“欺负”人类了。（叶子节点是必胜点，它的孩子节点全部为必败点的节点为必胜点，其他节点均视为必败点）
（2）（3）计算节点的高度，必胜点考虑最小高度，必败点考虑最大高度

#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>#define OK 1
#define YES 1
#define NO 0
#define ERROR 0
#define MAX_SIZE 10005using namespace std;const int INF = 0x3f3f3f3f;
typedef char ElemType;
typedef char AtomType;
typedef int Status;
typedef long long ll;typedef enum {ATOM, LIST} ElemTag;
typedef struct GLNode {ElemTag tag;union {AtomType atom;struct {struct GLNode *hp, *tp;}ptr;};
} * Glist;typedef struct Tnode{ElemType data;int status;struct Tnode * firstchild, * nextsibling;
} * Tree;string emp("()");Status CreateGlist(Glist &L, string s);
Status sever(string &str, string &hstr);
Glist GetHead(Glist L);
Glist GetTail(Glist L);
void CreateTree(Tree &T, Glist L);
Status pre_deal(Tree T);
Status play(Tree T);
int get_height(Tree T);
Status who_play_first();
Status illegal_move();
Tree computer_do(Tree T);
Tree human_do(Tree T);int main() {string s;cin >> s;int i;for(i = 0; s[i] != '\0'; i++) {if(s[i] >= 'a' && s[i] <= 'z') printf("%c\n", s[i]);}Glist L;CreateGlist(L, s);Tree T;CreateTree(T, L);pre_deal(T);play(T);return 0;
}Status CreateGlist(Glist &L, string s) {  //建立广义表if(s == emp) {L = NULL;}else {L = new GLNode;if(s.length() == 1) {    //原子节点L ->tag = ATOM;L ->atom = s[0];}else {    //表结点L ->tag = LIST;string sub, hsub;sub = s.substr(1, s.size() - 2);//cout << sub;Glist p, q;p = L;while(!sub.empty()) {sever(sub, hsub);    //分离头尾//cout << sub << endl;//cout << hsub << endl;CreateGlist(p ->ptr.hp, hsub);q = p;if(!sub.empty()) {    //若尾表非空，创建尾表指向以便递归使用p = new GLNode;p ->tag = LIST;q ->ptr.tp = p;}}q ->ptr.tp = NULL;}    //else 创建表结点}    //else 表不空return OK;
}Status sever(string &str, string &hstr) {  //头尾分离函数（用于建立广义表）int i, k = 0;int n = str.length();char ch = '\0';for(i = 0; i < n && (ch != ',' || k != 0); i++) {ch = str[i];if(ch == '(') {k++;}if(ch == ')') {k--;}}if(i < n) {hstr = str.substr(0, i - 1);str = str.substr(i, n - i);//cout << hstr << endl;//cout << str << endl;}else {hstr = str;str.clear();}return OK;
}Glist GetHead(Glist L) {if(L) {return L ->ptr.hp;}else {return NULL;}
}Glist GetTail(Glist L) {if(L) {return L ->ptr.tp;}else {return NULL;}
}void CreateTree(Tree &T, Glist L) {  //根据广义表建立树if(L) {T = new Tnode;T ->data = GetHead(L) ->atom;T ->firstchild = NULL;T ->nextsibling = NULL;if(GetTail(L)) {Glist h = GetHead(GetTail(L));Glist t = GetTail(GetTail(L));CreateTree(T ->firstchild, h);Tnode * p = T ->firstchild;while(t) {h = GetHead(t);t = GetTail(t);CreateTree(p ->nextsibling, h);p = p ->nextsibling;}p ->nextsibling = NULL;}}else {T = NULL;}return;
}Status play(Tree T) {while(1) {who_play_first();int player, flag = 0;scanf("%d", &player);Tree p = T;switch(player) {case 0:p = computer_do(T);flag = 0;break;case 1:p = human_do(T);flag = 1;break;default: exit(-1);}if(p ->firstchild == NULL) {// 本局结束if(flag == 0) {printf("Sorry,you lost.\n");}else {printf("Congratulate,you win.\n");}printf("Continue(y/n)?\n");char c;getchar();scanf("%c", &c);if(c == 'y') {continue;}else {return OK;}}if(flag == 1 && p != T) {  //下一步电脑while(1) {  //循环电脑-人-电脑-人-...p = computer_do(p);if(p ->firstchild == NULL) {printf("Sorry,you lost.\n");printf("Continue(y/n)?\n");char c;getchar();scanf("%c", &c);if(c == 'y') {break;}else {return OK;}} while(1) {  //处理因输入错误而重来的情况Tree q;q = human_do(p);if(q != p) {p = q;break;}}if(p ->firstchild == NULL) {printf("Congratulate,you win.\n");printf("Continue(y/n)?\n");char c;getchar();scanf("%c", &c);if(c == 'y') {break;}else {return OK;}} }}else {  //下一步人while(1) {  //思路同上while(1) {Tree q;q = human_do(p);if(q != p) {p = q;break;}}if(p ->firstchild == NULL) {printf("Congratulate,you win.\n");printf("Continue(y/n)?\n");char c;getchar();scanf("%c", &c);if(c == 'y') {break;}else {return OK;}}p = computer_do(p);if(p ->firstchild == NULL) {printf("Sorry,you lost.\n");printf("Continue(y/n)?\n");char c;getchar();scanf("%c", &c);if(c == 'y') {break;}else {return OK;}}}}}return OK;
}Status pre_deal(Tree T) { //预处理if(T) {if(T ->firstchild == NULL) {T ->status = 1;}pre_deal(T ->firstchild);pre_deal(T ->nextsibling);Tnode * p = T;if(T ->firstchild) {p = T ->firstchild;int flag = 1;while(p) {if(p ->status == 1) {flag = 0;break;}p = p ->nextsibling;}if(flag) {T ->status = 1;}else {T ->status = 0;}}}return OK;
}Status who_play_first() {printf("Who play first(0:computer;1:player)?\n");return OK;
}Status illegal_move() {printf("illegal move.\n");return OK;
}Tree computer_do(Tree T) {  //电脑进行一轮操作int victory_h = INF, false_h = 0;Tree p = T, q1, q2;if(p ->firstchild) {p = p ->firstchild;while(p) {int h = get_height(p);if(p ->status == 1) {if(h < victory_h) {victory_h = h;q1 = p;}}else {if(h > false_h) {false_h = h;q2 = p;}}p = p ->nextsibling;}if(victory_h != INF) {printf("computer:%c\n", q1 ->data);return q1;}else {printf("computer:%c\n", q2 ->data);return q2;}}return T;
}Tree human_do(Tree T) {  //人进行一轮操作printf("player:\n");char c;getchar();scanf("%c", &c);Tnode * p = T;if(p ->firstchild) {p = p ->firstchild;while(p) {if(p ->data == c) {break;}p = p ->nextsibling;}}if(p) {return p;}else {illegal_move();return T;}
}int get_height(Tree T) {  //计算树的高度if(T == NULL) return 0;else {int h, h2;h = get_height(T ->firstchild);if(h != 0) {T = T ->firstchild;while(T) {h2 = get_height(T ->nextsibling);if(h < h2) {h = h2;}T = T ->nextsibling;}}return h + 1;}
}

http://chatgpt.dhexx.cn/article/h7r1nTlX.shtml

相关文章

第四章 博弈树game tree

第四章 博弈树game tree

这里写目录标题 perfect-information game从博弈树得到收益表subgamebackward induction 反向推导一个值得思考的例子&#xff1a; 另一个例子umperfect information extensive混合策略和行为策略&#xff08;mexed and behavioral strategies)不完美信息博弈的求解 博弈树用于…
阅读更多...
人工智能—— 博弈树的启发式搜索

人工智能—— 博弈树的启发式搜索

一、概述 博弈的概念 博弈是一类具有智能行为的竞争活动&#xff0c;如下棋、战争等。 博弈的类型 双人完备信息博弈&#xff1a;两位选手&#xff08;例如MAX和MIN &#xff09;对垒&#xff0c;轮流走步&#xff0c;每一方不仅知道对方已经走过的棋步&#xff0c;而且还能…
阅读更多...
博弈树与α-β剪枝

博弈树与α-β剪枝

一、评价函数&#xff08;Evaluation function&#xff09; 绝大部分的游戏&#xff0c;决策空间都相当庞大。 即使是最简单的三子棋&#xff08;又叫做“井”字棋&#xff0c;一字棋&#xff09;。它的第一步有9种决策&#xff0c;然后对面有9*872种决策&#xff0c;....&…
阅读更多...
博弈树

博弈树

博弈树的搜索 博弈树定义&#xff1a; 一类特殊的与或图 &#xff08;本次讨论的博弈树都是“与或图”&#xff09; 应用范围&#xff1a; 下棋、故障诊断、风险投资 基本搜索策略&#xff1a; 极小极大搜索&#xff08;min-max&#xff09; 优化的搜索方法&#xff1a; α…
阅读更多...
vim的目录树插件NERDtree的安装

vim的目录树插件NERDtree的安装

下载&#xff1a; https://github.com/preservim/nerdtree 上面是NERDTree插件的下载链接&#xff0c;在github上下载即可将下载的文件的解压&#xff0c;并通过虚拟机的共享文件夹共享到虚拟机 将共享的文件&#xff0c;复制到~./vim/ 目录下&#xff0c;如下图&#xff1a; …
阅读更多...
Vim的NerdTree插件

Vim的NerdTree插件

在vundle插件管理的方式&#xff0c;直接在~/.vimrc中的Plugin段落中加入Plugin "scrooloose/nerdtree "然后重启Vim并输入PluginInstall&#xff0c;即可完成安装 然后输入: NERDTreeToggle即可打开文件树。当然&#xff0c;默认是关闭的&#xff0c;需要每次都输入…
阅读更多...
分享一个Vim目录树的插件-NERDTree

分享一个Vim目录树的插件-NERDTree

之前的公司有目录树&#xff0c;方便很多&#xff0c;但是没把代码带过来&#xff0c;这次新找了一个&#xff0c;对于日常工作来说&#xff0c;确实方便很多。NERDTree是github上分享的免费的linux/vim上的目录树插件&#xff0c;有需要的可以参考原来的链接&#xff1a; NER…
阅读更多...
java之TreeNode

java之TreeNode

~ 前言 之前讲的HashMap机制遗漏了一个Tree的操作&#xff0c;我们在这里补上。如果是从头看到这里那么这一章也会非常容易。 后续讲解内容为源码实现&#xff0c;这里使用的是JDK8的版本。 红黑树 HashMap使用的树结构是红黑树&#xff0c;而红黑树是一个平衡二叉树&#xf…
阅读更多...
Vim升华之树形目录插件NERDTree安装图解

Vim升华之树形目录插件NERDTree安装图解

无意中看到实验室的朋友使用的vim竟然能在左边显示树形目录&#xff0c;感觉很方便&#xff0c;这样子文件夹有什么文件一目了然。她说是一个插件叫NERDTree&#xff0c;安装执行后的效果如下&#xff0c;不是你想要的效果就别安了。我的系统是Ubuntu12.04&#xff0c;版本不同…
阅读更多...
gvim安装NERDTree插件

gvim安装NERDTree插件

gvim安装NERDTree插件 安装vim plug遇到的问题安装成功 安装NERDTree插件遇到的问题安装成功 安装vim plug 访问网站链接: download vim-plug Linux终端命令敲入&#xff1a; curl -fLo ~/.vim/autoload/plug.vim --create-dirs \https://raw.githubusercontent.com/junegunn…
阅读更多...
安装NERDtree

安装NERDtree

无意中看到实验室的朋友使用的vim竟然能在左边显示树形目录&#xff0c;感觉很方便&#xff0c;这样子文件夹有什么文件一目了然。她说是一个插件叫NERDTree&#xff0c;安装执行后的效果如下&#xff0c;不是你想要的效果就别安了。我的系统是Ubuntu12.04&#xff0c;版本不同…
阅读更多...
nerdtree-git-plugin插件

nerdtree-git-plugin插件

给用 NERDTree 的同学推荐一个很好用的插件 nerdtree-git-plugin&#xff0c;这个插件能显示 git 管理的项目文件变更状态. 配置 这个插件是”开箱即用”的&#xff0c;不过建议大家做如下配置(用zsh的同学是不是很熟悉XD): let g:NERDTreeIndicatorMapCustom {\ "Mod…
阅读更多...
NERDTree安装

NERDTree安装

转自https://blog.csdn.net/qq_33862644/article/details/80545654 安装&#xff1a; 1、下载vundle&#xff08;管理插件工具&#xff09; git clone https://github.com/VundleVim/Vundle.vim.git ~/.vim/bundle/Vundle.vim 注意&#xff1a;~开始是下载到哪&#xff0c;…
阅读更多...
linux下Nerdtree安装方法

linux下Nerdtree安装方法

目录 1.下载Nerdtree 2. linux下安装 3. 成功享受吧 1.下载Nerdtree 百度网盘下载&#xff0c;地址为链接&#xff1a;百度网盘 请输入提取码 提取码&#xff1a;07e3 --来自百度网盘超级会员V4的分享 github方式下载&#xff0c;地址为 https://github.com/scrooloose/ner…
阅读更多...
GVim配置一个漂亮的NerdTree

GVim配置一个漂亮的NerdTree

GVim配置一个漂亮的NerdTree GVim使用也有一段时间了&#xff0c;有空写几个简单的教程帮助新手快速上手&#xff0c;定制一个个性化的编辑器把。以下是我的NerdTree效果展示。 NerdTree插件 NerdTree下载安装 如果你安装了插件管理器的化安装就很简单了&#xff0c;如果没有安…
阅读更多...
NERDTree插件安装和使用

NERDTree插件安装和使用

如何安装NERDTree插件&#xff0c;该插件显示一个目录树&#xff0c;可以执行一下文件的操作命令&#xff0c;首先添加配置&#xff1a; " 在vim中安装及配置NERDTree插件&#xff0c;放在Plugin gmarik/Vundle.vim 之后 Plugin scrooloose/nerdtree ""-----…
阅读更多...
Win系统中GVim8.2配置NerdTree插件

Win系统中GVim8.2配置NerdTree插件

目录 功能说明 NerdTree插件实现效果图&#xff1a; NerdTree安装&#xff1a; NerdTree配置 功能说明 NERDTree是Vim最常用的插件之一&#xff0c;可以在Vim运行时显示目录和文件结构&#xff0c;类似TextMate左侧的文件浏览器&#xff0c;但操作起来更为方便&#xff0c;…
阅读更多...
vim插件：显示树形目录插件NERDTree安装 和 使用

vim插件：显示树形目录插件NERDTree安装 和 使用

前言 一、下载和配置 NERDTree插件的官方地址如下&#xff0c;可以从这里获取最新的版本 https://github.com/scrooloose/nerdtree 下载zip安装包 或者使用下面官网源文件安装方法 我的实验环境是centos6.6,其他版本可能有些不同。 安装方法很简单&#xff0c;先把压缩文件下…
阅读更多...
VIM插件：目录导航与操作插件NERDTree的使用方法

VIM插件：目录导航与操作插件NERDTree的使用方法

VIM插件&#xff1a;目录导航与操作插件NERDTree的使用方法 &#x1f4d8; 从外部Buffer打开NERDTree的方法 &#x1f468;‍&#x1f4bb; 假设已经会了VIM的配置基本知识&#xff0c;并会安装和简单配置VIM插件了&#xff0c;如果这点不太熟悉&#xff0c;可以自行查看相关…
阅读更多...
webview跳转外部链接

webview跳转外部链接

提示&#xff1a;本文章主要讲述js点击跳转外链 前言 一、示例模板 二、使用步骤 1.需点击跳转页面&#xff08;假设为a&#xff09; 2.跳转页面&#xff08;假设为b&#xff09; 3.json文件中配置路由 4.配置业务域名 总结 前言 官方介绍&#xff0c;web-view这个组件…
阅读更多...
推荐文章

Copyright @ 2022~2023