开源中国

我们不支持 IE 10 及以下版本浏览器

It appears you’re using an unsupported browser

为了获得更好的浏览体验,我们强烈建议您使用较新版本的 Chrome、 Firefox、 Safari 等,或者升级到最新版本的IE浏览器。 如果您使用的是 IE 11 或以上版本,请关闭“兼容性视图”。
C++ 很有趣:编写一个井字游戏 (Tic Tac Toe) - 技术翻译 - 开源中国社区

C++ 很有趣:编写一个井字游戏 (Tic Tac Toe) 【已翻译100%】

标签: <无>
oschina 推荐于 4年前 (共 22 段, 翻译完成于 12-12) 评论 27
收藏  
219
推荐标签: 待读

这个有趣的C++系列打算展示一下使用C++写代码可以和其他主流语言一样高效而有趣。在第二部分,我将向你展示使用C++从无到有的创建一个井字游戏。这篇文章,以及整个系列都是针对那些想学习C++或者对这个语言性能好奇的开发者。

许多年轻人想学习编程来写游戏。C++是用的最多的用来写游戏的语言,尽管在写出下个愤怒的小鸟之前,需要学会很多的编程经验。一个井子游戏是开始学习的一个好选择,事实上,在许多年前我开始学习C++后,他是我写的地一个游戏。我希望这篇文章可以帮助到那些还不熟悉C++的初学者和有经验的开发者。

我使用的是Visual Studio 2012来写这篇文章的源代码。

Ley
 翻译得不错哦!

游戏介绍

如果你没有玩过井字游戏或者并不熟悉这个游戏,下面是来自维基百科的描述.

井字游戏 (或者"圈圈和叉叉",Xs and Os) 是一个两人的纸笔游戏,两个人轮流在3X3的网格内画圈和叉. 当一名玩家放置的标志在水平,垂直或者对角线上成一条线即获得胜利.

这个游戏也可以人机对战,先手不固定.

创建这个程序的时候有2个关键的东西:程序的逻辑和程序的UI界面. 有许多在windows中创建用户UI的方法, 包括 Win32 API, MFC, ATL, GDI+, DirectX, etc. 在这篇文章中,我将展示使用多种技术来实现同一个程序逻辑. 我们将新建2个应用, 一个使用 Win32 API 另一个使用 C++/CX.

阿丢丢
 翻译得不错哦!

游戏逻辑

如果一个玩家在网格上放下一个标记时,遵循几个简单的规则,那他就可以玩一个完美的游戏(意味着赢或者平局)。在Wikipedia上写有这些规则,在里面你也可以找到先手玩家的最优策略。

xkcd drawing上有先手和后手玩家的最优策略。尽管有几个错误(在几种情况下没有走必胜的步骤,至少在一个情况下丢失了一个X标记),我将使用这个版本作为游戏策略(修复了那些我能找到的错误)。记住电脑总是玩一个完美的游戏。如果你实现了这样一个游戏,你可能也想让用户赢,这种情况下你需要一个不同的方法。当对本文的目的,这个策略应该足够了。

Ley
 翻译得不错哦!

提出的第一个问题是在C++程序中用什么数据结构来表示图像的模型。这可以有不同的选择,比如树、图、数组或者位字段(如果真有人对内存消耗很在意)。网格有9个单元,我选择的最简单的使用对每个单元使用一个包含9个整数的数组:0表示空的单元,1表示单元被标记为X,2表示单元被标记为O。让我们看下图以及它将被如何编码。

这幅图可以这么理解:

  • 在单元(0,0)放X。网格可以编码为:1,0,0,0,0,0,0,0,0
  • 如果对手在单元(0,1)放置O,那么在单元(1,1)放置X。现在网格编码为:1,2,0,0,1,0,0,0,0
  • 如果对手在单元(0,2)放置O,那么在单元(2,2)放置X。现在网格编码为:1,2,2,0,1,0,0,0,1
  • ...
  • 如果对手在单元(2,2)放置O,那么在单元(2,0)放置X。现在网格编码为:1,2,0,0,1,0,1,0,2。这时,无论对手怎么做,X都将赢得比赛。
  • 如果对手在单元(0,2)放置O,那么在单元(1,0)放置X。现在网格编码为:1,2,2,1,1,0,1,0,2。这表示的是一个赢得比赛的一步。
  • ...
