奖励学习
中世纪流传下来这样一个故事：一位统治者为了感谢发明国际象棋的人，想要奖励他一块麦田。发明人请求在棋盘的第一格放一粒麦子，第二格放两粒，第三格放四粒，依次类推，剩余每格都放前一格两倍的麦子，直到放满64格的棋盘。统治者觉得这个请求并不过分，就同意了。但实际上，要满足这一请求，统治者不仅要拿出他王国里所有的麦子，还要加上全世界未来几百年的麦子产量才能凑够，因为最后一格要放的麦粒数目达到了2<sup>64</sup>（大约是10<sup>19</sup>）。<sup>[1]</sup> 这被称为“指数增长”。在国际象棋和围棋游戏中，棋盘不同布局状态的增长速度比这个故事里麦子数量增加的速度还要快得多。在国际象棋中，每一步棋平均都有35种摆法，而在围棋中，分支系数是250，这就使得围棋的指数增长速度要快得多。
机器如何学会下棋
游戏的好处就在于，其规则都有明确的定义，玩家对棋盘十分熟悉，决策也不像现实世界中那样复杂，但又不失挑战性。1959年，在商业数字计算机发展的早期，IBM的机器学习先驱亚瑟·塞缪尔（Arthur Samuel）编写了一个擅长玩国际跳棋的程序，在宣布其诞生的当天，IBM的股票就获得了巨大的收益。西洋跳棋则相对容易。塞缪尔的程序利用了代价函数来评估对局中不同布阵的优劣情况，这一点跟以前的游戏程序很相似。该程序是在IBM第一款真空管商用计算机
10