计算博弈理论课程详细信息

课程号 04833640 学分 2
英文名称 Computational Game Theory
先修课程 Data Structures and Algorithms, Discrete Mathematics, Python language fluency
中文简介 本课程将探讨计算博弈理论的丰富内容,即利用计算机的强力计算性能来解决抽象策略游戏。课程融合了人工智能的思想,组合学、人机界面设计、并行与分布式计算、软件工程等方面的理论知识。学生将学习抽象策略游戏的数学基础和组合游戏的基础理论,结合讲授包括超现实数字在内的组合数学游戏的特殊案例。他们将学习如何计算一个博弈树的规模上限,将编写程序实现无环路的游戏一个简单的递归求解,以及逆行求解处理游戏,进而通过”Apache Spark“API将把他们的逆向求解器延伸到在分布式环境中使用。作为课程的最终项目,学生们将以团队合作的形式选择和编写一个抽象策略游戏,求解该游戏,编写一个图形界面,以保证系统的完美运作和性能分析工作。
英文简介 This course will explore the fertile ground of computational game theory, i.e., the use of computers to solve abstract strategy games via computational brute force. We blend ideas from artificial intelligence, combinatorics, human-computer interface design, parallel and distributed computing and software engineering. Students will learn the mathematical foundations of abstract strategy games and the special case of combinatorial games, including surreal numbers. They will learn how to calculate the upper bounds of the size of a game tree, will author a simple recursive solver for loop-free games, and a retrograde solver to handle loopy games. They will extend their retrograde solver to work in a distributed environment using the Apache Spark? API. For their final project, students will work in teams to choose and encode an abstract strategy game, solve it, author a graphical interface that will allow the system to play perfectly, and use it to perform analysis.
开课院系 信息科学技术学院
通选课领域  
是否属于艺术与美育
平台课性质  
平台课类型  
授课语言 英文
教材 Checkers Is Solved,Jonathan Schaeffer, Neil Burch et al.,Science,2007;
R.U.Gasser. Solving Nine Men's Morris,R.J.Nowakowski (Ed.), Games of No Chance, MSRI Publications,Cambridge University Press,1996;
Winning Ways for Your Mathematical Plays: Volume 1 (2nd Edition),Elwyn R. Berlekamp, John H. Conway, Richard K. Gu,A K Peters/CRC Pres,2001,
参考书
教学大纲
Session 1: Introduction to Computational Game Theory Date:7/31
【Description of the Session】(purpose, requirements, class and presentations scheduling, etc.) After group introductions, we will provide an overview of the field, motivation and basics of computational game theory. We will also explore many popular abstract strategy games and form classifications.

Session 2:Determining the Size of Games Date:8/01
【Description of the Session】(purpose, requirements, class and presentations scheduling, etc.) Using principles from Combinatorics, students will learn how to calculate bounds on the number of positions of games.

Session 3:Solvers Date:8/02
【Description of the Session】(purpose, requirements, class and presentations scheduling, etc.) Starting from a simple recursive descent solver, we will understand its limitations, and will first increase its speed significantly through memoization, and then explore the retrograde algorithm to handle loopy games, as well as explore an optimized iterative solver for tier games.

Session 4:Distributed Solvers Date:8/03
【Description of the Session】(purpose, requirements, class and presentations scheduling, etc.) Students will be introduced to the Apache Spark system and explore how to use it to speed up an iterative solver.

Session 5: Introduction to Combinatorial Game Theory Date:8/07
【Description of the Session】(purpose, requirements, class and presentations scheduling, etc.)  Starting with Nim and moving quickly through to Kayles and Domineering, students will learn the fundamentals of combinatorial game theory.

Session 6:Building a Graphical User Interface Date:8/08
【Description of the Session】(purpose, requirements, class and presentations scheduling, etc.) Students will be introduced to the principles behind building a graphical user interface for their game.

Session 7:Group Project Work Session Date:8/09
【Description of the Session】(purpose, requirements, class and presentations scheduling, etc.) This session is provided to allow the student groups to finish up their projects with instructor guidance, and do analysis of the games.

Session 8:Final Project Demonstrations Date:8/10
【Description of the Session】(purpose, requirements, class and presentations scheduling, etc.) This session is devoted to demonstrations of the student final projects and submissions of their final report.
Reading, Assignment and Programming
Attendance, Participation and Reading: 20%
Programming Project: 50%
Final Report: 30%
教学评估 陈毅松:
学年度学期:17-18-3,课程班:计算博弈理论1,课程推荐得分:4.38,教师推荐得分:4.38,课程得分分数段:95-100;