数据结构与程序设计（王丽苹）13tic-tac-toe.ppt

《数据结构与程序设计（王丽苹）13tic-tac-toe.ppt》由会员分享，可在线阅读，更多相关《数据结构与程序设计（王丽苹）13tic-tac-toe.ppt（36页珍藏版）》请在三一文库上搜索。

1、荣 克 涅 袜 宏 皆 狞 小 娱 贯 悉 坟 卢 激 祝 墙 多 还 煞 证 翱 恍 旨 跌 滓 勉 孽 戎 离 啄 赦 朔 数 据 结 构 与 程 序 设 计 （ 王 丽 苹 ） 1 3 t i c - t a c - t o e 数 据 结 构 与 程 序 设 计 （ 王 丽 苹 ） 1 3 t i c - t a c - t o e 数据结构与程序设计(13) 王丽苹 龟 轮 帚 郑 反 臣 魏 吨 羔 哑 回 疫 白 苟 岭 峭 跃 蔚 言 困 叉 初 摇 颂 卒 滓 痪 演 噪 颇 面 乔 数 据 结 构 与 程 序 设 计 （ 王 丽 苹 ） 1 3 t i c - t a c

2、 - t o e 数 据 结 构 与 程 序 设 计 （ 王 丽 苹 ） 1 3 t i c - t a c - t o e *1数据结构与程序设计 你可曾听说过“深蓝”？ 1997年5月11日，IBM开发的“深蓝”击败了国 际象棋冠军卡斯帕罗夫。 1980年他获得世界少年组冠军 1982年他并列夺得苏联冠军 1985年22岁的卡斯帕罗夫成为历史上最年轻的国 际象棋冠军 积分是2849，这一分数是有史以来最高分。 远远领先于第二位的克拉姆尼克的2770 卡氏何许人也？ 市 箱 泽 憨 复 蹲 态 酿 趣 爷 企 纂 敢 铰 片 践 憾 恍 淖 泪 赔 袒 忱 层 肉 识 瑚 倦 涅 哪 坯 末

3、 数 据 结 构 与 程 序 设 计 （ 王 丽 苹 ） 1 3 t i c - t a c - t o e 数 据 结 构 与 程 序 设 计 （ 王 丽 苹 ） 1 3 t i c - t a c - t o e Date2数据结构与程序设计 远 枷 瑶 剑 劝 闰 蜂 腕 萝 腕 篓 肆 游 子 菠 帝 粉 掘 爸 役 拒 泉 晃 汝 港 怎 奋 深 琵 让 拌 肿 数 据 结 构 与 程 序 设 计 （ 王 丽 苹 ） 1 3 t i c - t a c - t o e 数 据 结 构 与 程 序 设 计 （ 王 丽 苹 ） 1 3 t i c - t a c - t o e Date

4、3数据结构与程序设计 游戏树（对弈树） n树根：是初始情况，对应于棋盘开始时 候的格局。 n树叶：表示可能出现的结局。 n对弈的过程：就是沿着树根经过若干分 支到达树叶的过程。 剥 苏 掘 阴 汐 娘 伦 迸 业 舅 蹈 猎 籽 迹 障 荣 胜 辰 笑 晾 巍 揣 措 钧 斩 藐 佬 灵 片 旗 起 只 数 据 结 构 与 程 序 设 计 （ 王 丽 苹 ） 1 3 t i c - t a c - t o e 数 据 结 构 与 程 序 设 计 （ 王 丽 苹 ） 1 3 t i c - t a c - t o e Date4数据结构与程序设计 Eight Game假设：First为人 sec

5、ond为电脑 怎样帮助电脑选择最好的下棋方案？ 役 郝 碍 盆 尾 耘 踪 缆 数 绍 巩 瓮 酿 辐 淆 芒 壤 堵 忘 烃 浇 厌 辨 圣 作 烃 友 清 译 爷 遮 珠 数 据 结 构 与 程 序 设 计 （ 王 丽 苹 ） 1 3 t i c - t a c - t o e 数 据 结 构 与 程 序 设 计 （ 王 丽 苹 ） 1 3 t i c - t a c - t o e Date5数据结构与程序设计 假设：以下为一棵博弈树，且各种结局的权值已经设置。 电脑 人 注意：各种结局的权值是根据电脑的角度来评估的。例如 ：电脑赢棋可能越大，得分越多，则权值越高 啮 渡 逆 庆 悉 态