Ley
 翻译得不错哦!

记住这个我们就可以开始在程序中对其编码了。我们将使用一个std::array来表示一个9格板。这是个固定大小的容器,在编译时就已知的大小,在连续的内存区域存储元素。为了避免一遍又一遍的使用相同数组类型,我将定义一个别名来简化。

#include <array>

typedef std::array<char, 9> tictactoe_status;
上面描述的最优策略用这样的数组队列(另一个数组)来表示。
tictactoe_status const strategy_x[] = 
{
   {1,0,0,0,0,0,0,0,0},
   {1,2,0,0,1,0,0,0,0},
   {1,2,2,0,1,0,0,0,1},
   {1,2,0,2,1,0,0,0,1},
   // ...
};

tictactoe_status const strategy_o[] = 
{
   {2,0,0,0,1,0,0,0,0},
   {2,2,1,0,1,0,0,0,0},
   {2,2,1,2,1,0,1,0,0},
   {2,2,1,0,1,2,1,0,0},
   // ...
};
strategy_x是先手玩家的最优策略,strategy_o是后手玩家的最优策略。如果你看了文中的源代码,你将注意到这两个数组的真实定义和我前面展示的不同。
tictactoe_status const strategy_x[] = 
{
#include "strategy_x.h"
};

tictactoe_status const strategy_o[] = 
{
#include "strategy_o.h"
};
Ley
 翻译得不错哦!

这是个小技巧,我的理由是,它允许我们把真实的很长的数组内容放在分开的文件中(这些文件的扩展性不重要,它可以不仅仅是C++头文件,也可以是其他任何文件),保证源码文件和定义简单干净。strategy_x.h和strategy_o.h文件在编译的预处理阶段就被插入到源码文件中,如同正常的头文件一样。下面是strategy_x.h文件的片断。

// http://imgs.xkcd.com/comics/tic_tac_toe_large.png
// similar version on http://upload.wikimedia.org/wikipedia/commons/d/de/Tictactoe-X.svg
// 1 = X, 2 = O, 0 = unoccupied

1,0,0,0,0,0,0,0,0,

1,2,0,0,1,0,0,0,0,
1,2,2,0,1,0,0,0,1,
1,2,0,2,1,0,0,0,1,
1,2,0,0,1,2,0,0,1,
你应该注意到,如果你使用支持C++11的编译器,你可以使用一个std::vector而不是C类型的数组。Visual Studio 2012不支持这么做,但在Visual Studio 2013中支持。
std::vector<tictactoe_status> strategy_o = 
{
   {2, 0, 0, 0, 1, 0, 0, 0, 0},
   {2, 2, 1, 0, 1, 0, 0, 0, 0},
   {2, 2, 1, 2, 1, 0, 1, 0, 0},
   {2, 2, 1, 0, 1, 2, 1, 0, 0},
   {2, 2, 1, 1, 1, 0, 2, 0, 0},
};
为了定义这些数字表示的对应玩家,我定义了一个叫做tictactoe_player的枚举类型变量。
enum class tictactoe_player : char
{
   none = 0,
   computer = 1,
   user = 2,
};
Ley
 翻译得不错哦!

游戏的逻辑部分将会在被称之为tictactoe_game 的类中实现。最基本的,这个 class 应该有下面的状态:

  • 一个布尔值用来表示游戏是否开始了,命名为 started 。
  • 游戏的当前状态(网格上的标记), 命名为 status 。
  • 根据当前的状态得到的之后可以进行的下法的集合,命名为strategy
class tictactoe_game
{
   bool started;
   tictactoe_status status;
   std::set<tictactoe_status> strategy;
   
   // ...
};

在游戏的过程中,我们需要知道游戏是否开始了、结束了,如果结束了,需要判定是否有哪个玩家赢了或者最终两个人打平。为此,tictactoe_game类提供了三个方法:

  • is_started()来表示游戏是否开始了
  • is_victory()来检查是否有哪位玩家在游戏中获胜
  • is_finished()来检查游戏是否结束。当其中某位玩家在游戏中获胜或者当网格被填满玩家不能再下任何的棋子的时候,游戏结束。
