Learn about the Reversi C++ game engine

Article
10/13/2015

[This article is for Windows 8.x and Windows Phone 8.x developers writing Windows Runtime apps. If you’re developing for Windows 10, see the latest documentation]

The Reversi sample now supports pluggable game engines. The solution now defines an IGame interface and includes a C++ Windows Runtime Component project that contains a game engine that is written entirely in ISO standard C++, and a C++/CX wrapper class that implements IGame.

You can compile the solution using either the C# Windows Runtime component in the ReversiGameComponentCS project, or the C++ Windows Runtime component in ReversiGameComponentCPP. The new GameFactory class can be conditionally compiled to create either the C++ engine or the C# engine depending on whether you define CSHARP. For more information, see Understand the Reversi app structure: The model layer.

The standard C++ game engine has no dependencies on the Windows Runtime Type system or C++/CX syntax. We’ve created this C++ implementation for two basic purposes (besides the fact that it was fun):

to demonstrate how to add new standard C++ code, or port existing C++ code, into a Windows Store app.
To briefly compare C++ and C++/CX coding idioms with C# idioms, for developers whose background is primarily in .NET.

For a general introduction to the sample, see Reversi, a Windows Store game in XAML, C#, and C++. To see how specific features are used in the sample, see Learn how the Reversi sample uses Windows Store app features. To understand how the various features work together as a whole, see Understand the Reversi app structure.

Download the Reversi sample app or browse the source code.

Background

In general, C++ code for Windows Store appsWindows Store app that doesn’t have to interoperate with the Windows Runtime type system can and should be written in ISO standard C++, not C++/CX. If you have existing portable code in standard C++, you can add it to a Windows Store appWindows Store app or to a Windows Runtime component. C++/CX code can coexist with and consume any standard C++ types and constructs that are supported by the Visual C++ compiler, as well as Windows Runtime types (ref classes, delegates, etc). It’s all C++ and no wrapper is required for C++/CX to standard C++ interoperation. However, to make standard C++ code available to Windows Store appsWindows Store apps and components that are written in C#, Visual Basic, or JavaScript, then you need to write an interface in C++/CX that’s callable through the Windows Runtime type system, and if necessary translate between standard C++ types and the Windows Runtime types.

Packaging standard C++ code

You have several options for using standard C++ code from a Windows Store appWindows Store app or component:

Add the source files directly to the project. A ref class can consume a standard C++ class or template as a private member or local variable and pass it around in private class methods. It can also call free functions. That is the approach used in the Reversi sample.
As a static library. You can make new static library projects for Windows Store appsWindows Store apps, and you can also drop in existing libs, with some restrictions. For more information, see Static libraries (C++/CX).
As a DLL. You can also invoke a standard C++ DLL from a Windows Store appWindows Store app or component, with some restrictions. For more information, see DLLs (C++/CX).

Wrapping standard C++ code in a C++/CX interface

In the C# ReversiGameComponent project, the Game class in Game.cs contains both the IGame interface and the implementation of the game engine. In ReversiGameComponentCPP, the ReversiGameWrapper ref class in game.h and game.cpp implements the IGame interface, and is written in C++/CX. The game engine is implemented in standard C++ in the ReversiGameEngine class in ReversiGameEngine.h/.cpp.

The C# client creates an instance of the ReversiGameWrapper class and calls its IGame methods. The wrapper class crates an instance of the ReversiGameEngine class and forwards the calls to it to do the actual work.

The C++ code in ReversiGameEngine.h /.cpp has no dependencies on the Windows Runtime type system. The code itself is closely based on the C# game engine (in Game.cs) and does not attempt to significantly re-architect it. The method names are also mostly the same. This allows for easier comparison between the C# and the modern C++ ways of doing things.

Enabling serialization of C++/CX types in a C# client app

The Windows Runtime does not define a serialization API for saving app state. A C# client app can use the convenient SuspensionManager class that is auto-generated in a Visual Studio project. In a C# project, this class uses the .NET DataContractSerializer to enable serialization. But DataContractSerializer understands only .NET types and the built-in types such as int and float. It cannot serialize C++/CX or Windows Runtime types. When you use a C++/CX Windows Runtime Component in a C# or Microsoft Visual BasicWindows Store appWindows Store app, and that component contains state that you need to save if the app is terminated, you can either write your code so that all state is stored in the built-in scalar types which are serializable by DataContractSerializer, or you can wrap the C++/CX class inside a .NET wrapper class. In Reversi we chose the latter approach and that is the purpose of the CLRSerializableCPPGame class, which implements IGame.