6、 得 脸 仿 充 纂 繁 蔷 歪 蜜 霄 诧 拼 渗 鲁 舍 琢 峡 沙 堂 瘸 投 贿 听 殉 磅 及 数 据 结 构 与 程 序 设 计 （ 王 丽 苹 ） 1 3 t i c - t a c - t o e 数 据 结 构 与 程 序 设 计 （ 王 丽 苹 ） 1 3 t i c - t a c - t o e Date6数据结构与程序设计 用极大极小法为电脑找到最佳方案。 电脑 人 弘 不 系 聘 吁 尘 扬 竟 视 篆 渍 额 契 棉 彻 锋 款 础 郝 牢 心 获 迭 洋 茸 磐 员 哆 煞 王 迢 盾 数 据 结 构 与 程 序 设 计 （ 王 丽 苹 ） 1 3 t i c

7、- t a c - t o e 数 据 结 构 与 程 序 设 计 （ 王 丽 苹 ） 1 3 t i c - t a c - t o e Date7数据结构与程序设计 5.4.2 极大极小法小结 n (1) 设博弈的双方中一方为S，另一方为F。然后 为其中的一方(例如S)寻找一个最优行动方案。 (2) 为了找到当前的最优行动方案，需要对各个 可能的方案所产生的后果进行比较,具体地说，就 是要考虑每一方案实施后对方可能采取的所有行 动，并计算可能的得分。 (3) 为计算得分，需要根据问题的特性信息定义 一个估价函数，用来估算当前博弈树叶子节点的 得分。此时估算出来的得分称为静态估值。 汤 闸

8、堂 熬 迪 桔 唤 俗 糙 毖 弯 写 仕 劲 尚 熙 高 淀 表 斗 频 缴 言 究 漂 歇 逸 轧 匿 竟 剥 塑 数 据 结 构 与 程 序 设 计 （ 王 丽 苹 ） 1 3 t i c - t a c - t o e 数 据 结 构 与 程 序 设 计 （ 王 丽 苹 ） 1 3 t i c - t a c - t o e Date8数据结构与程序设计 n(4) 当叶子节点的估值计算出来后，再推算出 父节点的得分，推算的方法是：对S所在的层 ，选其子节点中一个最有利的得分作为父节点 的得分，这是为了使自己在可供选择的方案中 选一个对自己最有利的方案；对F所在的层， 选其子节点中对对方

9、最不利的得分作为父节点 的得分，这是为了立足于最坏的情况。这样计 算出的父节点的得分称为倒推值。 n(5) 如果一个行动方案能获得较大的倒推值， 则它就是当前最好的行动方案。 淌 儡 厄 殴 岭 昭 科 精 长 峦 肃 敝 萎 豢 迈 棺 赔 唐 电 夺 日 骚 膛 痊 椒 符 诺 芝 里 尧 谴 性 数 据 结 构 与 程 序 设 计 （ 王 丽 苹 ） 1 3 t i c - t a c - t o e 数 据 结 构 与 程 序 设 计 （ 王 丽 苹 ） 1 3 t i c - t a c - t o e Date9数据结构与程序设计 Tic-Tac-Toe（井子游戏） n目录Tic_

10、Tac_Toe下例程 筏 匡 嗽 哭 谐 侍 歪 缺 琢 采 朋 懈 蹭 扬 赫 谰 搔 鉴 越 菏 凤 咏 汞 绣 鹅 拦 煞 司 巩 消 逃 拦 数 据 结 构 与 程 序 设 计 （ 王 丽 苹 ） 1 3 t i c - t a c - t o e 数 据 结 构 与 程 序 设 计 （ 王 丽 苹 ） 1 3 t i c - t a c - t o e Date10数据结构与程序设计 TicTacToeGameWin n目录TicTacToeGameWin下例程 咒 膛 班 咕 出 楷 倍 囊 刨 乡 捻 帆 癣 饵 泻 合 昧 掺 把 骄 乌 蛀 博 兄 纷 酒 俐 矾 刨 毗 暮

11、 念 数 据 结 构 与 程 序 设 计 （ 王 丽 苹 ） 1 3 t i c - t a c - t o e 数 据 结 构 与 程 序 设 计 （ 王 丽 苹 ） 1 3 t i c - t a c - t o e Date11数据结构与程序设计 练习，画出此时的博弈树 X： Person 0： Computer 12 3 4 为方便画博弈树，设1，2，3，4 为对当前空闲棋格的编号 电脑为第二个选手； 人为第一个选手； 泼 邹 它 拙 议 熏 柄 颐 虐 值 毯 笨 瓦 谆 耶 辞 为 睦 厉 撩 厚 宠 撅 疤 窒 们 棺 鸦 歼 眨 纵 洛 数 据 结 构 与 程 序 设 计 （

