8
\$\begingroup\$
#include <iostream>
#include <ctime>
#include <numeric>
#include <vector>
#include <functional>
#include <map>
#include <stack>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <memory>

const int initWeight = 100;
const int precCoeff = 50;
const double stepCoeff = 0.65;
const int learningStep = 20;

char gameField[ 9 ];
enum OUTCOME { XS, OS, DRAW, UNFINISHED };

OUTCOME
gameStatus()
{
    static int V[ 8 ][ 3 ] = { { 0, 1, 2 }, { 3, 4, 5 }, { 6, 7, 8 }, { 0, 3, 6 },
                               { 1, 4, 7 }, { 2, 5, 8 }, { 0, 4, 8 }, { 2, 4, 6 } };

    for( int i = 0; i < 8; ++i )
    {
        if( gameField[ V[ i ][ 0 ] ] == gameField[ V[ i ][ 1 ] ] &&
            gameField[ V[ i ][ 0 ] ] == gameField[ V[ i ][ 2 ] ] &&
            gameField[ V[ i ][ 0 ] ] != ' ' )
        {
             return gameField[ V[ i ][ 0 ] ] == 'x' ? XS : OS;
        }
    }

    return ( std::find( gameField, gameField + 9, ' ' ) == gameField + 9 ) ? DRAW : UNFINISHED;
}

void
printField()
{
    std::cout << gameField[ 0 ] << " | " << gameField[ 1 ] << " | " << gameField[ 2 ] << std::endl;
    std::cout << gameField[ 3 ] << " | " << gameField[ 4 ] << " | " << gameField[ 5 ] << std::endl;
    std::cout << gameField[ 6 ] << " | " << gameField[ 7 ] << " | " << gameField[ 8 ] << std::endl;
}

struct TField
{
    char field[ 9 ];

    TField() { std::copy( gameField, gameField + 9, field ); }
    bool operator < ( const TField & rhs ) const
    {
        return std::lexicographical_compare( field, field + 9, rhs.field, rhs.field + 9 );
    }
};

struct TWeight
{
    int weight[ 9 ];
    TWeight() { std::fill( weight, weight + 9, initWeight ); }

};

typedef std::map < TField, TWeight >  DataBaseType;

class Player
{
public:
    Player( char _symbol ) : symbol( _symbol ) {}
    virtual void makeMove() = 0;
    virtual void learn( int ) { }

protected:
    const char symbol;
};

class HumanPlayer : public Player
{
public:
    HumanPlayer( char _symbol ) : Player( _symbol ) {}

    virtual void makeMove()
    {
        while(true)
        {
            int cell;
            std::cin >> cell;
            if(cell < 0 || cell > 8 || gameField[cell] != ' ')
            {
                std::cout << "The current position is occupied or index is out of range!" << std::endl;
                continue;
            }

            gameField[ cell ] = symbol;
            break;
        }
    }
};

class RandomPlayer : public Player
{
public:
    RandomPlayer( char _symbol ) : Player( _symbol ) {}
    virtual void makeMove()
    {
        std::vector < int > v;
        for( int i = 0; i < 9; ++i )
            if( gameField[ i ] == ' ' )
                v.push_back( i );

        gameField[ v[ rand() % v.size() ] ] = symbol;
    }
};

struct WRandmomPolciy
{
    static int getMove(DataBaseType::iterator s)
    {
        const int sum = std::accumulate( s -> second.weight, s -> second.weight + 9, 0 );
        if( sum == 0 )
            return std::find( gameField, gameField + 9, ' ' ) - gameField;

        std::vector < int > coords;
        for( int i = 0; i < 9; ++i )
            std::fill_n( std::back_inserter( coords ), precCoeff * s ->second.weight[ i ] / sum, i );
        return coords[ rand() %  coords.size()];
    }
};


template <class LearningPolciy>
class SmartPlayer : public Player,
                    public LearningPolciy
{
private:
    struct HistoryElement
    {
        DataBaseType::iterator situation;
        int move;
        HistoryElement(DataBaseType::iterator s, int m )
            : situation( s ), move( m ) { }
    };

    typedef std::stack < HistoryElement > HistoryType;

public:
    DataBaseType::iterator getSituation();

public:
    SmartPlayer ( char _symbol ) : Player( _symbol ) {  }
    virtual void makeMove();
    void learn( int step );

private:
    HistoryType history;
    DataBaseType database;
};