Type conversions

The ReversiGameWrapper class is written in C++/CX and it implements the ReversiGameModel::IGame interface. That interface uses some Windows Runtime helper types as method parameters, including the Space, Score classes and the State enum. The standard C++ code defines corresponding types as regular C++ structs ReversiSpace and ReversiScore and a standard C++ enum ReversiState. When the ReversiGameWrapper class receives a WinRT type from the C# client, for example a Space object, it can’t just cast that type to a ReversiSpace and pass it to the engine. It must instead construct a ReversiSpace from the data members of the WinRT Space. So it would be more precise to talk about type marshaling or type translation, rather than type conversion between WinRT and standard C++.

The built-in types (int, bool, float, etc) require no conversion, and we can use those to construct both the WinRT helper types and the standard C++ types. The following example shows a standard ReversiSpace being constructed from the ISpace^ move object that was passed in from C#.

// ReversiGamewrapper class
bool ReversiGameWrapper::IsValidMove(ISpace^ move)
{
    if (move == nullptr)
    {
        return m_Game->IsValidMove(ReversiSpace(-1, -1));        
    }

    return m_Game->IsValidMove(ReversiSpace(move->Row, move->Column));
}

// ReversiGameEngine class
bool ReversiGameEngine::IsValidMove(const ReversiSpace& move) const
{
    return move.Column != -1 ? 
        IsValidMoveSpace(m_board, GetCurrentPlayer(), move) : 
        IsPassValid(GetCurrentPlayer());
}

Of course there is a cost to this conversion, which varies depending on the specific types involved. If the methods were on a super-critical hot path, we could perhaps avoid the cost by simply passing the row and column values to the engine class. But then we would have to consider whether the resulting code would be more difficult to understand, test, and maintain.

Properties

The IGame interface defines properties which the ReversiGameWrapper class must implement. For most simple properties in ReversiGameWrapper, the implementation is simply to call through to the inner class:

// ReversiGameWrapper class
property ReversiGameModel::State Winner
{
    virtual ReversiGameModel::State get() 
    {
        return static_cast<ReversiGameModel::State> ( m_Game->GetWinner());
    }
}

// ReversiGameEngine class
ReversiState GetWinner() { return GetWinner(m_board); }
ReversiState ReversiGameEngine::GetWinner(ReversiBoard& board) const
{
    auto score = GetScore(board);
    if (!IsGameOver(board) || score.PlayerOne == score.PlayerTwo) 
    {
        return ReversiState::None;
    }
    return score.PlayerOne > score.PlayerTwo ? ReversiState::One : ReversiState::Two;
}

Standard C++ doesn’t have the concept of a property, and the use of public fields is never a good idea in a big class like ReversiGameEngine. Data members are declared as private fields, and, when necessary, public accessor methods are also defined. Fields in ReversiGameEngine such as m_board, m_rowCount and m_columnCount, don’t have public accessors because they aren’t needed. The ReversiGameWrapper instance captures values for its RowCount and ColumnCount properties when the app starts up, and these values never change. We keep m_board private by declaring public parameterless methods that call private methods that take a board as parameter. We need that parameter internally because sometimes the board passed in will be a copy used in the AI evaluation, not the actual game board. As much as possible, we want to hide the ReversiGameEngine internals from the wrapper class.

There is typically not much performance penalty for simple properties. However, properties that expose arrays or collections are very expensive to construct and to access and should be avoided. The Board property, which is required by the IGame interface to support data-binding functionality in the C# app, looks like this (only the getter is shown here):

// ReversiGamewrapper class
using namespace WFC = Windows::Foundation::Collections;

