查看: 4944|回复: 4

[教程] 【AI2+AI】利用马尔可夫矩阵制作“石头剪刀布”APP

【AI2+AI】石头剪刀布

难度： 高级
课程类型： 教程
学科： 计算机科学
年级水平： 9~12年级

教程链接： 石头剪刀布教程
本作品来自：Youth Mobile Power

如今人工智能和机器学习全都风靡一时，但你是不是很疑惑，在现实世界中究竟有没有可能教一台机器学习某种东西，然后使其真正具有人工智能？在这个项目中，使用最简单的儿童游戏：剪刀石头布。你面临的挑战是创建一个程序，让机器来观察和了解用户的游戏选择，然后很快具有足够的智能在游戏中反复击败用户。难以置信？让我们现在开始准备给自己一个惊喜吧。

1. 项目简介

在本项目中，你会一览如何对机器进行编程，让它从经验中学习并做出展示智能的“明智”决策。您将在移动设备上实现“石头剪刀布”游戏，用户可以在其中与机器进行游戏。机器将跟踪用户的选择，如果在用户做出的选择顺序中出现了某种模式，机器将运用此知识来击败用户。

这是一个双人游戏，每个玩家同时用手势显示他们的选择，如下图所示。一轮比赛的赢家是由以下规则决定的:

石头击败剪刀
剪刀击败布
布击败石头

2. 用户界面

下面是用户界面(UI)的样子。第一行显示分数，分数下面有三个按钮让用户选择:石头、布、剪刀。再下面是用户和电脑的选择，分别以文字和图片的形式显示。接下来是一个标签，显示一轮比赛的获胜者。最后一部分展示了“马尔可夫转移矩阵”，以俄罗斯数学家Andrey Markov的名字命名，他最著名的是在概率过程方面的开创性工作。此处无需考虑这个矩阵。在本教程的后面，会学习 3x3 组数字背后的简单思想。请注意，矩阵中行的着色与石头、布和剪刀的按钮的颜色一致。

3. 组件的层次结构

UI已经创建好了。你可以在UI组件下面看到它们在组件层次结构中的对应位置。研究此图和命名方案，以便能够按照本教程的其余部分为组件提供功能。

4. 使用马尔可夫过程的机器学习

以下是如何赋予机器根据经验来学习的能力的基本思想。机器将跟踪用户做出的顺序选择，并连续记录用户选择的频率。保存这些信息的矩阵称为“马尔可夫转移矩阵”。

矩阵的行表示用户前一步的选择，矩形的列表示用户下一步的选择。这些单元格包含了一个特定序列连续选择的频度信息。如上面的矩阵所示，用户在上一次出石头后接下来继续出石头有7次，上一次出石头接下来出布有13次，上一次出布接下来出剪刀一共有11次，上一次出剪刀接下来也出一共有3次，依此类推。

5. 使用马尔可夫过程的机器学习

下图中高亮的第二行(红色)显示了用户出布后出石头、剪刀及布的次数(分别是2、4、11)。

下图中高亮的第二列(绿色)显示了用户出布之前出石头、剪刀及布的次数(分别是13、4、8)。

下面矩阵中橙色单元格显示了第二行与第二列的交点，橙色单元格中的数字4是用户前后两次都出布的次数。

6. 建立并递增马尔可夫矩阵

在博弈开始时，马尔可夫矩阵的每个项都是零。

假设用户先出石头，然后再出布(即连续的选择序列是石头、布)。然后，需要将第一行(石头)和第二列(布)中的单元格从0增加到1，如图所示。

假设用户用剪刀跟随其上一个选择布(即选择的顺序是石头、布、剪刀)，那么第二行(布)第三列(剪刀)的单元格需要增加，如图所示。

你可以把这个矩阵看作是用户对游戏选择的记录:

用户选择顺序:

石头、剪子、布
第一组前两个连续选择:

（石头、布），剪刀
然后分组第二个连续选择:

石头，（布，剪刀）

7. 用马尔可夫矩阵练习

假设游戏继续进行，在某一时刻你会得到下面的矩阵来记录连续的用户移动。

接下来假如用户在最后一次布上出了另一次布。如何增加这个矩阵的适当条目?

检查你的解决方案
你可以将第二行(布)第二列(布)的单元格从4增加到5。

正如所看到的，马尔可夫矩阵只是用户选择频率的记录。

假设游戏刚开始时矩阵如下:

假设用户做出如下一系列选择:
石头，剪刀，剪刀，布

游戏此时的马尔可夫矩阵会是什么样子？

提示：