template <class LearningPolciy>
DataBaseType::iterator
SmartPlayer<LearningPolciy>::getSituation()
{
   DataBaseType::iterator p = database.find( TField() );
    if( p == database.end() )
    {
        TWeight w;
        for( int i = 0; i < 9; ++i )
            if( gameField[ i ] != ' ' )
                w.weight[ i ] = 0;

        database[ TField() ] = w;
        return database.find( TField() );
    }
    return p;
}

template <class LearningPolciy>
void
SmartPlayer<LearningPolciy>::makeMove()
{
    const DataBaseType::iterator s = getSituation();
    const int move = LearningPolciy::getMove( s );
    gameField[ move ] = symbol;
    history.push( HistoryElement( s, move ) );
}

template <class LearningPolciy>
void
SmartPlayer<LearningPolciy>::learn( int step )
{
    while(!history.empty())
    {
        const HistoryElement h = history.top();
        history.pop();

        TWeight& w = h.situation -> second;

        w.weight[ h.move ] += step;
        if( w.weight[ h.move ] < 0 )
            w.weight[ h.move ] = 0;

        step *= stepCoeff;
    }
}

void
playGame(Player& xp, Player& op, bool verbose)
{
    Player* const cp[] = { &xp, &op };
    int move = 0;
    std::fill( gameField, gameField + 9, ' ' );
    while( gameStatus() == UNFINISHED )
    {
        cp[ move++ % 2 ] -> makeMove();
        if( verbose )
            printField();
    }

    if( gameStatus() == XS )
    {
        xp.learn( learningStep );
        op.learn( -learningStep );
    }
    else if( gameStatus() == OS )
    {
        xp.learn( -learningStep );
        op.learn( learningStep );
    }
}

typedef SmartPlayer<WRandmomPolciy> CompPlayer;

int main()
{
    time_t t;
    srand( ( unsigned )time( &t ) );

    std::auto_ptr<RandomPlayer> r(new RandomPlayer( 'O' ) );
    std::auto_ptr<HumanPlayer> h(new HumanPlayer( 'O' ) );
    std::auto_ptr<CompPlayer> s(new CompPlayer( 'X' ) );

    for( int i = 0; i < 100000; ++i )
        playGame(*s, *r, false);

    playGame(*s.get(), *h, true);
    return 0;
}

Here is the implementation of tic-tac-toe problem. The implementation "remembers" past games and tries to act according to it. But after 100000 games it still "lacks" clever actions. For instance here is the actions of "computer player":

X |   |  
  |   |  
  |   |  
1
X | O |  
  |   |  
  |   |  
X | O | X
  |   |  
  |   | 
\$\endgroup\$
5
\$\begingroup\$

I see a number of things that may help you improve your program.

Fix the bug

The code marks squares with uppercase letters, but the gameStatus code looks for a lowercase x. The result is that the computer incorrectly concludes that O always wins, which obviously throws off the training a bit. That could have been avoided by following the next suggestion.

Eliminate "magic numbers"

Instead of using 'X' and ' ' and 'O' everywhere, create and use three named constants. Similarly, the number 9 occurs many places and could also be a named constant instead.

Don't use auto_ptr

Since C++11, std::auto_ptr is deprecated and it will completely disappear in C++17. Anyway, in this particular case, it adds nothing but complication. Instead of this:

std::auto_ptr<RandomPlayer> r(new RandomPlayer( 'O' ) );
std::auto_ptr<HumanPlayer> h(new HumanPlayer( 'O' ) );
std::auto_ptr<CompPlayer> s(new CompPlayer( 'X' ) );

write this:

RandomPlayer r{'O'};
HumanPlayer h{'O'};
CompPlayer s{'X'};

Note that this uses the C++11 initialization syntax. If your compiler doesn't support that, my first advice would be to update the compiler. Only if that's not possible for some very compelling reason should you limit yourself to C++03 syntax.

Consider using a better random number generator

You are currently using

gameField[ v[ rand() % v.size() ] ] = symbol; 

There are two problems with this approach. One is that the low order bits of the random number generator are not particularly random, so neither is your result. On my machine, there's a slight but measurable bias toward 0 with that. The second problem is that unless RAND_MAX happens to be an integral multiple of v.size(), this will not result in a uniform distribution. A better solution, if your compiler and library supports it, would be to use the C++11 std::uniform_int_distribution.

Think about the cost of objects

The current code includes this object:

struct WRandmomPolciy
{
    static int getMove(DataBaseType::iterator s)
    {
        const int sum = std::accumulate( s -> second.weight, s -> second.weight + 9, 0 );
        if( sum == 0 )
            return std::find( gameField, gameField + 9, ' ' ) - gameField;

        std::vector < int > coords;
        for( int i = 0; i < 9; ++i )
            std::fill_n( std::back_inserter( coords ), precCoeff * s ->second.weight[ i ] / sum, i );
        return coords[ rand() %  coords.size()];
    }
};