property WFC::IVector<WFC::IVector<ReversiGameModel::State>^>^  Board
{
    virtual WFC::IVector<WFC::IVector<ReversiGameModel::State>^>^ get();
    virtual void set(WFC::IVector<WFC::IVector<ReversiGameModel::State>^>^);
}
IVector<IVector<State>^>^ Game::Board::get()
{
    Vector<IVector<State>^>^ boardAsVector = ref new Vector<IVector<State>^>();
    for (int row = 0; row < RowCount; ++row)
    {
        auto v = ref new Vector<State>();
        for (int col = 0; col < ColumnCount; ++col)
           {
               v->Append(static_cast<State> (m_Game->GetAt(row, col)));
        }
           boardAsVector->Append(v);
    }
    return boardAsVector;
}

The IGame board is a two-dimensional IVector<Vector<State>> and the C++ board is a one-dimensional std::vector<ReversiState>. Even if the client just wants to access a single element, say the space at Row 3, Column 4, if it were to ask for Board[3][4], the wrapper class would first have to create the entire collection. Obviously this is very inefficient, especially if we don’t actually need the entire board. As much as possible we avoid exposing arrays and collections as properties. If you just need to access a single element, it is better to provide an API to do that. The IGame interface provides the GetSpaceState method for this purpose. In C++/CX we can simply call through to a corresponding method on the engine class to quickly get the desired element.

// ReversiGameWrapper class
State Game::GetSpaceState(int row, int column)
{
    return static_cast<State>(m_Game->GetAt(row, column));
}

// ReversiGameEngine class
ReversiState ReversiGameEngine::GetAt(size_t row, size_t col) 
{
    size_t spaceNumber = row * m_columnCount + col;
    if (spaceNumber < 0 || spaceNumber >= m_board.size())
    {
        throw runtime_error("Invalid board position.");
    }
    return m_board[spaceNumber];
}

Asynchronous operations

The IGame interface defines some methods that return an IAsyncOperation or IAsyncAction. The easiest way to implement these in the ReversiGameWrapper class is to use the create_async method, and then just call into the ReversiGameEngine class inside the lambda expression:

/// <summary>
/// Performs an AI move using the specified search depth and an optional cancellation token.
/// </summary>
/// <param name="searchDepth">The AI search depth to use.</param>
/// <param name="cancellationToken">A token that the caller can use to cancel the move.</param>
Windows::Foundation::IAsyncAction^ ReversiGameWrapper::AiMoveAsync(int searchDepth)
{
    return create_async([this, searchDepth](cancellation_token token)
    {
        auto ShouldCancel = [token]()
        {
            if (token.is_canceled())
            {
                cancel_current_task();
            }
        };
        m_Game.Move(m_Game.GetBestMove(searchDepth, ShouldCancel));
    });
}

The ReversiGameEngine class itself does not define any asynchronous operations. There is no need for it to, because the wrapper class calls the method on a worker thread.

Exceptions

The ReversiGameEngine class throws exceptions of type std::logic_error but we never try to handle them in the wrapper class because they always signal a programming error that should be fixed during the development phase. If we did want to handle them in the ReversiGameWrapper class we could do so. But to pass the exception from ReversiGameWrapper on to client code across the application binary interface (ABI) , we would have to catch the runtime_error, swallow it, and throw a new Platform::Exception object. A C# or JavaScript client has no idea what a std::exception is. Those exceptions, if not handled in your standard C++ or C++/CX code, will bring down the process.

Comparing C# to standard C++ in the Reversi game engine

If you examine the ReversiGameEngine class you will see that in many ways modern C++ is not very different from .NET or Java code. We use standard library containers ("collections") and algorithms for searching and sorting, rather than rolling our own, for strings we use the std::wstring class rather than raw character arrays, we use range-based for-loops (similar to foreach) when appropriate, and we throw exceptions rather than returning error codes.

The following sections call out some specific code examples for comparison:

Passing by value vs. by reference

In Reversi, the game board is naturally represented as a container (called collections in .NET) of elements that represent the board spaces. Many class methods take the board as a parameter. We can’t always just use the member variable m_board because it represents the current state of the actual game, and sometimes a method needs to operate on a hypothetical board when evaluating potential moves. In both C# and C++, parameter arguments are passed by value by default. In C# when you pass a complex object by value, it is only the reference that is copied. In C++, when you pass any object, by default the entire object is copied. This can be quite expensive for containers with lots of elements, and it can also lead to unexpected results If the method is supposed to modify the board member variable. In C++, we have to explicitly pass the board by reference (by appending “&” to the type) to avoid unnecessary copy operations.