（石头，剪刀），剪刀，布
石头，（剪刀，剪刀），布
石头，剪刀，（剪刀，布）

解决方案：

首先将石头与剪刀相交的单元格，即第一行第三列增加1。
然后将剪刀与剪刀相交的单元格，即第三行第三列增加1。
最后将剪刀与布相交的单元格，即第三行第二列增加1。

得到：

可夫矩阵的聪明选择">8. 使用马尔可夫矩阵的聪明选择

现在你已经了解了应用程序将如何跟踪用户的选择，请考虑以下方案：应用程序如何“智能地”决定自己的下一个选择。假设这是博弈中某个时刻的马尔可夫矩阵：

用户最后出的是剪刀。根据“历史”记录，机器知道剪刀后有15次出石头，8次出布，只有3次出剪刀。所以用户最有可能的是出石头。那机器的聪明之处在什么地方呢？要击败石头机器就会出……布呀！！哈哈!

这些例子可以让你了解机器是如何跟踪用户的连续选择，然后基于现有的模式，做出最有可能击败用户的“知情”决策。

9. 逻辑设计

现在来为用户界面(UI)提供功能并赋予机器智能，切换到逻辑设计。

10. 初始化

1) 创建一个名为choices的列表变量，保存可能的选择（ROCK, PAPER, SCISSORS），先将它初始化为一个空列表。

2) 创建一个名为beatingChoices的列表变量，保存对应的击败选择（PAPER, SCISSORS, ROCK），将其初始化为一个空列表。如此的顺序是因为：布击败石头，剪刀击败布，石击败剪刀。

3) 创建变量ROCK、PAPER和SCISSORS，并将它们分别初始化为数值1、2和3。将数字分配给选择可以方便对列表进行索引，并在每一轮游戏结束时更新马尔可夫矩阵。

解决方案：

4) 创建一个名为choicesInWords的变量，并初始化为包含项目为"ROCK", "PAPER" 和 "SCISSORS"的列表。注意,"ROCK"是一个字符串，而ROCK是一个变量，保存数值1。其他选择也类似。

5) 创建一个名为buttonChoices并初始化的变量保存的列表按钮组件，用户可以按下来给出自己的选择：RockButton, PaperButton 和 ScissorsButton。

解决方案：

6) 创建一个名为imageChoices的变量并初始化列表为："rock.png", "paper.png", "scissors.png"。

7) 创建一个名为MarkovTransitionMatrix的变量，并将其初始化为一个空列表。稍后你将创建一个过程，使该变量包含列表的列表。

8) 创建两个变量lastUserChoice和currentUserChoice，它们将跟踪用户最后两个连续的选择，并将它们初始化为零。

9) 创建一个名为currentComputerChoice的变量，它将跟踪电脑当前所做的选择并将其初始化为零。

解决方案：

11. 矩阵过程

创建两个无返回值的过程用于马尔可夫矩阵:

要创建一个没有返回值的过程，请选择左边的：

创建一个名为 initializeMarkovMatrix 的过程，并让它将变量MarkovTransitionMatrix设置为一个包含三个列表的列表，每个列表包含三个0作为元素。它等价于将 3X3 马尔可夫矩阵的元素初始化为零。

提示：

创建一个名为 printMatrix 的过程，它把MarkovTransitionMatrix的每一行分别写入标签 MatrixRow1、MatrixRow2、MatrixRow3。

