用C++編寫一個井字游戲 (Tic Tac Toe)

jopen 11年前發布 | 42K 次閱讀 游戲 C/C++開發

這個有趣的C++系列打算展示一下使用C++寫代碼可以和其他主流語言一樣高效而有趣。在第二部分，我將向你展示使用C++從無到有的創建一個井字游戲。這篇文章，以及整個系列都是針對那些想學習C++或者對這個語言性能好奇的開發者。

許多年輕人想學習編程來寫游戲。C++是用的最多的用來寫游戲的語言，盡管在寫出下個憤怒的小鳥之前，需要學會很多的編程經驗。一個井子游戲是開始學習的一個好選擇，事實上，在許多年前我開始學習C++后，他是我寫的地一個游戲。我希望這篇文章可以幫助到那些還不熟悉C++的初學者和有經驗的開發者。

我使用的是Visual Studio 2012來寫這篇文章的源代碼。

游戲介紹

如果你沒有玩過井字游戲或者并不熟悉這個游戲,下面是來自維基百科的描述.

井字游戲 (或者"圈圈和叉叉",Xs and Os) 是一個兩人的紙筆游戲,兩個人輪流在3X3的網格內畫圈和叉. 當一名玩家放置的標志在水平,垂直或者對角線上成一條線即獲得勝利.
用C++編寫一個井字游戲 (Tic Tac Toe)

這個游戲也可以人機對戰,先手不固定.

創建這個程序的時候有2個關鍵的東西:程序的邏輯和程序的UI界面. 有許多在windows中創建用戶UI的方法, 包括 Win32 API, MFC, ATL, GDI+, DirectX, etc. 在這篇文章中,我將展示使用多種技術來實現同一個程序邏輯. 我們將新建2個應用, 一個使用 Win32 API 另一個使用 C++/CX.

游戲邏輯

如果一個玩家在網格上放下一個標記時，遵循幾個簡單的規則，那他就可以玩一個完美的游戲（意味著贏或者平局）。在Wikipedia上寫有這些規則，在里面你也可以找到先手玩家的最優策略。

用C++編寫一個井字游戲 (Tic Tac Toe)

在xkcd drawing上有先手和后手玩家的最優策略。盡管有幾個錯誤（在幾種情況下沒有走必勝的步驟，至少在一個情況下丟失了一個X標記），我將使用這個版本作為游戲策略（修復了那些我能找到的錯誤）。記住電腦總是玩一個完美的游戲。如果你實現了這樣一個游戲，你可能也想讓用戶贏，這種情況下你需要一個不同的方法。當對本文的目的，這個策略應該足夠了。

提出的第一個問題是在C++程序中用什么數據結構來表示圖像的模型。這可以有不同的選擇，比如樹、圖、數組或者位字段（如果真有人對內存消耗很在意）。網格有9個單元，我選擇的最簡單的使用對每個單元使用一個包含9個整數的數組：0表示空的單元，1表示單元被標記為X，2表示單元被標記為O。讓我們看下圖以及它將被如何編碼。

用C++編寫一個井字游戲 (Tic Tac Toe)

這幅圖可以這么理解：

  • 在單元（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。這表示的是一個贏得比賽的一步。

  • ...
    • </ul>

    記住這個我們就可以開始在程序中對其編碼了。我們將使用一個std::array來表示一個9格板。這是個固定大小的容器，在編譯時就已知的大小，在連續的內存區域存儲元素。為了避免一遍又一遍的使用相同數組類型，我將定義一個別名來簡化。 

    #include  typedef std::array 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},
   // ...
};</pre>strategy_x是先手玩家的最優策略，strategy_o是后手玩家的最優策略。如果你看了文中的源代碼，你將注意到這兩個數組的真實定義和我前面展示的不同。 
    tictactoe_status const strategy_x[] = 
{
    

    include "strategy_x.h"
    

    };
    

    tictactoe_status const strategy_o[] = 
{
    

    include "strategy_o.h"
    

    };</pre> 
    這是個小技巧，我的理由是，它允許我們把真實的很長的數組內容放在分開的文件中（這些文件的擴展性不重要，它可以不僅僅是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,</pre>你應該注意到，如果你使用支持C++11的編譯器，你可以使用一個std::vector而不是C類型的數組。Visual Studio 2012不支持這么做，但在Visual Studio 2013中支持。 
    std::vector 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,
};
     
    游戲的邏輯部分將會在被稱之為tictactoe_game 的類中實現。最基本的，這個 class 應該有下面的狀態： 
    

      

    • 一個布爾值用來表示游戲是否開始了，命名為 started 。 
      • 

    • 游戲的當前狀態(網格上的標記), 命名為 status 。 
      • 

    • 根據當前的狀態得到的之后可以進行的下法的集合，命名為strategy 
      • 
</ul>

      class tictactoe_game
{
   bool started;
   tictactoe_status status;
   std::set strategy;
      

      // ...
};</tictactoe_status></pre> 
      在游戲的過程中，我們需要知道游戲是否開始了、結束了，如果結束了，需要判定是否有哪個玩家贏了或者最終兩個人打平。為此，tictactoe_game類提供了三個方法： 
      

        

      • is_started()來表示游戲是否開始了 
        • 

      • is_victory()來檢查是否有哪位玩家在游戲中獲勝 
        • 

      • is_finished()來檢查游戲是否結束。當其中某位玩家在游戲中獲勝或者當網格被填滿玩家不能再下任何的棋子的時候，游戲結束。 
        • 
</ul>
        

        bool is_started() const {return started;}