private static bool IsBoardFilled(IList<IList<State>> board)

bool IsBoardFilled(const ReversiBoard& board);

Note that when when the input parameter is marked as const, the C++ compiler will raise an error if the method attempts to modify the argument that is passed in. In the C# example, the method can modify the content of the board. This isn’t allowed in the C++ signature because of const. In the case of the game board, for example, we always pass it by const reference except in the one case where we do need to pass a copy of the board.

Object Initialization

Member initialization syntax

C++ uses member initialization syntax when constructing objects. In the following C++/CX example, a member initializer is used to initialize m_Game. The RowCount and ColumnCount properties are initialized via assignment, because C++ member initialization doesn’t support properties, which are a Windows Runtime concept.

ReversiGameWrapper::ReversiGameWrapper() : m_Game(ReversiGameEngine(8, 8 ))
{
    // Trivial properties (those without explicit backing fields) 
    // must be initialized via assignment.
    RowCount = 8;
    ColumnCount = 8;
}

The ReversiGameEngine class initializes m_columnCount and m_rowCount using member initializer syntax because they are simply fields.

ReversiGameEngine::ReversiGameEngine(int rowCount, int columnCount): 
    m_columnCount(columnCount), m_rowCount(rowCount), m_randomGenerator(rd())
{           
    // ...

    InitializeBoard();
}

Brace initialization

m_Directions is a vector that holds structs of type ReversiSpace, which represent the directions of play from any given spot on the board: up, down, diagonal, right, left. We initialize the vector in the same statement where it is declared by providing an initializer list. The outer braces indicate that the vector is to be initialized using brace semantics, the next braces represent the implicit initializer list, and each set of inner braces represent one ReversiSpace object. This statement invokes the vector constructor that takes a std::initializer_list<T> as an argument.

std::vector<ReversiSpace> m_Directions = { { { -1, -1 }, { -1, 0 }, { -1, 1 },
                                             { 0, -1 },             { 0, 1 },
                                             { 1, -1 }, { 1, 0 }, { 1, 1 } } };

Stack allocation

The ReversiGameEngine class doesn’t create any “garbage” or heap-allocated objects. The new keyword is never used. The entire game is implemented using only automatic variables which are allocated on the stack and destroyed automatically when they go out of scope. C++ doesn’t have the concept of value types and reference types; you can declare local variables of complex types directly on the stack. For cases when you need to create an object on the heap, so that its lifetime is not tied to its local scope, the C++ standard library provides the shared_ptr<T> and unique_ptr<T> smart pointer types.

The following example shows a variable of std::vector<ReversiSpace>. The variable is default constructed on the stack, and then its methods are invoked using the dot operator. Note that the input parameter ReversiBoard is a typedef (alias) for vector<ReversiSpace>, defined in ReversiGameEngine.h. We use this typedef name whenever we are passing a vector that represents the entire board, as a way of documenting the intent of the code.

vector<ReversiSpace> ReversiGameEngine::GetValidMoveSpaces(
    const ReversiBoard& board, ReversiState  player, size_t& size) const
{  
    vector<ReversiSpace> validSpaces; 
    for (int row = 0; row < m_rowCount; ++row)
    {
        for (int col = 0; col < m_columnCount; ++col)
        {
            ReversiSpace reversiMove(row, col);
            if (IsValidMoveSpace(board, player, reversiMove))
            {
                validSpaces.push_back(reversiMove);
            }
        }
    }

    size += validSpaces.size();
    return validSpaces;     
}

Inside the loop, ReversiSpace objects are constructed using the constructor that takes two ints. Those objects are then copied and the copy is appended to the vector. The original goes out of scope and is destroyed on each inner loop iteration.

When validSpaces is returned to the caller, the Named-Return-Value-Optimization feature in C++ will attempt to avoid making an unnecessary copy of the object, if possible.

Range for vs. foreach

The C# foreach loop is familiar

foreach (var direction in Directions) {... }

In C++ the analogous construct is the range for loop, which is analogous to foreach in C#. auto in C++ is analogous to var in C#. dir is the iteration variable that will successively hold each element in the source container m_Directions. In this example, the iteration variable dir is passed in by reference to avoid making a copy, and const is used to ensure that the element itself is not modified.