bool is_started() const {return started;}
bool is_victory(tictactoe_player const player) const {return is_winning(status, player);}
bool is_finished() const 
{
laiconglin
 翻译得不错哦!

对于方法is_victory()和is_finished(),实际上是依赖于两个私有的方法,is_full(), 用来表示网格是否被填满并且不能再放下任何的棋子,以及方法is_winning, 用来表示在该网格上是否有某玩家胜出。它们的实现将会很容易被读懂。is_full 通过计算网格中空的(在表示网格的数组中值为0)格子的数量,如果没有这样的格子那么将返回true。is_winning将会检查这些连线,网格的行、列、以及对角线,依此来查看是否有哪位玩家已经获胜。

bool is_winning(tictactoe_status const & status, tictactoe_player const player) const
{
   auto mark = static_cast<char>(player);
   return 
      (status[0] == mark && status[1] == mark && status[2] == mark) ||
      (status[3] == mark && status[4] == mark && status[5] == mark) ||
      (status[6] == mark && status[7] == mark && status[8] == mark) ||
      (status[0] == mark && status[4] == mark && status[8] == mark) ||
      (status[2] == mark && status[4] == mark && status[6] == mark) ||
      (status[0] == mark && status[3] == mark && status[6] == mark) ||
      (status[1] == mark && status[4] == mark && status[7] == mark) ||
      (status[2] == mark && status[5] == mark && status[8] == mark);
}

bool is_full(tictactoe_status const & status) const 
{
   return 0 == std::count_if(std::begin(status), std::end(status), [](int const mark){return mark == 0;});
}
当一个玩家获胜的时候,我们想给他所连成的线(行、列、或者对角线)上画一条醒目的线段。因此首先我们得知道那条线使得玩家获胜。我们使用了方法get_winning_line()来返回一对 tictactoe_cell,用来表示线段的两端。它的实现和is_winning很相似,它检查行、列和对角线上的状态。它可能会看起来有点冗长,但是我相信这个方法比使用循环来遍历行、列、对角线更加简单。

struct tictactoe_cell
{
   int row;
   int col;

   tictactoe_cell(int r = INT_MAX, int c = INT_MAX):row(r), col(c)
   {}

   bool is_valid() const {return row != INT_MAX && col != INT_MAX;}
};

std::pair<tictactoe_cell, tictactoe_cell> const get_winning_line() const
{
   auto mark = static_cast<char>(tictactoe_player::none);
   if(is_victory(tictactoe_player::computer))
      mark = static_cast<char>(tictactoe_player::computer);
   else if(is_victory(tictactoe_player::user))
      mark = static_cast<char>(tictactoe_player::user);

   if(mark != 0)
   {
      if(status[0] == mark && status[1] == mark && status[2] == mark) 
         return std::make_pair(tictactoe_cell(0,0), tictactoe_cell(0,2));
      if(status[3] == mark && status[4] == mark && status[5] == mark)
         return std::make_pair(tictactoe_cell(1,0), tictactoe_cell(1,2));
      if(status[6] == mark && status[7] == mark && status[8] == mark)
         return std::make_pair(tictactoe_cell(2,0), tictactoe_cell(2,2));
      if(status[0] == mark && status[4] == mark && status[8] == mark)
         return std::make_pair(tictactoe_cell(0,0), tictactoe_cell(2,2));
      if(status[2] == mark && status[4] == mark && status[6] == mark)
         return std::make_pair(tictactoe_cell(0,2), tictactoe_cell(2,0));
      if(status[0] == mark && status[3] == mark && status[6] == mark)
         return std::make_pair(tictactoe_cell(0,0), tictactoe_cell(2,0));
      if(status[1] == mark && status[4] == mark && status[7] == mark)
         return std::make_pair(tictactoe_cell(0,1), tictactoe_cell(2,1));
      if(status[2] == mark && status[5] == mark && status[8] == mark)
         return std::make_pair(tictactoe_cell(0,2), tictactoe_cell(2,2));
   }

   return std::make_pair(tictactoe_cell(), tictactoe_cell());
}
laiconglin
 翻译得不错哦!

现在我们只剩下添加开始游戏功能和为网格放上棋子功能(电脑和玩家两者).

对于开始游戏,我们需要知道,由谁开始下第一个棋子,因此我们可以采取比较合适的策略(两种方式都需要提供,电脑先手或者玩家先手都要被支持)。同时,我们也需要重置表示网格的数组。方法start()对开始新游戏进行初始化。可以下的棋的策略的集合被再一次的初始化, 从stategy_x 或者strategy_o进行拷贝。从下面的代码可以注意到,strategy是一个std::set, 并且strategy_x或者strategy_o都是有重复单元的数组,因为在tictoctoe表里面的一些位置是重复的。这个std::set 是一个只包含唯一值的容器并且它保证了唯一的可能的位置(例如对于strategy_o来说,有一半是重复的)。<algorithm> 中的std::copy算法在这里被用来进行数据单元的拷贝,将当前的内容拷贝到std::set中,并且使用方法assign()来将std::array的所有的元素重置为0。

void start(tictactoe_player const player)
{
   strategy.clear();
   if(player == tictactoe_player::computer)
      std::copy(std::begin(strategy_x), std::end(strategy_x), 
                std::inserter(strategy, std::begin(strategy)));
   else if(player == tictactoe_player::user)
      std::copy(std::begin(strategy_o), std::end(strategy_o), 
                std::inserter(strategy, std::begin(strategy)));
                
   status.assign(0);
   
   started = true;
}
laiconglin
 翻译得不错哦!

当玩家走一步时,我们需要做的是确保选择的网格是空的,并放置合适的标记。move()方法的接收参数是网格的坐标、玩家的记号,如果这一步有效时返回真,否则返回假。

bool move(tictactoe_cell const cell, tictactoe_player const player)
{
   if(status[cell.row*3 + cell.col] == 0)
   {
      status[cell.row*3 + cell.col] = static_cast<char>(player);
      
      if(is_victory(player))
      {
         started = false;
      }
      
      return true;
   }

   return false;
}
电脑走一步时需要更多的工作,因为我们需要找到电脑应该走的最好的下一步。重载的move()方法在可能的步骤(策略)集合中查询,然后从中选择最佳的一步。在走完这步后,会检查电脑是否赢得这场游戏,如果是的话标记游戏结束。这个方法返回电脑走下一步的位置。
tictactoe_cell move(tictactoe_player const player)
{
   tictactoe_cell cell;

   strategy = lookup_strategy();

   if(!strategy.empty())
   {
      auto newstatus = lookup_move();

      for(int i = 0; i < 9; ++i)
      {
         if(status[i] == 0 && newstatus[i]==static_cast<char>(player))
         {
            cell.row = i/3;
            cell.col = i%3;
            break;
         }
      }

      status = newstatus;

      if(is_victory(player))
      {
         started = false;
      }
   }

   return cell;
}
lookup_strategy()方法在当前可能的移动位置中迭代,来找到从当前位置往哪里移动是可行的。它利用了这样的一种事实,空的网格以0来表示,任何已经填过的网格,不是用1就是用2表示,而这两个值都大于0。一个网格的值只能从0变为1或者2。不可能从1变为2或从2变为1。
Ley
 翻译得不错哦!
本文中的所有译文仅用于学习和交流目的,转载请务必注明文章译者、出处、和本文链接
我们的翻译工作遵照 CC 协议,如果我们的工作有侵犯到您的权益,请及时联系我们
评论(27)
Ctrl/CMD+Enter

有趣,非常有趣,遇到一个上千字错误说明的模板错误更是有趣,各种能让人精神崩溃大小便失禁的错误非常有趣。虽然如此,C++也确实是个真正有趣的语言,一直用C++。
mark

引用来自“刘子玄”的评论

有趣,非常有趣,遇到一个上千字错误说明的模板错误更是有趣,各种能让人精神崩溃大小便失禁的错误非常有趣。虽然如此,C++也确实是个真正有趣的语言,一直用C++。

各种能让人精神崩溃大小便失禁的错误非常有趣
收藏

引用来自“刘子玄”的评论

有趣,非常有趣,遇到一个上千字错误说明的模板错误更是有趣,各种能让人精神崩溃大小便失禁的错误非常有趣。虽然如此,C++也确实是个真正有趣的语言,一直用C++。

敬请斧正
他是说c++语言本身,并非你的程序
习惯就好了~!
先收藏了,谢谢楼主
标记一下。
mark
楼主,我正在用java做一个井字棋游戏,但是这里面的极大极小算法一直搞不明白,你能不能给详细讲解一下啊?
mark
mark
mark
mark
mark
居然也可以用 XAML 的哟!!!
mark下
mark
写个博弈算法嵌入其中是不是不会输了?
顶部