学习 Connect Four
4.74/5 (19投票s)
2004年7月23日
18分钟阅读
190641
5488
一个从经验中学习的连连看游戏。
引言
首先，从一开始就应该指出，这是一个连连看游戏的事实，对于这个项目来说几乎是偶然的。这个项目的创建背后有两个截然不同的原因，第一个是我想要一个比我之前应用程序中使用的更好的棋盘控制，并且我需要一个框架来开发它，而无需其他项目因开发棋盘的过程而偏离轨道。此外，我需要能够开发棋盘控制，以便在不同的应用程序中使用它，因此我试图避免将其与任何特定项目联系过紧的危险。我目前的个人感觉是，棋盘控制仍然需要另一个项目才能达到我想要的高度，但它在这里完成了所需的工作。
项目的第二个原因是关于我一直在阅读的关于人工智能和学习的想法。我在某个地方读到的论点大致是，如果我们想开发出智能的计算机软件，那么程序必须能够获取人类的全部知识，才能理解任何事情。这在很多层面上都让我觉得不对，以至于很难知道从哪里开始。首先，尽管地球上没有人能够获取人类的全部知识，或者即使他们 somehow 能够将它注入他们的大脑而不至于精神崩溃，他们也无法记住其中的一小部分。然后是启发式方法和在信息不完整的情况下做决策的问题，更不用说考虑个人和政治偏见了。
但这会分散我对这个项目的注意力，所以让我们回到它。一个计算机拥有完全访问人类知识总和的想法所带来的问题是一回事，但姑且假设你编写了一个计算机程序，它是地球上最智能的软件。唯一的问题是它一无所知。你如何首先将人类的全部知识输入计算机？暂时忘掉人类的全部知识，你如何将任何信息输入程序？最明显的答案是某种数据库，而数据库的唯一问题是它们最初是空的。数据库也用于特定目的，包含与手头的任务或业务相关的数据。即使是设想一个可以用于所有事情的通用数据库，也将是一项艰巨的任务。最后，我们到达了即使我们拥有这样一个数据库，我们仍然需要将信息输入其中，这把我带到了导致这个项目的思考主线。
鉴于我们拥有虚构的智能软件和虚构的无所不知的数据库模式来为它提供信息，谁将编写程序来填充数据库，或者坐下来输入信息？我可以向你保证，我不会。我通常觉得数据库编程很乏味，我最不感兴趣的事情就是一辈子都在输入数据库信息，因为即使我个人远远不能知道人类的全部知识，我可能也需要花我一生来输入我所知道的一小部分知识，并且是以程序能够有意义地提取信息的形式。这就引出了我的明显结论：如果一个软件要学习人类的全部知识，那么它就必须自己完成。
孩子可以自己学习，为什么软件不行？与其把信息数据库交给软件使用，不如开发一种让计算机能够自己学习的方法，而不是直接把信息丢给它，希望它知道如何处理。这很方便地将我们引向了模式。
记忆模式理论
万物皆有模式。你此刻所处的房间与你一生中曾经去过的所有其他房间都遵循完全相同的模式。问题是“你怎么知道你在房间里？”你当前环境的什么让你知道你在房间里，答案是你的环境的模式符合你对房间接受定义的标准。也就是说，它有入口，墙壁，通常是四面或更多，地板和某种屋顶。通常会有某种窗户，但这些不是必需的。当我们开始谈论房间的类型时，我们可以更深入地研究，但它们遵循相同的基本模式，并添加了额外的元素，如书架和书籍用于图书馆，炉灶用于厨房，或浴缸或淋浴器或两者都用于浴室。
那么问题是如何将模式的想法应用于软件可以使用的形式，以便它能够了解其环境，这又回到了连连看程序，因为棋子的形成代表了游戏的模式。如果你从非常基本的层面来思考，连连看游戏只是玩家响应以做出棋子的颜色模式的集合。某些模式在游戏中有特定含义，玩家根据这些模式做出决策，特别是如果他们之前看到过这些模式并且这些模式导致游戏被赢或输。
连连看游戏在至少三个层面进行。有记忆层面。“我以前见过这个模式吗？”这个层面玩家知道可能是威胁也可能不是。存在威胁层面，玩家识别出三个相同颜色的棋子模式，这可能导致玩家或其对手赢得游戏，还有一个安全层面，当前回合既不会赢得也不会输掉游戏。
学习 Connect Four
连连看游戏使用四种不同的模式类型来确定走法。这些是攻击性、防御性、警告性和战术性。
- 攻击性：- 攻击性模式是指软件知道或认为它可以走一步以赢得游戏。
- 防御性：- 防御性模式是指软件知道或认为需要走某一步才能避免输掉游戏。
- 警告：- 警告模式是指软件知道或认为棋盘上的特定模式可能导致对手玩家赢得游戏。
- 战术性：- 战术性模式是指软件知道或认为棋盘上的特定模式可能导致软件赢得游戏。
每次软件走一步时，它都会对棋盘进行快照。此时，棋子的颜色或属于哪个玩家并不重要。一旦确定了棋盘上的棋子，计算机就开始搜索棋子寻找模式，其中模式被定义为两个或多个相同颜色的棋子。当然，棋子的颜色决定了这组棋子最终被定义为哪种类型的模式，因此一组计算机颜色的两个或三个棋子将被定义为软件可以用来赢得游戏的攻击性模式。尽管如此，在这个阶段，代码只是关心确定任何颜色的有效模式。
代码找到模式的一个例子是
/// check top
///
patternSquareInfo = connectFourGame.GetSquareInfo(
GetIdentifierAbove( square.Identifier ) );
if( patternSquareInfo != null )
{
bool bTwoPieces = false;
bool bThreePieces = false;
if( patternSquareInfo.IsOccupied == true )
{
nextInfo = connectFourGame.GetSquareInfo(
GetIdentifierAbove( patternSquareInfo.SquareIdentifier ) );
if( nextInfo != null && nextInfo.IsOccupied == false )
{
/// allow this square
///
bTwoPieces = true;
}
else
{
if( nextInfo != null )
{
bTwoPieces = true;
bThreePieces = true;
}
}
}
if( bTwoPieces == true )
{
ConnectFourPiece abovePiece = new
ConnectFourPiece( false, patternSquareInfo.SquareIdentifier );
if( piece.IsPieceRed == patternSquareInfo.IsRed )
{
abovePiece.IsPieceRed = patternSquareInfo.IsRed;
abovePiece.Position = PIECEPOSITION.ABOVE;
abovePiece.Level = 1;
if( connectFourGame.PlayerIsRed == patternSquareInfo.IsRed )
abovePiece .IsEnemy = false;
else
abovePiece.IsEnemy = true;
pattern.AddGamePiece( abovePiece );
if( bThreePieces == false )
{
if( patternCollection.IsIn( pattern ) == false )
patternCollection.AddPattern( pattern );
}
}
}
if( bThreePieces == true )
{
patternSquareInfo = nextInfo;
nextInfo = connectFourGame.GetSquareInfo(
GetIdentifierAbove( patternSquareInfo.SquareIdentifier ) );
if( nextInfo != null && nextInfo.IsOccupied == false )
{
ConnectFourPiece abovePiece = new
ConnectFourPiece( false, patternSquareInfo.SquareIdentifier );
if( piece.IsPieceRed == patternSquareInfo.IsRed )
{
abovePiece.IsPieceRed = patternSquareInfo.IsRed;
abovePiece.Position = PIECEPOSITION.ABOVE;
abovePiece.Level = 2;
if( connectFourGame.PlayerIsRed == patternSquareInfo.IsRed )
abovePiece.IsEnemy = false;
else
abovePiece.IsEnemy = true;
pattern.AddGamePiece( abovePiece );
if( patternCollection.IsIn( pattern ) == false )
patternCollection.AddPattern( pattern );
}
}
}
pattern.Clear();
pattern.AddGamePiece( piece );
}
代码从包含在方块中的当前棋子信息开始，在代码示例中，它检查棋盘上方是否有棋子。如果有，它会检查更上面的方块，看它是否是一个有效的方块，并且它是否也包含一个棋子。如果原始棋子上面的方块有效，那么这就是一个两棋子模式，只要颜色匹配，棋子就会被存储，但除非上面的方块不等于 null，否则模式不会被添加到集合中。
如果它上面的方块有效，那么这就是一个三棋子模式，只要颜色相同，并且它上面的方块有效且未被占用，剩余的棋子就会被添加。这样做是因为如果模式包含三个棋子，那么添加到该模式的下一个棋子将是某人的获胜走法，如果无处可走，那么它就与模式无关。
我们现在处于这样的境地：我们有一个用于工作的棋盘快照，其中所有棋盘包含的模式都存储在 patternCollection 对象中，它只是一个连连看模式的集合。下一步是确定我们要如何处理这些模式。
以下代码是查找防御模式的代码片段。
for( int i=0; i<patternCollection.Count; i++ )
{
holdingPattern = patternCollection.GetPattern( i );
if( historicalPatternCollection.IsIn( holdingPattern ) == true )
{
holdingPattern =
( ConnectFourPattern )historicalPatternCollection.GetPattern(
holdingPattern );
if( holdingPattern.NumberOfTimesSeenInLosingGame > 0
&& IsValidPattern( holdingPattern ) == true )
{
holdingPattern.Weighting = nMemoryDefensiveWeight;
defensivePatterns.AddPattern( holdingPattern );
}
else
{
if( connectFourGame.GetSquareInfo(
holdingPattern.GetStartsWith() ).IsRed
!= connectFourGame.PlayerIsRed )
defensivePatterns.AddPattern( holdingPattern );
}
}
else /// determine if this is a defensive pattern
{
patternSquareInfo = connectFourGame.GetSquareInfo(
holdingPattern.GetStartsWith() );
/// if the pattern square colour is NOT the same as the player colour
/// it's a pattern that needs defending against
///
if( patternSquareInfo.IsRed != connectFourGame.PlayerIsRed )
{
leftSquareInfo = connectFourGame.GetSquareInfo(
GetIdentifierToLeft( patternSquareInfo.SquareIdentifier ) );
leftSquareNextInfo = connectFourGame.GetSquareInfo(
GetIdentifierToLeft(
GetIdentifierToLeft( patternSquareInfo.SquareIdentifier ) ) );
rightSquareInfo = connectFourGame.GetSquareInfo(
GetIdentifierToRight( patternSquareInfo.SquareIdentifier ) );
rightSquareNextInfo = connectFourGame.GetSquareInfo(
GetIdentifierToRight(
GetIdentifierToRight( patternSquareInfo.SquareIdentifier ) ) );
if( leftSquareNextInfo != null )
nextSquareInfo = connectFourGame.GetSquareInfo(
GetIdentifierToLeft( leftSquareNextInfo.SquareIdentifier ) );
else
nextSquareInfo = null;
if( leftSquareInfo != null && leftSquareNextInfo != null )
{
if( leftSquareInfo.IsOccupied == true
&& leftSquareInfo.IsRed != connectFourGame.PlayerIsRed )
{
if( leftSquareNextInfo.IsOccupied == false )
defensivePatterns.AddPattern( holdingPattern );
else
{
if( nextSquareInfo != null
&& nextSquareInfo.IsOccupied == false
&& leftSquareNextInfo.IsRed
!= connectFourGame.PlayerIsRed )
{
defensivePatterns.AddPattern( holdingPattern );
}
}
}
}
代码从循环遍历从快照收集的模式开始，然后检查该模式是否是历史模式。也就是说，代码是否在之前的游戏中遇到过该特定模式。这是通过代码在每场游戏结束时保存从棋盘上的最后一个快照收集的所有模式来确定的。如果该模式是之前见过的模式，并且曾是导致失败游戏的组成部分，那么该模式的权重将获得记忆防御权重。（游戏中权重的用法稍后讨论。）然后将该模式添加到防御模式列表中。但是，如果该模式以前见过，但不是导致失败游戏的组成部分，那么只要颜色标准匹配，该模式仍会被添加到防御模式列表中，但它不会获得任何特殊权重。
当模式以前未见过时，会产生很多代码，我们必须辛苦地找出它。这是通过获取我们要检查的轴线上的方块，然后测试在防御模式的情况下，轴线上的方块是否包含玩家的棋子，并且它们的排列方式可能导致他们赢得游戏。
当计算机每走一步时，所有模式类型都会重复此过程，以便计算机能够构建当前快照中模式的完整图景。一旦快照中的模式被处理完毕，计算机就会到达这段代码
if( aggressivePatterns.Count == 0 && defensivePatterns.Count == 0
&& warningPatterns.Count == 0 && tacticalPatterns.Count == 0 )
{
MakeRandomMove();
return;
}
这基本上意味着，如果当前快照中未找到任何模式，则随机走一步。但请注意，由于需要至少两个相邻的同色方块才能形成模式，因此这不仅仅在第一步时被调用。一旦我们有了单独的模式集合，我们就会进入处理模式函数，该函数用于处理所有四种模式集合。
Process Patterns 函数遍历集合中的模式，并尝试为单个模式分配权重，以确定对模式做出反应的重要性。
函数开始于
if( pattern.NumberOfTimesSeen > 1 || pattern.Weighting == nAggressiveWeight )
{
/// ensures that a pattern of three pieces will have a higher priority
/// than a pattern with two pieces
///
if( pattern.Count == 3 )
{
pattern.Weighting = patternWeight * 2;
/// A winning pattern can be ignored
/// if a defensive pattern from memory is used
/// and the winning pattern has not been seen before.
///
if( patternWeight == nAggressiveWeight )
pattern.Weighting += nMemoryAggressiveWeight;
}
else
pattern.Weighting = 0;
/// give added weight if pattern is part of an ending move
///
if( pattern.IsEndingPattern == true )
pattern.Weighting += 2;
if( pattern.ResponsePresent == true )
{
if( pattern.NumberOfTimesSeenInWinningGame
> pattern.NumberOfTimesSeenInLosingGame )
{
pattern.Weighting += pattern.NumberOfTimesSeenInWinningGame * 3;
bFindMove = false;
}
else
bFindMove = true;
}
/// try to increase the warning level in an attempt to detect
/// two way tricks
///
if( patternWeight == nWarningWeight
&& pattern.NumberOfTimesSeenInLosingGame
> pattern.NumberOfTimesSeenInWinningGame )
pattern.Weighting += pattern.NumberOfTimesSeenInLosingGame;
它首先检查模式是否出现过一次以上，除非它是攻击性模式，在这种情况下，它始终允许通过。这样做是为了减少程序错过它以前未见过的获胜走法的发生次数，因为没有人真的想玩一种感觉对手在放水来赢的游戏。然后它检查模式的计数是否为三。这样做是为了让包含三个棋子的模式比只有两个棋子的模式获得更高的权重，而之前见过的包含三个棋子的攻击性模式获得最高的评级。
然后我们检查该模式是否被识别为以前结束过连连看游戏的模式，如果已结束，则给予稍微增加的权重，然后再检查该模式是否已有先前游戏的编程响应。如果来自先前游戏的响应，并且该响应是获胜响应，则模式的权重会增加，因此我们认识到需要找到一个走法。
然后我们检查该模式是否为警告，并尝试增加防止双向诡计的几率。双向诡计是指对手有两个相邻的棋子，并且两侧的方块都是空白的，这意味着如果对手在两个棋子的一侧放置一个棋子，他们将赢得游戏，并且对此无能为力。完成后，函数会检查是否需要找到一个走法。如果需要，它会检查所有可用的选项并相应地分配权重。
当所有模式都处理完毕后，代码会提取权重最高的模式并尝试走棋，尽管此时，如果走棋不利于计算机，它仍然可以被阻止，因为它会给玩家一个获胜的机会。正是由于这些条件，计算机只会尝试几次走棋，然后决定随机走棋。
记住走法
游戏的历史模式在程序初始化时加载，并在每场游戏结束时保存。在每场游戏结束时，从最后一个快照收集的模式会与历史模式集合中的模式进行比较。如果模式存在，则更新它；如果不存在，则将其添加到集合中，然后将整个历史模式集合保存到磁盘。
这是保存的模式数据的示例
<ConnectFourPattern>
<BasicGamePatternSet>
<PatternID>0</PatternID>
<BasicGamePiece>
<PieceID>0</PieceID>
<IsStartForPattern>True</IsStartForPattern>
<Square>CF</Square>
<IsEnemy>False</IsEnemy>
<PiecePosition>START</PiecePosition>
<Level>0</Level>
</BasicGamePiece>
<BasicGamePiece>
<PieceID>1</PieceID>
<IsStartForPattern>False</IsStartForPattern>
<Square>DF</Square>
<IsEnemy>False</IsEnemy>
<PiecePosition>RIGHT</PiecePosition>
<Level>1</Level>
</BasicGamePiece>
<NumberOfTimesSeen>80</NumberOfTimesSeen>
<NumberOfTimesSeenInWinningGame>38</NumberOfTimesSeenInWinningGame>
<NumberOfTimesSeenInLosingGame>42</NumberOfTimesSeenInLosingGame>
<EndingPattern>False</EndingPattern>
<Weighting>103</Weighting>
<Response>
<ResponsePresent>0</ResponsePresent>
</Response>
</BasicGamePatternSet>
</ConnectFourPattern>
应该注意的是，模式和棋子的 ID 在当前程序中均未使用，并且可能在系列中的下一个程序中完全移除。
连连看中的权重
代码中包含许多预定义的权重常量，这些常量有助于代码准确地决定如何处理某个模式。这些是
const int nAggressiveWeight = 10;
const int nDefensiveWeight = 7;
const int nTacticalWeight = 3;
const int nWarningWeight = 5;
const int nMemoryAggressiveWeight = 105;
const int nMemoryDefensiveWeight = 104;
const int nMemoryTacticalWeight = 103;
const int nMemoryWarningWeight = 102;
这些权重分为两类：每种模式类型的标准权重，以及来自记忆的该类型的标准权重。这里的想法是，当从记忆中识别出模式时，它比程序尚未见过的模式更有可能被使用。当代码决定使用哪些模式时，它会分配初始权重。
holdingPattern = ( ConnectFourPattern )historicalPatternCollection.GetPattern(
holdingPattern );
if( holdingPattern.NumberOfTimesSeenInLosingGame > 0
&& IsValidPattern( holdingPattern ) == true )
{
holdingPattern.Weighting = nMemoryDefensiveWeight;
defensivePatterns.AddPattern( holdingPattern );
}
else
{
if( connectFourGame.GetSquareInfo( holdingPattern.GetStartsWith() ).IsRed
!= connectFourGame.PlayerIsRed )
defensivePatterns.AddPattern( holdingPattern );
}
上面的代码显示了查找防御模式时使用的循环。此时，我们知道该模式存在于历史模式中，并且如果该模式通常在导致失败的游戏中出现，那么我们将为其分配防御模式的内存权重。但是，如果该模式在导致失败的游戏中不常见，则将其留给后面的代码来分配权重。
这段后期的代码位于 Process Patterns 函数中，在该函数中，代码会计算响应棋子放置在模式的哪一端。这是使用简单的权重完成的，其中每侧的权重会根据方块的可用性而增加或减少，获胜位置将获得传入的权重。应该注意的是，Process Patterns 函数处理所有模式，并将每种模式类型的权重作为传入的参数。
平衡问题
程序学习部分的技巧不仅在于让程序随着时间的推移而改进，而且在于让它看起来也在改进。为此，学习不是即时发生的。代码需要看到一个走法至少两次才会开始对其做出反应。这意味着在游戏开始时，玩家可以通过一个显而易见的获胜走法来故意捉弄计算机，并在计算机识别出它之前重复几次该走法。例如，假设你在棋盘底部横向走棋；起初，计算机应该让你得逞。但一旦它注意到这个走法并记住它，程序就应该每次都阻止它。
尽管如此，应该指出的是，部分代码以更传统的方式工作，立即计算最佳走法。这样做是因为如果游戏完全依赖于它记住的内容，那么它将很容易被击败，而且我个人认为学习的印象不会那么有效。在计算机允许走棋之前，还会执行一些更高级别的代码，这是为了防止非常明显的错误。
这实际上意味着代码在三个独立的层面上运行，即记忆的初始和基本层面。正常连连看游戏工作的中间确定性层面直接基于棋盘的当前状态计算走法，而上层控制层面如果未能遵守规则（例如，允许玩家下一步获胜）则可以否决任何走法。
该软件确实有一个战术模式，尽管在程序中可能被低估了，因为在开发过程中出现了几次关于连连看游戏需要多智能的问题。我试图在可玩性和复杂性之间找到一个折衷方案，因为鉴于连连看游戏的性质，我并不完全相信可以写出一个每次都能获胜的杀手级游戏，即使你能做到，玩起来也不会有趣。因此，出于这个原因，战术并不是这个代码的主要部分，尽管有一些关于将来使用战术的想法。因此，任何看似巧妙的走法，通过让玩家阻挡一个允许软件使用玩家刚刚丢下的棋子来获胜的走法来抓住玩家，都是纯粹偶然的。
关于参考文献的说明
下面列出的书籍是我在开始研究人工智能以来读过的书。所有这些书都或多或少地影响了我的思想，并且在我知道使用某本书的内容时，我会在使用它的文章中明确说明。文本中未提及特定书籍或书籍的事实并不意味着它们没有产生影响，因为它们都是核心研究的一部分。
参考文献
- Tom Archer (2001) Inside C#, Microsoft Press。
- Jeffery Richter (2002) Applied Microsoft .NET Framework Programming, Microsoft Press。
- Charles Peltzold (2002) Programming Microsoft Windows With C#, Microsoft Press。
- Robinson et al (2001) Professional C#, Wrox。
- William R. Staneck (1997) Web Publishing Unleashed Professional Reference Edition, Sams.net。
- Robert Callan, (1999) The Essence Of Neural Networks, Prentice Hall。
- Timothy Masters (1993) Practical Neural Network Recipes In C++, Morgan Kaufmann (Academic Press)。
- Melanie Mitchell (1999) An Introduction To Genetic Algorithms, MIT Press。
- Joey Rogers (1997) Object-Oriented Neural Networks in C++, Academic Press。
- Simon Haykin (1999) Neural Networks A Comprehensive Foundation, Prentice Hall。
- Bernd Oestereich (2002) Developing Software With UML Object-Orientated Analysis And Design In Practice, Addison Wesley。
- R Beale & T Jackson (1990) Neural Computing An Introduction, Institute Of Physics Publishing。
- Bart Kosko (1994) Fuzzy Thinking, Flamingo。
- Buckley & Eslami (2002) An Introduction To Fuzzy Logic And Fuzzy Sets, Physica-Verlag。
- Steven Johnson (2001) Emergence, The Penguin Press。
- John H. Holland (1998) Emergence From Chaos To Order, Oxford University Press。
- Earl Cox (1999) The Fuzzy Systems Handbook, AP Professional。
- Mark Ward (1999) Virtual Organisms, Pan。
- Bonabeau, Dorigo, Theraulaz (1999) Swarm Intelligence From Natural To Artificial Systems, Oxford University Press。