for (const auto& dir : m_Directions) {}

Collections and containers

In standard C++ the std::vector<T> class is analogous to the System.Collections.Generic.List<T> object in .NET. std::map<K,T> is analogous to System.Collections.Generic.Dictionary<K,T>. They provides the usual member functions that you would expect. For example, to get the number of elements, you call Moves.Count in C#, or moves.size() in C++.

What makes C++ containers unique is the concept of iterators, which are non-member objects that point to individual elements in the container. You use iterators to loop over all or some specified subrange of elements. You can store iterators to a specific element in a container. Containers have methods that return iterators to the first element and the end, which is one past the last element. In this example, we define a sub-range of elements from another container, as defined by the two iterators that we pass in, the one returned by begin(m_Moves) and by the end variable. We then copy that range of elements into the newMoves vector:

if (turnCount < moveCount)
{
    // ...
    auto end = begin(m_Moves) + turnCount;
    newMoves.assign(begin(m_Moves), end);
    m_Moves.clear();
}

If we don't need to store the subrange of elements in a new vector, we can store iterators to the beginning and end of the subrange in the original vector and just use those as needed. Most functions that operate on containers have an overload that takes two iterators to define the source sequence.

Lambda Expressions

In C#, the input parameters to the lambda expression are located on the left side of the => operator. On the right side is the expression to execute.

var bestValue = moveEvaluations.Max(eval => eval.Item2);

In C++, a lambda expression begins with square brackets that specify which variables to “capture” in the lambda expression. Often this is used to capture the this pointer to enable the lambda to refer to member variables. In this particular snippet no variables are captured and so the brackets are empty. This is followed by parentheses that contain the input parameters. The expression itself is enclosed in curly braces.

auto bestPair = max_element(moveEvaluations.begin(), moveEvaluations.end(),
    [] (const pair<ReversiSpace, int>& elem1, const pair<ReversiSpace, int>& elem2)
{
    return elem1.second < elem2.second;
});

Searching collections

The following sections compare the C# vs. C++ way of performing various tasks in Reversi:

Determine whether a map contains a specified key:

Assume that AllSpaces is a .NET Dictionary type, which has a ContainsKey method:

if (AllSpaces.ContainsKey(boardDimensions)) {...}

The std::map class has a member function find() that returns an iterator that points to the element if a match is found, or the end iterator if no match is found. This is a common pattern in standard library search algorithms.

if (m_allSpaces.find(boardDimensions) == m_allSpaces.end())

Find all the items in a list that match a condition, and copy them into a new collection.

C# can use the LINQ query operator where to find matches in a sequence.

var bestMoves =
   (from moveEvaluation in moveEvaluations
    where moveEvaluation.Item2 == bestValue
    select moveEvaluation.Item1).ToArray();

In this example, moveEvaluations is a std::vector<ReversiState>. We can use a range-based for loop to evaluate elements and copy them into a new vector. We don’t need to convert the new vector to an array as in the C# code, because it is essentially already an array internally.

vector<ReversiSpace> bestMoves;
for (const auto& e : moveEvaluations)
{       
    if (e.second == bestValue)
    {
       bestMoves.push_back(e.first);
    }
}

Find the element with the maximum value:

var bestValue = moveEvaluations.Max(eval => eval.Item2);

std::max_element is a C++ standard library free function, which means it is not defined as a member variable of any class. This overload takes two iterators that specify the range of elements in a container, and the lambda expression specifies a custom comparison function. We use the free functions cbegin and cend to return const iterators, because we are only reading from the source container, not modifying its elements.

auto bestPair = max_element(cbegin(moveEvaluations), cend(moveEvaluations),
    [] (const pair<ReversiSpace, int>& elem1, const pair<ReversiSpace, int>& elem2)
{
    return elem1.second < elem2.second;
});

Determine whether a sequence contains any elements:

GetValidMoveSpaces(board, State.Two).Any()

The std::vector::empty() method returns true if the vector has no elements.

GetValidMoveSpaces(board, ReversiState::Two).empty()

Split a string

In .NET you can use the String.Split method to split a string on a specified separator.