The ultimate effect of this is to create a potentially huge vector just to select one entry and throw the rest away. This is a very inefficient way to do things, in addition to the problem with the random number mentioned earlier. The goal, as I understand it, is to select a move with a probability proportional to its weight. There's a very direct and efficient way to do that in C++11 using std::discrete_distribution

class SmartPolicy
{
public:
    int getMove(DataBaseType::iterator s)
    {
        const auto &w = s->second.weight;
        std::discrete_distribution<> dist(w.begin(), w.end());
        return dist(gen);
    }
private:
    std::mt19937 gen;
}

Note that in my version, TWeight is now a std::array<int, 9>.

Eliminate global variables where practical

The code declares and uses several global variables. Global variables obfuscate the actual dependencies within code and make maintainance and understanding of the code that much more difficult. It also makes the code harder to reuse. For all of these reasons, it's generally far preferable to eliminate global variables and to instead pass pointers to them. That way the linkage is explicit and may be altered more easily if needed. The constants are not so bad, but gameField really should be inside of main rather than global.

Use objects

The gameField has both data and logic associated with it. This strongly suggests an object. I'd propose something like this:

class GameField {
public:
    enum OUTCOME { XS, OS, DRAW, UNFINISHED };
    GameField::OUTCOME gameStatus() const;
    void print() const;
    void play(Player& xp, Player& op, bool verbose);
    bool move(int location, char symbol);
    bool occupied(int location) const;
    int firstFree() const;
    friend TField;
private:
    char gameField[ 9 ];
};

Naturally, you'll have to also adjust places within the code which assume access to a global variable.

Use better variable names

The variable name gameField is good, but the name s is not. The first name explains something about what the variable means within the context of the code, but the latter is too short to convey much of anything.

Think about the user

It's not immediately obvious to the human player that the machine is expecting input, nor is it obvious that it numbers the squares starting with zero. A little explanatory message would be nice for the user.

Fix spelling errors

The code has WRandmomPolciy instead of RandomPolicy and LearningPolciy instead of LearningPolicy. These kinds of typos don't bother the compiler at all, but they will bother human readers of the code and make it a little more difficult to understand and maintain.

Don't use std::endl if you don't really need it

The difference betweeen std::endl and '\n' is that '\n' just emits a newline character, while std::endl actually flushes the stream. This can be time-consuming in a program with a lot of I/O and is rarely actually needed. It's best to only use std::endl when you have some good reason to flush the stream and it's not very often needed for simple programs such as this one. Avoiding the habit of using std::endl when '\n' will do will pay dividends in the future as you write more complex programs with more I/O and where performance needs to be maximized.

Omit return 0

When a C or C++ program reaches the end of main the compiler will automatically generate code to return 0, so there is no need to put return 0; explicitly at the end of main.

Note: when I make this suggestion, it's almost invariably followed by one of two kinds of comments: "I didn't know that." or "That's bad advice!" My rationale is that it's safe and useful to rely on compiler behavior explicitly supported by the standard. For C, since C99; see ISO/IEC 9899:1999 section 5.1.2.2.3:

[...] a return from the initial call to the main function is equivalent to calling the exit function with the value returned by the main function as its argument; reaching the } that terminates the main function returns a value of 0.

For C++, since the first standard in 1998; see ISO/IEC 14882:1998 section 3.6.1:

If control reaches the end of main without encountering a return statement, the effect is that of executing return 0;

All versions of both standards since then (C99 and C++98) have maintained the same idea. We rely on automatically generated member functions in C++, and few people write explicit return; statements at the end of a void function. Reasons against omitting seem to boil down to "it looks weird". If, like me, you're curious about the rationale for the change to the C standard read this question. Also note that in the early 1990s this was considered "sloppy practice" because it was undefined behavior (although widely supported) at the time.

So I advocate omitting it; others disagree (often vehemently!) In any case, if you encounter code that omits it, you'll know that it's explicitly supported by the standard and you'll know what it means.

\$\endgroup\$
  • 2
    \$\begingroup\$ Okay, but what about the main problem that bothers the OP - the lack of cleverness in the computer actions? \$\endgroup\$ – Erel Segal-Halevi Feb 25 '17 at 18:36
  • 1
    \$\begingroup\$ The main reason for that is a bug in the gameStatus code. It looks for lowercase x but actually marks squares with an uppercase X. I'll add that to the answer. \$\endgroup\$ – Edward Feb 25 '17 at 19:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.