注意，当列表打印标签时，MIT App Inventor会自动添加左右括号(即 "(" 和 ")" 。

提示：

解决方案：

12. 屏幕初始化

当屏幕初始化时：

调用过程 initializeMarkovMatrix;
设置变量choices 为包含变量ROCK, PAPER 和 SCISSORS的列表(按此顺序)。(记住，这些变量的值分别为1、2和3);
设置变量beatingChoices为包含变量PAPER, SCISSORS 和 ROCK的列表(按此顺序);

将变量 lastUserChoice设置为变量 ROCK。注意，开始的选择可以是任意的，用户做出第一个选择后立即构建马尔克夫矩阵，而不需要等待两轮，这会导致稍微复杂一点的编程代码;

尝试自己编写代码。如果卡住了，可以查看提示：

解决方案：

注意：此处比较微妙，如果你想知道为什么在一开始时不直接初始化列表变量choices和beatingChoices为变量ROCK, PAPER 和 SCISSORS，这是因为变量ROCK, PAPER 和 SCISSORS在被其它变量使用之间必须先初始化。

13. 折叠代码块

在这个项目中要编写相当多的代码，可以单击鼠标右键选择折叠代码块以获得更多的工作空间和更好地组织代码，如下所示:

14. 重置按钮

当点击ResetButton时：

调用过程 initializeMarkovMatrix;
调用过程 printMatrix 显示初始化为零的3X3矩阵项;
设置用户和电脑分数为零;
将赢家 announcement 标签、用户和电脑announcement标签重置为“NONE”;
设置变量 lastUserChoice 为变量 ROCK，和初始化一样;
设置变量currentUserChoice为0，和初始化一样。

尝试自己编写代码。如果卡住了，可以查看提示：

解决方案：

15. randomChoice 和 smartChoice

创建两个有返回值的过程，先将它们留空，不写任何代码。第一个过程,randomChoice，会让电脑随机选择 石头，布 或剪刀 (在游戏开始时)，第二个过程 smartChoice，将在研究马尔克夫矩阵后做出“知情”选择。我们在后面填充这些过程的代码。

要创建具有返回值的过程，请选择右侧：

16. Update 过程

创建两个没有返回值的过程，先将它们留空，暂时不添加任何代码。第一个过程，updateWinnerScore，将增加一局游戏获胜者分数。第二个过程，updateMatrix，将在每一轮游戏结束时更新马尔可夫矩阵。

17. 用户选择按钮 Choice Buttons

现在解决单击 RockButton, PaperButton 和 ScissorsButton 按钮事件。因为它们都以相同的方式运行，所以使用App Inventor的任意组件特性是必要的。

当用户点击任意按钮时：

提示：

你已经解决了单击 ResetButton 按钮事件，所以只需处理 尚未解决的按钮;
如果变量currentUserChoice的值是0（这意味着游戏开始了）
- 设置变量 currentComputerChoice 为过程 randomChoice的返回值;
- 否则设置变量 currentComputerChoice 为过程 smartChoice的返回值；
设置 ComputerChoiceImage 图片属性和 ComputerChoiceLabel 文字属性，使用变量 currentComputerChoice 分别作为 imageChoices 和 choicesinWords 的索引;
根据用户按下的按钮设置 currentUserChoice 变量。我们现在只在电脑做出选择之后才设置这个变量，因为电脑不能根据用户刚才的选择做出决定 —— 这是作弊 —— 只基于用户以往的选择来做决定。
设置 UserChoiceImage 的图片属性和 UserChoiceLabel 的文字属性，使用 currentComputerChoice 分别作为 imageChoices 和 choicesinWords 的索引;
调用过程(没有返回值) updateWinnerScore 来增加给定一轮比赛的获胜者的分数。
调用过程(没有返回值) updateMatrix 来更新马尔可夫矩阵。
最后将变量 lastUserChoice 设置为 currentUserChoice，以便为下一轮游戏做好准备。

尝试自己编写代码。如果卡住了，可以查看提示：

提示：

解决方案：

18. randomChoice

现在，为上面创建的过程填写代码。
使用返回值完成过程 randomChoice ：

让程序从选择列表中返回一个随机选择的项目（包含ROCK, PAPER, SCISSORS）

尝试自己编写代码。如果卡住了，可以查看提示：

解决方案：

19. smartChoice

使用返回值完成这程 smartChoice ：

创建另一个返回值在 smartChoice 过程中调用的过程，并将其命名为 findMostLikelyNextUserChoice，但暂时不带代码，将其留空稍后填充。

该过程根据电脑对马尔可夫矩阵的评估返回用户最可能做出的选择，马尔可夫矩阵跟踪用户之前连续选择序列的历史数据。
让 smartChoice 过程返回beatingChoices列表中的元素，使用 findMostLikelyNextUserChoice 返回的值作为列表的索引。

尝试自己编写代码。如果卡住了，可以查看提示：

提示：

解决方案：

20. 更新分数

如下完成步骤 updateWinnerScore：

如果电脑的选择击败了用户的选择，增加电脑的分数，宣布电脑获胜;
否则，如果用户的选择击败了电脑的选择，增加用户的分数，宣布用户获胜;
其他情况(即双方都没有击败对方)，没有分数需要增加，并宣布无人获胜。

尝试自己编写代码。如果卡住了，可以查看提示：

提示：

解决方案：

21. 更新马尔可夫矩阵

根据下面的要求完成过程 updateMatrix ：

根据lastUserChoice和currentUserChoice作为行和列，将适当的马尔可夫矩阵单元格增加1。
调用过程 printMatrix 确保矩阵更新显示在应用程序中.

尝试自己编写代码。如果卡住了，可以查看提示：

提示：

解决方案：

22. 查找最有可能的下一个用户选择

最后完成过程 findMostLikelyNextUserChoice，它的返回值用于在 smartChoice过程中的beatingChoices的索引。

注意,这个过程必须返回一个值即电脑估计最有可能的用户选择(ROCK, PAPER, SCISSORS变量的值分别1、2、3)，确保选择了返回结果的适当类型的过程块。

注意用户最后一次的选择(ROCK, PAPER, SCISSORS变量的值分别1、2、3)，并将其设置为行索引,你需要检查马尔可夫矩阵适当的行来决定哪一列存储了频率最高的元素。例如，如果用户最后一次出的是PAPER布，则检查第二行(红色的)，返回的是SCISSORS 剪刀(最大值11的列索引为3)作为用户下一步最有可能的选择。

23. 查找一行中的最大值

为了简化过程 findMostLikelyNextUserChoice，首先创建一个简单的助手过程 maxInRow，用于查找马尔可夫矩阵给定行中的最大元素。

尝试自己编写代码。如果卡住了，可以查看提示：

提示：

从Math块中获取数学函数 min，并将其切换为 max。
呼出设置齿轮给函数设置三个插槽，用于比较马尔可夫矩阵中给定行中的三个元素。
创建具有返回值的过程 maxInRow，并使用设置齿轮为其提供一个输入参数行。
使用 max函数让过程 maxInRow返回给定行的最大元素。请记住，马尔可夫矩阵中的一行是一个列表，因此可以使用列表操作访问一行中的单个元素。

解决方案：

24. 查找最有可能的下一个用户选择

完成过程(带回值) findMostLikelyNextUserChoice：

查找由 lastUserChoice 确定的马尔可夫矩阵的行;
使用过程 maxInRow查找该行中的最大值，并返回该行中该值的索引(1、2或3)。

尝试自己编写代码。如果卡住了，可以查看提示：

提示：

解决方案：

25. 测试应用程序

现在彻底测试应用程序，以确保:

用户可以点击按钮来做选择;
每次用户点击时，马尔可夫矩阵都会正确更新，连续记录用户选择的频率;
机器可以对第一轮随机做出选择，然后根据马尔可夫矩阵中可用的信息进行引导，做出明智的选择;
用户和电脑分数更新正确;
如果用户总是做相同的选择，机器应适当回应，像石头, 石头, 石头, ....
- 用户重复选择石头，机器很快学会使用重复的布来应对?
- 当用户只选择布或只选择剪刀时呢？

26. 进一步测试应用程序

尝试测试机器对用户选择的更复杂模式的响应:
- 石头，布，石头，布，石头，布........
- 布，剪刀，布，剪刀，布，剪刀.......
- 石头，布，剪刀，石头，布，剪刀，石头，布，剪刀 ....
机器是否学会了这些模式并学会了如何打败用户?
试着击败这台机器。在30轮的游戏中，你能做的最好的是什么?
你能用机器自己的策略打败它吗？也就是说，你能根据马尔可夫矩阵的当前状态预测机器将如何试图击败你并利用这些知识在那一轮中击败机器吗？例如，如果这是在游戏中某一时候的马尔可夫矩阵，你最后一次的选择是石头，

机器接下来会预测你会选择布(如教程最前面的列表，第一行的最大值是13，即布)，从而给出剪刀来打败你。然而你已经掌握了技巧，现在使用机器自己的策略给出选择石头来让机器“惊喜”一下。
- 运用这个策略你能把游戏玩多远?
- 你总能通过观察马尔可夫矩阵打败机器吗?
- 如果你用这种方式长时间玩这个游戏，你希望马尔可夫矩阵会发生什么?你能证实你的假设吗?

恭喜你!庆祝一下吧，因为你刚刚创建了第一个机器学习和人工智能的示例!

27. 扩展你的应用程序

进一步的探索

创建一个按钮（替代标签MarkovLabel)来显示和隐藏Markov矩阵信息，这样机器的决策过程就可以对用户隐藏了。
你还能想到其他的机器学习方案吗?你将如何实施这些想法?
你在这个项目中实现的机器学习算法是一个“古典”的人工智能算法的例子（“古典”的意思是“不现代”）。它是特定领域（即只适用于石头剪刀布游戏)实现一个特定策略的游戏。做一些关于神经网络的研究，学习机器学习的更现代的方法。特别注意机器学习的“监督”和“非监督”方法。
观看电影AlphaGo，这部电影记录了机器学习算法AlphaGo的惊人故事，该算法由谷歌的DeepMind团队开发，在2016年成功击败了世界围棋冠军李世石。
对AlphaGo Zero做一些研究。它与AlphaGo有什么不同和优越之处？