// Example call: game.Move("13,01,00,03,02,23,33")             
foreach (var move in moves.Split(','))
{
    if (move.Equals("--")) 
    {
         await PassAsync();
    }
    else
    {
        var row = Int32.Parse(move[0].ToString());
        var column = Int32.Parse(move[1].ToString());
        await MoveAsync(row, column);
    }
}

In C++, you can use the std::wsregex_token_iterator in a similar way to split strings. You first construct the object, passing in the source string, the regular expression object, and the value -1 to specify that you want to view the entire string from the last separator (or beginning of string) to the current one. After it has been constructed, the iterator points to the beginning of the sequence of tokens (or matches) that were created according to the regular expression. The code then loops over those tokens until the end iterator is reached.

// Example call: game.Move("13,01,00,03,02,23,33") 

// The character to split on.
const wregex r(L",");

// Iterate over each 2-character token in the split string.
for (wsregex_token_iterator i(moves.begin(), moves.end(), r, -1), end; i != end; ++i)
{
    if (*i == L"--")
    {
        Pass();
    }
    else
    {
        // Convert each character to an int.
        wchar_t digit = i->str()[0];
        int row = stoi(&digit);
        digit = i->str()[1];
        int col = stoi(&digit);

        // Perform the move.
        Move(row, col);
    }
}

There are other ways to split strings using regular expressions. This approach is the closest stylistically to C#.

Random Numbers

In .NET, the Random object is used to generate random numbers.

// Member variable
private static readonly Random m_random = new Random();

// Method scope
return bestMoves[_random.Next(bestMoves.Length)];

The C++ standard library provides several random number generators, each with its own distinct characteristics. In ReversiGameEngine we use the std::mt19937mersenne_twister random number generator.

// Member variable
std::mt19937 m_randomGenerator;

// Initialize in class constructor
// by passing in a random_device instance
ReversiGameEngine::ReversiGameEngine() : m_randomGenerator(random_device())
{ ... }

// At method scope:
// Create the distribution with a range
// and call it, passing in the generator
uniform_int_distribution<int> uid(0, len - 1);
return bestMoves[uid(m_randomGenerator)];

Null values

In C# an object reference or a nullable value type can have a value of null.

return MoveAsync((ISpace)null);

In C++/CX a ref class or ref struct (or a nullable value type in VS2013) can have a value of nullptr.

Vector<ISpace^>^ vec = ref new Vector<ISpace^>();
vec->Append(static_cast<ISpace^>(nullptr));

In standard C++, a pointer type may be assigned a value of nullptr.

Obj* p = new Object();
if (p == nullptr) { ... }

In the ReversiGameEngine, we declare all ReversiSpace objects on the stack. A stack-allocated object can’t have a value of nullptr, so we represent a “pass” not as nullptr but as ReversiSpace(-1,-1).

ReversiSpaces ReversiGameEngine::Pass()
{ 
    return Move(ReversiSpace(-1, -1) ); 
}

Conclusion

We’ve highlighted the major differences between the C# and C++ implementations of the Reversi game engine. The rest of the C++ code should be relatively straightforward and easy to read if you have a background in C#.

Reversi sample app

Reversi, a Windows Store game in XAML, C#, and C++

Use the Model-View-ViewModel (MVVM) pattern

Learn how the Reversi sample uses Windows Store app features

Understand the Reversi app structure

Share via

Learn about the Reversi C++ game engine

Background

Packaging standard C++ code

Wrapping standard C++ code in a C++/CX interface

Enabling serialization of C++/CX types in a C# client app

Type conversions

Properties

Asynchronous operations

Exceptions

Comparing C# to standard C++ in the Reversi game engine

Passing by value vs. by reference

Object Initialization

Range for vs. foreach

Collections and containers

Lambda Expressions

Searching collections

Additional resources

Share via

Learn about the Reversi C++ game engine

Background

Packaging standard C++ code

Wrapping standard C++ code in a C++/CX interface

Enabling serialization of C++/CX types in a C# client app

Type conversions

Properties

Asynchronous operations

Exceptions

Comparing C# to standard C++ in the Reversi game engine

Passing by value vs. by reference

Object Initialization

Range for vs. foreach

Collections and containers

Lambda Expressions

Searching collections

Related topics

Additional resources