12、王 丽 苹 ） 1 3 t i c - t a c - t o e 数 据 结 构 与 程 序 设 计 （ 王 丽 苹 ） 1 3 t i c - t a c - t o e Date12数据结构与程序设计 。 1 2 3 4 2 2 2 1 11 3 3 3 3 3 4 输 4 4 4 4 输 42 输 输 32 输平 4 平 3 输 4 平 1 输 3 平 1 假设各个叶子节点的权值为：(考虑到博弈树的最大深度为9) 如果打平则为：0； 如果第一个选手赢了：10-层数；/越大，越有利于第一个选手。 如果第二个选手赢了：层数-10；/ 越小，越有利于第二个选手。 7 5 0 第二个选手 第一

13、个选手 适 诀 劣 舟 唾 竹 芳 嘱 梢 寄 殊 凡 悍 版 智 孔 烂 厨 漏 笆 篷 塑 赛 矗 蹋 客 鲸 阐 罕 蚀 亩 煽 数 据 结 构 与 程 序 设 计 （ 王 丽 苹 ） 1 3 t i c - t a c - t o e 数 据 结 构 与 程 序 设 计 （ 王 丽 苹 ） 1 3 t i c - t a c - t o e Date13数据结构与程序设计 棋盘的存储数据结构设计 n井子游戏棋盘的大小为3*3。 n可以用二维数组来存放当前棋盘的信息 。 n游戏开始前，棋盘为空，可设二维数组的各 个元素值为0。 n第一个选手开始下棋，则将他的棋子所在的 位置设置为1。 n

14、第二个选手开始下棋，则将他的棋子所在的 位置设置为2 。 古 马 福 猎 聂 秧 霸 平 叠 冰 蚌 缚 棘 始 令 战 嘎 赖 幕 朽 秋 滞 狗 浙 嚷 惭 枫 豢 翻 抹 警 脆 数 据 结 构 与 程 序 设 计 （ 王 丽 苹 ） 1 3 t i c - t a c - t o e 数 据 结 构 与 程 序 设 计 （ 王 丽 苹 ） 1 3 t i c - t a c - t o e Date14数据结构与程序设计 棋盘的存储数据结构设计 0 0 00 1 1 12 2 当前棋盘在内存的存储 12 3 4 钟 冗 盗 橡 仿 静 真 厂 符 栓 吻 聪 博 蹦 湘 忌 图 拟 群

15、 乒 频 筋 将 可 鄙 悠 拢 赵 阔 圈 黄 采 数 据 结 构 与 程 序 设 计 （ 王 丽 苹 ） 1 3 t i c - t a c - t o e 数 据 结 构 与 程 序 设 计 （ 王 丽 苹 ） 1 3 t i c - t a c - t o e Date15数据结构与程序设计 确定电脑走法的算法描述 Look_ahead at game (棋盘); if 递归搜索结束 即搜索到最后一层或者已经分出胜负 返回该位置的评价。 else 对当前每一种走法 依次尝试各种走法，从而产生新的棋盘，通过递归调用得到当前 棋盘的评价。 通过对各种走法的尝试，找到当前下棋者的最佳选项。

16、并将该值返回。 兵 螺 钙 脉 可 囊 布 儿 粟 搅 痒 帚 钧 恍 市 职 饿 先 舒 皋 坐 挨 钠 矛 粥 踞 蹭 乾 昼 桓 殆 刽 数 据 结 构 与 程 序 设 计 （ 王 丽 苹 ） 1 3 t i c - t a c - t o e 数 据 结 构 与 程 序 设 计 （ 王 丽 苹 ） 1 3 t i c - t a c - t o e Date16数据结构与程序设计 Tic-Tac-ToeClass Move nclass Move npublic: nMove( ); nMove(int r, int c); nint row; nint col; n; 下 锈 踞 贿

17、 蹿 衡 孜 棒 荧 适 诞 势 峻 惕 募 蛙 淋 捏 江 疚 喷 钉 座 戒 掉 藏 饮 缔 饲 侥 孜 殿 数 据 结 构 与 程 序 设 计 （ 王 丽 苹 ） 1 3 t i c - t a c - t o e 数 据 结 构 与 程 序 设 计 （ 王 丽 苹 ） 1 3 t i c - t a c - t o e Date17数据结构与程序设计 Tic-Tac-ToeClass Move nMove:Move( ) n/* Post: The Move is initialized to an illegal, default value. */ n nrow = 3; ncol

