Graphs and Games

图表和游戏

• 批准号: RGPIN-2014-04139
• 负责人: Nowakowski, Richard
• 金额: $ 2.04万
• 依托单位: Dalhousie University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2016
• 资助国家: 加拿大
• 起止时间: 2016-01-01 至 2017-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=610853
• 关键词: Graphs; Games

Playing games is one of the oldest human intellectual activities but is only within the last 100 years that mathematics has offered any real insights. Most of mathematics deals with `nature' or it describes ongoing situations. The mathematics of games has to take in to account an intelligent opponent. For example, consider the problems of capturing an intruder who is fleeing pursuers in a system of passageways. If the intruder is much faster than the pursuers this can be used as a model for decontaminating the passageways from chemical or biological spills. The worst–case scenario is that the contaminant/intruder is an intelligent adversary! The main goal is to identify good strategies that humans can understand and implement. There has been great success in the game theory originating in the fields of economics, biology and psychology where there are many players, simultaneous moves and hidden information. This has been useful in pure strategy games such as Chess, Checkers and Hex. Only in the last 40 years has the foundations of a mathematical theory for “last-player-to-move-wins” games (e.g., Chess, Checkers and Go) been laid. In these cases, even identifying an `infinitesimal’ (i.e. a very, very small edge) in a game can gain a move that could earn extra money for professional players. This research will identify and exploit the hidden structures in these games to obtain good strategies. This research will also extend the techniques from both the last-player-to-move and economic game theories to consider pure strategy, scoring games (e.g., Dots-and-Boxes and Reversi).

玩游戏是人类最古老的智力活动之一，但直到最近 100 年，数学才提供了真正的见解。大多数数学都涉及“自然”或描述正在发生的情况。游戏的数学必须考虑到聪明的对手。例如，考虑捕获在通道系统中逃离追捕者的入侵者的问题。如果入侵者比追赶者快得多，则可以将其用作净化通道免受化学或生物泄漏污染的模型。最坏的情况是污染物/入侵者是一个聪明的对手！主要目标是确定人类可以理解和实施的良好策略。起源于经济学、生物学和心理学领域的博弈论已经取得了巨大的成功，这些领域有许多参与者、同时行动和隐藏信息。这在国际象棋、西洋跳棋和十六进制等纯策略游戏中非常有用。直到最近 40 年，“最后走棋者获胜”游戏（例如国际象棋、西洋跳棋和围棋）的数学理论基础才奠定了基础。在这些情况下，即使识别出游戏中的“无穷小”（即非常非常小的优势）也可以获得可以为职业玩家赚取额外收入的举动。这项研究将识别并利用这些游戏中的隐藏结构来获得良好的策略。这项研究还将扩展最后玩家和经济博弈论的技术，以考虑纯策略、计分游戏（例如点棋和黑白棋）。