Saturday, June 18, 2016

Data Generation for Tic-Tac-Toe Game : Example of Recursion in C++


Problem Statement: I need to generate data set for a 3x3 Tic-Tac-Toe Game. In this game, there are 9 Cells and each can take one of the values in the set {0, 1, 2}. Where 0 denotes and empty cell while 1 and 2 correspond to each of the two players.  So, we need to generate a 9x1 state vector where each element can have one of three possible states. Total number of states is 3^9 = 19683.


I have written a generic program that can generate such datasets irrespective of their dimension or possible state values:

We use a function to remove redundant vectors.


#include <iostream>
#include <fstream>
#include <cmath>

using namespace std;

#define N 3
#define M 3
#define MAX 20000
int Data[MAX][N];

std::ofstream f1("dataset2.txt");
//-------------------------------------------

bool find_match(int state[N], int rowcnt)
{
  for(int q = 0; q < rowcnt; q++)
  {
    int simcnt = 0;
    for(int r = 0; r < N; r++)
    {
      if(Data[q][r] == state[r])
        simcnt++;
    }

    if(simcnt == N)
      return true;
  }

  return false;
}

//------------------------------------

void add_row(int state[N], int rowcnt)
{

  for(int r = 0; r < N; r++)
    Data[rowcnt][r] = state[r];
}

//-----------------------------------------

void genstate(int state[], int k, int &rowcnt)//, char *filename)
{

  bool mFlag = false;
  for(int l = k; l < N; l++)
  {
    for(int j = 0; j < M; j++)
    {
      state[k] = j;

      mFlag = find_match(state, rowcnt);
      if(mFlag == false)
      {
        add_row(state, rowcnt);
        rowcnt++;
        for(int p = 0; p < N; p++)
          f1 << state[p] << "\t";
        f1 << endl;
      }
      genstate(state, k+1,rowcnt);

    }           
  }

 // f1.close();
}

//-------------------------

int main()
{
  int state[N];
  for(int i = 0; i < N; i++)
    state[i] = 0;

  int rowcnt = 0;

  genstate(state, 0, rowcnt);//, "dataset.txt");

  f1.close();

  return 0;
}


       
 

No comments:

 
pre { margin: 5px 20px; border: 1px dashed #666; padding: 5px; background: #f8f8f8; white-space: pre-wrap; /* css-3 */ white-space: -moz-pre-wrap; /* Mozilla, since 1999 */ white-space: -pre-wrap; /* Opera 4-6 */ white-space: -o-pre-wrap; /* Opera 7 */ word-wrap: break-word; /* Internet Explorer 5.5+ */ }