bool is_victory(tictactoe_player const player) const {return is_winning(status, player);}
bool is_finished() const 
{
        </span> 
        對于方法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(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), {return mark == 0;});
}</char></pre>當一個玩家獲勝的時候，我們想給他所連成的線(行、列、或者對角線)上畫一條醒目的線段。因此首先我們得知道那條線使得玩家獲勝。我們使用了方法get_winning_line()來返回一對 tictactoe_cell，用來表示線段的兩端。它的實現和is_winning很相似，它檢查行、列和對角線上的狀態。它可能會看起來有點冗長，但是我相信這個方法比使用循環來遍歷行、列、對角線更加簡單。</span> 
        

        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(tictactoe_player::none);
   if(is_victory(tictactoe_player::computer))
      mark = static_cast(tictactoe_player::computer);
   else if(is_victory(tictactoe_player::user))
      mark = static_cast(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());
}</char></char></char></TICTACTOE_CELL,></pre> 
        現在我們只剩下添加開始游戲功能和為網格放上棋子功能(電腦和玩家兩者). 
        

        對于開始游戲，我們需要知道，由誰開始下第一個棋子，因此我們可以采取比較合適的策略（兩種方式都需要提供，電腦先手或者玩家先手都要被支持）。同時，我們也需要重置表示網格的數組。方法start()對開始新游戲進行初始化。可以下的棋的策略的集合被再一次的初始化, 從stategy_x 或者strategy_o進行拷貝。從下面的代碼可以注意到，strategy是一個std::set, 并且strategy_x或者strategy_o都是有重復單元的數組，因為在tictoctoe表里面的一些位置是重復的。這個std::set 是一個只包含唯一值的容器并且它保證了唯一的可能的位置(例如對于strategy_o來說，有一半是重復的)。 中的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;
}</pre> 
        當玩家走一步時，我們需要做的是確保選擇的網格是空的，并放置合適的標記。move()方法的接收參數是網格的坐標、玩家的記號，如果這一步有效時返回真，否則返回假。 
        

        bool move(tictactoe_cell const cell, tictactoe_player const player)
{
   if(status[cell.row3 + cell.col] == 0)
   {
      status[cell.row3 + cell.col] = static_cast(player);
        


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

  return true;

        

        }
        

        return false;
}</char></pre>電腦走一步時需要更多的工作，因為我們需要找到電腦應該走的最好的下一步。重載的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;
}</char></pre>lookup_strategy()方法在當前可能的移動位置中迭代，來找到從當前位置往哪里移動是可行的。它利用了這樣的一種事實，空的網格以0來表示，任何已經填過的網格，不是用1就是用2表示,而這兩個值都大于0。一個網格的值只能從0變為1或者2。不可能從1變為2或從2變為1。 
        當游戲開始時的網格編碼為0,0,0,0,0,0,0,0,0來表示并且當前情況下任何的走法都是可能的。這也是為什么我們要在thestart()方法里把整個步數都拷貝出來的原因。一旦玩家走了一步，那能走的步數的set便會減少。舉個例子，玩家在第一個格子里走了一步。此時網格編碼為1,0,0,0,0,0,0,0,0。這時在數組的第一個位置不可能再有0或者2的走法因此需要被過濾掉。 
        

        std::set tictactoe_game::lookup_strategy() const
{
   std::set nextsubstrategy;
        

        for(auto const & s : strategy)
   {
      bool match = true;
      for(int i = 0; i < 9 && match; ++i)
      {
         if(s[i] < status[i])
            match = false;
      }
        


          if(match)
  {
     nextsubstrategy.insert(s);
  }

        

        }
        

        return nextsubstrategy;
}</tictactoe_status></tictactoe_status></pre> 
        在選擇下一步時我們需要確保我們選擇的走法必須與當前的標記不同，如果當前的狀態是1,2,0,0,0,0,0,0,0而我們現在要為玩家1選擇走法那么我們可以從余下的7個數組單元中選擇一個，可以是：1,2,1,0,0,0,0,0,0或1,2,0,1,0,0,0,0,0... 或1,2,0,0,0,0,0,0,1。然而我們需要選擇最優的走法而不是僅僅只隨便走一步，通常最優的走法也是贏得比賽的關鍵。因此我們需要找一步能使我們走向勝利，如果沒有這樣的一步，那就隨便走吧。 
        

        tictactoe_status tictactoe_game::lookup_move() const
{
   tictactoe_status newbest = {0};
   for(auto const & s : strategy)
   {
      int diff = 0;
      for(int i = 0; i < 9; ++i)
      {
         if(s[i] > status[i])
            diff++;
      }
        


          if(diff == 1)
  {
     newbest = s;
     if(is_winning(newbest, tictactoe_player::computer))
     {
        break;
     }
  }

        

        }
        

        assert(newbest != empty_board);
        

        return newbest;
}</pre> 
        做完了這一步，我們的游戲的邏輯部分就完成了。更多細節請閱讀game.h和game.cpp中的代碼 
        

        一個用Win32 API實現的游戲 
        

        我將用Win32 API做用戶界面來創建第一個應用程序。如果你不是很熟悉Win32 編程那么現在已經有大量的資源你可以利用學習。為了使大家理解我們如何創建一個最終的應用，我將只講述一些必要的方面。另外，我不會把每一行代碼都展現并解釋給大家，但是你可以通過下載這些代碼來閱讀瀏覽它。 
        

        一個最基本的Win32應用需要的一些內容：
 本文由用戶 jopen 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。
 轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。
 本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！