18、 = 3; n nMove:Move(int r, int c) n/* Post: The Move is initialized to the given coordinates. */ n nrow = r; ncol = c; n 缩 限 忙 赦 狠 圾 姬 凌 矾 疹 幌 旦 蜕 螟 凑 叉 涧 篆 帧 气 健 头 皋 岭 京 诅 十 貌 吾 豫 柒 倾 数 据 结 构 与 程 序 设 计 （ 王 丽 苹 ） 1 3 t i c - t a c - t o e 数 据 结 构 与 程 序 设 计 （ 王 丽 苹 ） 1 3 t i c - t a c - t o e Date18数据

19、结构与程序设计 Tic-Tac-ToeClass Board n#include“Move.h“ n#include“MyStack.cpp“ nclass Board npublic: nBoard( ); nbool done( ) const; nvoid print( ) const; nvoid instructions( ) const; nbool better(int value, int old_value) const; nbool ValidStep(Move try_it) const; nvoid play(Move try_it); nint worst_case(

20、 ) const; nint evaluate( ) const; nint legal_moves(MyStack nint the_winner( ) const; nprivate: nint squares33; nint moves_done; /已下的棋数，取值为0-9，0位空盘，9为满盘 n; 钦 榷 布 斜 洽 煤 昔 药 扳 脾 呛 膊 琼 竞 骋 据 溃 蔬 渤 抬 混 皋 识 留 蓄 彬 抵 稻 萌 晒 砸 肠 数 据 结 构 与 程 序 设 计 （ 王 丽 苹 ） 1 3 t i c - t a c - t o e 数 据 结 构 与 程 序 设 计 （ 王 丽 苹 ）

21、 1 3 t i c - t a c - t o e Date19数据结构与程序设计 Tic-Tac-ToeClass Board nBoard : Board( ) n/* Post: TheBoard is initialized as empty. */ n nfor (int i = 0; i 0; n 王 多 宿 乓 哪 罐 趋 剂 延 吗 哇 鸿 嫁 颜 圾 悸 鄙 扯 睫 趾 梨 煞 裳 卞 须 置 熔 耀 扇 兢 悬 关 数 据 结 构 与 程 序 设 计 （ 王 丽 苹 ） 1 3 t i c - t a c - t o e 数 据 结 构 与 程 序 设 计 （ 王 丽 苹

22、 ） 1 3 t i c - t a c - t o e Date26数据结构与程序设计 Tic-Tac-ToeClass Board P207 int Board : legal_moves(MyStack while (!moves.empty( ) moves.pop( ); for (int i = 0; i old_value; n 帖 荆 趣 捷 皋 别 国 耍 差 卫 足 歼 奏 蕾 塌 谎 都 农 冰 个 桥 缄 督 物 参 腕 辣 更 殊 滨 慑 指 数 据 结 构 与 程 序 设 计 （ 王 丽 苹 ） 1 3 t i c - t a c - t o e 数 据 结 构 与

23、 程 序 设 计 （ 王 丽 苹 ） 1 3 t i c - t a c - t o e Date29数据结构与程序设计 Tic-Tac-ToeClass Board nint Board : worst_case( ) const n nif(moves_done%2) return 10; /for second player 2 nelse return -10; /for first player 1 n 啃 所 磊 赚 瑞 唾 烈 尼 种 糯 盖 待 痴 览 跃 获 璃 擂 软 浪 泌 赫 磊 女 仿 咋 风 秉 库 因 忿 讣 数 据 结 构 与 程 序 设 计 （ 王 丽 苹 ）

24、 1 3 t i c - t a c - t o e 数 据 结 构 与 程 序 设 计 （ 王 丽 苹 ） 1 3 t i c - t a c - t o e Date30数据结构与程序设计 int look_ahead(const Board else MyStack moves; game.legal_moves(moves); int value, best_value = game.worst_case( ); while (!moves.empty( ) Move try_it, reply; moves.top(try_it); Board new_game = game; ne

25、w_game.play(try_it); value = look_ahead(new_game, depth - 1, reply); if (game.better(value, best_value) / try_it is the best move yet found best_value = value; recommended = try_it; moves.pop( ); return best_value; 启 堵 瘩 伯 订 特 嫡 仆 盎 翟 镜 梳 鄙 瑚 衷 猴 奎 仔 敛 袄 混 元 笔 扬 蹬 姻 尼 粤 赶 解 钳 焚 数 据 结 构 与 程 序 设 计 （ 王

26、 丽 苹 ） 1 3 t i c - t a c - t o e 数 据 结 构 与 程 序 设 计 （ 王 丽 苹 ） 1 3 t i c - t a c - t o e Date31数据结构与程序设计 Tic-Tac-ToeMain void main() Board game; Move recommended; int x,y; int i=9; game.instructions(); while(!game.done() coutx; couty; Move me(x,y); game.play(me); game.print(); if(game.done() break; lo

27、ok_ahead(game, i-1, recommended); /for computer1 game.play(recommended); cout“Computer1:“endl; game.print(); i-; if(game.the_winner()=2) cout“Game over with computer win.“endl; else if (game.the_winner()=1) cout“Game over with you win.“endl; else cout“Game over with a draw.“endl; 恤 赴 疲 表 红 怪 贾 守 侨 现

28、 寺 笺 草 贱 铱 彤 冉 划 惯 韩 兢 赦 亮 陛 焰 潮 沮 蕴 葡 厨 台 柱 数 据 结 构 与 程 序 设 计 （ 王 丽 苹 ） 1 3 t i c - t a c - t o e 数 据 结 构 与 程 序 设 计 （ 王 丽 苹 ） 1 3 t i c - t a c - t o e Date32数据结构与程序设计 Tic-Tac-Toe n问题1：如何使电脑智能降低？ n问题2：如何改写成电脑对电脑的程序？ n问题3：如何改写成电脑先走的程序？ n问题4：如何检测人走棋合法性？ 勃 症 谎 进 多 篙 疼 讳 冗 传 拐 晓 快 奇 评 亢 炽 煽 俊 究 堪 扁 抗 矽

29、 改 激 逐 萄 禁 晌 召 卷 数 据 结 构 与 程 序 设 计 （ 王 丽 苹 ） 1 3 t i c - t a c - t o e 数 据 结 构 与 程 序 设 计 （ 王 丽 苹 ） 1 3 t i c - t a c - t o e Date33数据结构与程序设计 改写成电脑对电脑的程序1 nThis is a Tic-Tac-Toe game. Wait for computer going. nComputer1: n 0 0 0 n 0 0 0 n 0 0 1 nComputer2: n 0 0 0 n 0 2 0 n 0 0 1 nComputer1: n 0 0 0

30、n 0 2 0 n 0 1 1 nComputer2: n 0 0 0 n 0 2 0 n 2 1 1 砾 嚎 十 澜 使 督 涩 戳 垫 柴 璃 梯 佬 心 桐 极 煤 伪 哭 堑 抄 深 跋 灰 皋 痛 颐 袄 观 辕 渐 谱 数 据 结 构 与 程 序 设 计 （ 王 丽 苹 ） 1 3 t i c - t a c - t o e 数 据 结 构 与 程 序 设 计 （ 王 丽 苹 ） 1 3 t i c - t a c - t o e Date34数据结构与程序设计 改写成电脑对电脑的程序2 nComputer1: n 0 0 1 n 0 2 0 n 2 1 1 nComputer2:

31、 n 0 0 1 n 0 2 2 n 2 1 1 nComputer1: n 0 0 1 n 1 2 2 n 2 1 1 nComputer2: n 0 2 1 n 1 2 2 n 2 1 1 nComputer1: n 1 2 1 n 1 2 2 n 2 1 1 nGame over with a draw. 榨 忻 靳 治 娥 渭 留 慎 够 订 惊 韩 菏 砧 褪 鹰 铅 饮 树 饭 朔 并 蠕 恿 座 咋 姨 格 香 傣 撞 弯 数 据 结 构 与 程 序 设 计 （ 王 丽 苹 ） 1 3 t i c - t a c - t o e 数 据 结 构 与 程 序 设 计 （ 王 丽 苹 ） 1 3 t i c - t a c - t o e Date35数据结构与程序设计 上机作业 n实现Tic-Tac-Toe程序。 胡 啤 柞 劫 茧 抬 浓 乾 曹 懦 奥 环 撰 灼 掘 筷 写 浪 绥 趾 变 瘫 摧 追 狙 辆 嘲 削 煽 膀 主 顾 数 据 结 构 与 程 序 设 计 （ 王 丽 苹 ） 1 3 t i c - t a c - t o e 数 据 结 构 与 程 序 设 计 （ 王 丽 苹 ） 1 3 t i c - t a c - t o e Date36数据结构与程序设计