C++ 中的 Matchbox 可学习的井字棋引擎 (MENACE)

• 下载演示 - 12.2 KB
• 下载源代码 - 8.5 KB

引言

最近我偶然发现了 M. Gardner 的《Scientific American 的新数学趣闻》（纽约，Simon and Schuster，1966），并阅读了关于用火柴盒制作的自学井字棋机器的文章。我觉得它很有趣，值得用 C++ 来实现。

最早的自学机器之一是 IBM 704。该程序由 A. Samuel 于 1959 年设计，允许机器玩跳棋，并通过之前玩过的游戏的经验来改进游戏策略。起初 Samuel 轻松赢得了比赛，但随着机器学会了如何玩，它开始在每一场比赛中击败他。

为了进行自学机器的实验，甚至不需要计算机，只需要大量的空火柴盒和彩色珠子。设计简单而强大的自学机器的绝妙主意属于 D. Michie。在《试错法》一文（Penguin Science Survey, 2, 1961）中，他解释了一种可以由 300 个火柴盒组装而成的井字棋自学机器。它被称为 MENACE（Matchbox Educable Noughts And Crosses Engine）。它的工作原理非常简单。每个火柴盒上都画着游戏中可能遇到的局面。机器进行第一步，因此只有奇数步的局面可以画在火柴盒上。每个火柴盒内都放着彩色珠子，每种颜色代表一个可能的走法。火柴盒内部还粘有硬纸板角，摇动时，一个珠子会滚到它下面。对于第一步的火柴盒，每种颜色的珠子有 4 颗；对于第三步，每种颜色的珠子有 3 颗；以此类推，直到第七步的火柴盒，每种走法都只有一种颜色的珠子。要确定下一步，只需摇动火柴盒，即可获得滚到硬纸板角下的珠子的颜色。打开的火柴盒会一直保持打开状态直到游戏结束。如果机器赢得了比赛，就会通过在滚到硬纸板角下的珠子的颜色中添加 3 颗相同颜色的珠子来奖励它。如果平局，则只添加一颗相应的彩色珠子；如果机器输了比赛，就会通过从每个打开的火柴盒的硬纸板角中取出珠子来惩罚它。机器玩的比赛越多，就越倾向于走能带来胜利的路线，并避开会导致失败的路线。尽管与 IBM 704 相比，这台机器无法分析已玩过的游戏并从经验中设计新颖的策略。Michie 和他的 MENACE 进行了第一次比赛，共进行了 220 场比赛。起初 Michie 总是因为输掉比赛而惩罚他的机器，但在第 17 场比赛后，机器开始将第一步棋下到角落方块，并在第 20 场比赛后，以平局结束所有比赛。比赛以 Michie 的惨败告终，他在 10 场比赛中输了 8 场。MENACE 成为了井字棋特级大师。

背景

你应该熟悉井字棋游戏。

Using the Code

为了避免你遇到火柴盒的麻烦，我用 C++ 编写了同样的程序。要开始与计算机对战，我提供了 player1.dat 文件，这是一个总是先走的训练好的玩家。运行 play.bat 来与它对战。要走你的那一步，输入空方块的 `y` 和 `x` 坐标。要走一步到 [0, 0]，输入 00 然后回车；要走一步到 [1, 0]，输入 10 然后回车，以此类推。只需输入一个包含 `y` 坐标作为第一个字母，`x` 坐标作为第二个字母的字符串。

井字棋的对局可能看起来像这样

    012

 0  ---
 1  ---
 2  ---

 0.000000 0.000000 0.000000 0.000000 1.000000 0.000000 0.000000 0.000000 0.000000

    012

 0  ---
 1  -x-
 2  ---

 human move o enter (y,x) coord or '--' to quit: 20
 
    012

 0  ---
 1  -x-
 2  -o-

 0.000000 0.000000 0.000000 0.000000 0.000000 1.000000 0.000000

    012

 0  ---
 1  -x-
 2  xo-

 human move o enter (y,x) coord or '--' to quit: 00
 
    012

 0  o--
 1  -x-
 2  xo-

 0.000000 1.000000 0.000000 0.000000 0.000000

    012

 0  o-X
 1  -X-
 2  Xo-

 player No 1 won
 wins: 5868
 loses: 214
 draws: 10934

finished.

字符串 0.0 和 1.0 是用于调试的，代表计算机走特定步的概率。正如你所见，它学会了总是将第一步棋下到中心方块，这是一种必胜策略。

命令行参数的帮助如下所示

argv[1] = 'uc', 'cu', 'cc', 'uu'
 'uc' - user vs. computer
 'cu' - computer vs. user
 'cc' - computer vs. computer
 'uu' - user vs. user
argv[2] = number of plays
argv[3] = 'player1.dat'
argv[4] = 'player2.dat'

你可以选择让计算机先走 (`cu` 或 `uc`)，或者自己先走。在 `cc` 模式下，计算机与自己对弈。这可以帮助你节省自己训练它玩游戏的时间。只需这样运行：

>ccross.exe cc 1000 player1_name player2_name

它会与自己对弈数千次，如果不存在则创建 `player1_name` 和 `player2_name` 文件，否则从文件中读取。要提高性能，请尝试将控制台输出重定向到文件。

当计算机玩家遇到新的棋盘局面时，它会为所有空方块的走法分配相等的概率。如果它输了比赛，它会降低它所走的棋盘局面的走法概率；否则，它会增加概率。如果平局，概率则不改变。它会将所有下过的棋盘局面和走法的概率，连同胜、负、平局的计数一起保存在文件中。