Games and Graphs

玩游戏是人类最古老的智力活动之一，但直到最近100年，数学才提供了真正的见解。大多数数学都是关于“自然”的，或者说它描述的是正在进行的情况。游戏的数学必须考虑到一个聪明的对手。例如，考虑在通道系统中捕获正在逃离追踪者的入侵者的问题。如果入侵者比追赶者快得多，这可以作为清除通道中化学或生物泄漏的模型。最糟糕的情况是，污染物/入侵者是一个聪明的对手！第二个重要的例子是在投票前发挥影响力。主要目标是确定人类可以理解和实施的良好战略。起源于经济学、生物学和心理学领域的博弈论在参与者多、同时行动和隐藏信息等领域取得了巨大的成功。只有在过去的50年里，才奠定了“最后一步获胜”游戏(例如国际象棋、跳棋、围棋和十六进制)的数学理论的基础。一个重要的结果是，一个游戏可以被一个等价的、唯一的、最简单的游戏所取代，从而降低了确定好的策略的复杂性。即使在一场比赛中识别出一个“无穷小”(即一个非常、非常小的优势)也可以获得一步棋，这可能会为职业球员赚取额外的钱，或者在势均力敌的竞争中扭转选举局面。在过去的5年里，这一理论已经显著扩展，涵盖了获胜者得分更高的领域。这项拟议的研究将识别和利用这类游戏中的隐藏结构，以获得良好的策略。这项研究还将把这一理论扩展到玩家同时移动，但其中一名玩家对对手的移动拥有先进知识的游戏类别。这就是“咀嚼机器人”模型，其中“机器人”的速度足够快，能够识别“人类”的动作并做出反应。这些游戏是确定性的，不涉及任何概率。

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! A second important example is playing for influence before a vote. 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. Only in the last 50 years has the foundations of a mathematical theory for "last-player-to-move-wins" games (e.g., Chess, Checkers, Go, and Hex) been laid. An important result is that a game can be replaced by an equivalent, unique simplest game thereby reducing the complexity in identifying good strategies. 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 or turn an election in tight races. In the last 5 years, the theory has been extended significantly to cover where the winner has the greater score. The proposed research will identify and exploit the hidden structures in these classes of games to obtain good strategies. This research will also extend the theory to classes of games where the players move simultaneously but where one player has advanced knowledge of the opponent's move. This is the `Cheating Robot' model where the `robot' is fast enough to recognize what move the `human' is making and respond. The games are deterministic and do not involve any probabilities.