德州扑克 BY 陈童 李楠. Outline  规则 介 绍  问题简 化及程序模 拟  模型 评 价与展望.

Presentation on theme: "德州扑克 BY 陈童 李楠. Outline  规则 介 绍  问题简 化及程序模 拟  模型 评 价与展望."— Presentation transcript:

1 德州扑克 BY 陈童 李楠

2 Outline  规则 介 绍  问题简 化及程序模 拟  模型 评 价与展望

3 游 戏规则：  发 牌者左 侧 小盲注  小盲注左 侧 大盲注  盖牌 （ FOLD ）、 跟注 （ CALL ）、 加注 （ RAISE ）  盖牌 、过 牌 （ CHECK ）、 下注 （ BET ）

4  第一 轮结 束 、 翻牌 （ FLOP ）  第二 轮（ 翻三 张 公共牌 ）  第三 轮（ 翻第四 张 公共牌 ）  第四 轮（ 公共牌全明 ）  比 较 牌的大小 （ 斗牌 ）

5 牌型比 较：  皇家同花 顺  同花 顺  四条  俘 虏  同花  顺 子  三条  两 对  一 对  高牌 （ 散牌 ）

6 问题简 化  双人 对战  过 程中双方均不盖牌 ， 直接比 较胜 率  已知己方两 张 牌

7 基本思路  分成两步 骤：  1 ： 假 设 五 张 公共牌已明 ， 即 进 行到第四 轮， 模 拟对 手牌型 ，计 算己方 胜 率  2 ： 假 设 五 张 公共牌均未知 ， 模 拟 公共牌和 对 手牌 ， 计 算己方 胜 率

8 数据 结 构与算法  使用大小 为 52 的一 维 数 组 表示可能的 52 种牌 ， 用 1 表示已 经 明 确存在于牌局中 ， 0 表示不存在或未明确 。 如 红 桃 A 标记为 a[1] = 1; 黑桃 2 标记为 a[5 + 1] = 1  设计评 价函数 ， 与 10 种可能的牌型 进 行 评 估 ，给 出 评 分 皇家同花 顺 同花 顺 四条俘虏俘虏 同花 顺子顺子三条两对两对 一对一对 高牌 510 ~13.5 18 ~25.5 30 ~36 40 ~48 50 ~53.5 60 ~66 70 ~76 80 ~86 90 ~104

9 数据 结 构与算法  function s = evaluate(a); s = ; if rflush_score(a)<s s = rflush_score(a);end; if sflush_score(a)<s s = sflush_score(a);end; if four(a)<s s = four(a);end; …  设计选择 函数 ， 在 7 张 中 选择评 价最高的 5 张 牌作 为 最 优 策略

10 时间 复 杂 度分析  公共牌已知 ：  公共牌未知 ：

11 随机抽 样 法  公共牌已知 ： 随机抽 样对 方牌型 ， 注意 检查 枚 举 到的牌是否已在牌局中  公共牌未知 ： 随机抽 样对 方牌型和公共牌 ， 注意牌的唯一性

12 随机抽 样 法的收 敛 性 * 引用自台湾 师 范大学扑克研究 论 文 ir.lib.ntnu.edu.tw/retrieve/45503/metadata_03_06_s_05_0018.pdf

13 模型 评 价与展望  最大的限制 ：时间  1 次 评 价的 时间约为 2s  将 时间 上的复 杂 度 转 移到空 间  使用其他 编 程 语 言 ，进 一步 优 化 评 价函数

14 模型 评 价与展望  核心数据 结 构 ： 牌型表示  现 有数 组 表示效率和利用率不高  使用位运算和哈希表 * 引用自 The Great Poker Hand Evaluator Roundup http://www.codingthewheel.com/archives/poker-hand-evaluator-roundup/

15 模型 评 价与展望  推广到多人  加入下注的考 虑  对处 理如此复 杂 度极高的 问题 的启示

16 THANK YOU FOR LISTENING!