Jump to content

  • Log In with Google      Sign In   
  • Create Account

FREE SOFTWARE GIVEAWAY

We have 4 x Pro Licences (valued at $59 each) for 2d modular animation software Spriter to give away in this Thursday's GDNet Direct email newsletter.


Read more in this forum topic or make sure you're signed up (from the right-hand sidebar on the homepage) and read Thursday's newsletter to get in the running!


more tic tac toe


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
31 replies to this topic

#1 phil67rpg   Members   -  Reputation: 767

Like
0Likes
Like

Posted 11 October 2012 - 03:55 PM

I am still working on my tic tac toe game using c++.What I want to do is check an array of characters for X's or O's.If it finds an X or O then it generates another O.It checks the array until it finds an empty spot and then puts an O in that spot.
here is the code I am working on.
if(board[player_O]!='X' && board[player_O]!='O')
{
  board[player_O]='O';
}
else
{
  player_O_two=rand()%9+1;
}

if(player_O_two==player_O)
{
  player_O=rand()%9+1;
  board[player_O]='O';
}
I only need a small hint.

Sponsor:

#2 Álvaro   Crossbones+   -  Reputation: 13934

Like
0Likes
Like

Posted 11 October 2012 - 05:06 PM

I don't understand the description in English of what you are trying to do. Perhaps you can try to explain it with an example?

#3 phil67rpg   Members   -  Reputation: 767

Like
0Likes
Like

Posted 11 October 2012 - 05:25 PM

ok I am trying to check for a empty spot on a tic tac toe board and then put an X or O in that spot.I dont want the computer to put a O in an already occupied spot.

#4 Álvaro   Crossbones+   -  Reputation: 13934

Like
0Likes
Like

Posted 11 October 2012 - 05:44 PM

One reasonable method consist of making a list of the empty spaces, then pick a random one from those.

Do you need to see code for that?

#5 phil67rpg   Members   -  Reputation: 767

Like
0Likes
Like

Posted 11 October 2012 - 06:46 PM

cool yes a little bit of code would help.

#6 Álvaro   Crossbones+   -  Reputation: 13934

Like
0Likes
Like

Posted 11 October 2012 - 07:35 PM

There you go:
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <vector>

enum Piece {Empty, Cross, Nought};

class Board {
  Piece array[9];
 
public:
  Board() {
    for (int i=0; i<9; ++i)
	  array[i] = Empty;
  }
 
  void make_move(int square, Piece piece) {
    array[square] = piece;
  }
 
  int pick_random_empty_square() {
    std::vector<int> empties;
    empties.reserve(9);
    for (int i=0; i<9; ++i) {
	  if (array[i] == Empty)
	    empties.push_back(i);
    }
   
    int random_index = std::rand() % empties.size();
   
    return empties[random_index];
  }
 
  friend std::ostream &operator<<(std::ostream &os, Board const &board);
};
 
std::ostream &operator<<(std::ostream &os, Board const &board) {
  for (int row=0; row<3; ++row) {
    for (int col=0; col<3; ++col)
	  os << "_XO"[board.array[3*row+col]] << ' ';
    os << '\n';
  }
  return os;
}

int main() {
  std::srand(std::time(0));
 
  Board board;
 
  for (int i=0; i<9; ++i) {
    board.make_move(board.pick_random_empty_square(), i%2==0 ? Cross : Nought);
    std::cout << board << '\n';
  }
}


#7 littletray26   Members   -  Reputation: 267

Like
0Likes
Like

Posted 18 October 2012 - 03:28 PM

If all you're actually trying to do is find the first empty space and replace it with an O then this would do it:


//Set all spaces to ' ' when you initialize the board
for (int i = 0; i < 8; ++i)     //Where 8 is the size of the board
{
     board[i] = ' ';
}

//Then when you're wanting to replace the first empty space wth 'O'
for (int i = 0; i < 8; ++i)
{
     if (board[i] == ' ')
         board[i] = 'O'; 
}

The majority of Internet Explorer users don't understand the concept of a browsing application, or that there are options.
They just see the big blue 'e' and think "Internet". The thought process usually does not get much deeper than that.

Worms are the weirdest and nicest creatures, and will one day prove themselves to the world.

I love the word Clicky :)

#8 arkane7   Members   -  Reputation: 213

Like
2Likes
Like

Posted 19 October 2012 - 10:22 AM

If all you're actually trying to do is find the first empty space and replace it with an O then this would do it:

//Set all spaces to ' ' when you initialize the board
for (int i = 0; i < 8; ++i)	 //Where 8 is the size of the board
{
	 board[i] = ' ';
}
//Then when you're wanting to replace the first empty space wth 'O'
for (int i = 0; i < 8; ++i)
{
	 if (board[i] == ' ')
		 board[i] = 'O';
}



if you do not put a break in that if statement, it will change ALL empty spaces into O's, rather than the first one you find

If (board[i] =='')
{
board [i] = 'O';
break;
}

that way only one empty is changed

also i think you may want 9 instead of 8; arent there 9 tiles in TTT?

Edited by arkane7, 19 October 2012 - 10:26 AM.

Always improve, never quit.

#9 littletray26   Members   -  Reputation: 267

Like
0Likes
Like

Posted 21 October 2012 - 03:19 AM


If all you're actually trying to do is find the first empty space and replace it with an O then this would do it:

//Set all spaces to ' ' when you initialize the board
for (int i = 0; i < 8; ++i)	 //Where 8 is the size of the board
{
	 board[i] = ' ';
}
//Then when you're wanting to replace the first empty space wth 'O'
for (int i = 0; i < 8; ++i)
{
	 if (board[i] == ' ')
		 board[i] = 'O';
}



if you do not put a break in that if statement, it will change ALL empty spaces into O's, rather than the first one you find

If (board[i] =='')
{
board [i] = 'O';
break;
}

that way only one empty is changed

also i think you may want 9 instead of 8; arent there 9 tiles in TTT?


You're right, I forgot to put that break in there. Thank you for correcting that :)

Also, 0 is counted as a space so in an 8 space array there is in fact 9 spaces.


If all you're actually trying to do is find the first empty space and replace it with an O then this would do it:

//Set all spaces to ' ' when you initialize the board
for (int i = 0; i < 8; ++i)	 //Where 8 is the size of the board
{
	 board[i] = ' ';
}
//Then when you're wanting to replace the first empty space wth 'O'
for (int i = 0; i < 8; ++i)
{
	 if (board[i] == ' ')
		 board[i] = 'O';
}



if you do not put a break in that if statement, it will change ALL empty spaces into O's, rather than the first one you find

If (board[i] =='')
{
board [i] = 'O';
break;
}

that way only one empty is changed

also i think you may want 9 instead of 8; arent there 9 tiles in TTT?


The majority of Internet Explorer users don't understand the concept of a browsing application, or that there are options.
They just see the big blue 'e' and think "Internet". The thought process usually does not get much deeper than that.

Worms are the weirdest and nicest creatures, and will one day prove themselves to the world.

I love the word Clicky :)

#10 phil67rpg   Members   -  Reputation: 767

Like
0Likes
Like

Posted 21 October 2012 - 03:49 PM

is there anyway I can generate a random number only once and do not have it repeat.

#11 Bacterius   Crossbones+   -  Reputation: 9304

Like
2Likes
Like

Posted 21 October 2012 - 04:04 PM

is there anyway I can generate a random number only once and do not have it repeat.

If you mean produce a sequence of numbers where no number is repeated, like 3, 1, 9, 5, 2, 4, ... then sure, it's very easy:

1. generate an array [0, 1, 2, 3, 4, ... as much as you need, pretty much put the numbers you want in there]
2. for each element A in the array...
----> select a random element B in the array
----> swap elements A and B
3. iterate through the modified array to get your repeat-free random numbers

See Fisher-Yates shuffle. Is this what you meant?

Edited by Bacterius, 21 October 2012 - 04:05 PM.

The slowsort algorithm is a perfect illustration of the multiply and surrender paradigm, which is perhaps the single most important paradigm in the development of reluctant algorithms. The basic multiply and surrender strategy consists in replacing the problem at hand by two or more subproblems, each slightly simpler than the original, and continue multiplying subproblems and subsubproblems recursively in this fashion as long as possible. At some point the subproblems will all become so simple that their solution can no longer be postponed, and we will have to surrender. Experience shows that, in most cases, by the time this point is reached the total work will be substantially higher than what could have been wasted by a more direct approach.

 

- Pessimal Algorithms and Simplexity Analysis


#12 phil67rpg   Members   -  Reputation: 767

Like
0Likes
Like

Posted 21 October 2012 - 04:07 PM

yes thanks

#13 Bacterius   Crossbones+   -  Reputation: 9304

Like
2Likes
Like

Posted 21 October 2012 - 04:09 PM

Note the algorithm I posted is the naive, inefficient one. The correct one is given on Wikipedia and is much faster:

[source lang="plain"]To shuffle an array a of n elements (indices 0..n-1): for i from n − 1 downto 1 do j ← random integer with 0 ≤ j ≤ i exchange a[j] and a[i][/source]

The slowsort algorithm is a perfect illustration of the multiply and surrender paradigm, which is perhaps the single most important paradigm in the development of reluctant algorithms. The basic multiply and surrender strategy consists in replacing the problem at hand by two or more subproblems, each slightly simpler than the original, and continue multiplying subproblems and subsubproblems recursively in this fashion as long as possible. At some point the subproblems will all become so simple that their solution can no longer be postponed, and we will have to surrender. Experience shows that, in most cases, by the time this point is reached the total work will be substantially higher than what could have been wasted by a more direct approach.

 

- Pessimal Algorithms and Simplexity Analysis


#14 dAND3h   Members   -  Reputation: 214

Like
0Likes
Like

Posted 21 October 2012 - 04:18 PM

Also, 0 is counted as a space so in an 8 space array there is in fact 9 spaces.


How can there be 9 spaces in an array of size 8? That makes no sense.

Arkane7 was correct. You will need to change that 8 to a 9. Otherwise, you can change the < sign to <= .

#15 phil67rpg   Members   -  Reputation: 767

Like
0Likes
Like

Posted 21 October 2012 - 04:19 PM

well i have found an algorithm that might work
#include <iostream>
#include <ctime>
using namespace std;
bool isContained(int arr[],int n,int x)
{
for(int i=0;i<n;i++)
{
  if(arr[i]==x)
   return true;
}
return false;
}
int main()
{
srand(time(0));
const int x = 100;
int r[x];
for(int i=0;i<x;i++)
{
  r[i]=1+rand()%x;
  while(isContained(r,i,r[i]))
  {
   r[i]=1+rand()%x;
  }
}
for(int i=0;i<x;i++)
  cout<<r[i]<<"\n";
cout<<"\n\n";
return 0;
}


#16 Bacterius   Crossbones+   -  Reputation: 9304

Like
1Likes
Like

Posted 21 October 2012 - 04:31 PM

That is slow. I gave a link to the proper algorithm in my last post - why not use it? Since you want code:

[source lang="cpp"]#include < iostream>#include < cstdlib>#include < ctime>using namespace std;void fisherYates(int array[], int length){ /* Go over each element backwards. */ for (int t = length - 1; t != 0; t--) { /* Select random element in [0..t] */ int r = rand() % (t + 1); /* Swap them. */ int tmp = array[t]; array[t] = array[r]; array[r] = tmp; }}int main(){ /* Randomize. */ srand(time(0)); /* Prepare array of N elements. */ const int length = 20; int array[length]; /* Initialize it. */ for (int t = 0; t < length; ++t) array[t] = t; /* Shuffle. */ fisherYates(array, length); /* Print out array. */ for (int t = 0; t < length; ++t) cout < < array[t] < < " "; cout < < endl;}[/source]

(remove spaces between << as the source tags munch'em apparently)

Edited by Bacterius, 21 October 2012 - 04:58 PM.

The slowsort algorithm is a perfect illustration of the multiply and surrender paradigm, which is perhaps the single most important paradigm in the development of reluctant algorithms. The basic multiply and surrender strategy consists in replacing the problem at hand by two or more subproblems, each slightly simpler than the original, and continue multiplying subproblems and subsubproblems recursively in this fashion as long as possible. At some point the subproblems will all become so simple that their solution can no longer be postponed, and we will have to surrender. Experience shows that, in most cases, by the time this point is reached the total work will be substantially higher than what could have been wasted by a more direct approach.

 

- Pessimal Algorithms and Simplexity Analysis


#17 phil67rpg   Members   -  Reputation: 767

Like
0Likes
Like

Posted 21 October 2012 - 04:58 PM

cool thanks

#18 phil67rpg   Members   -  Reputation: 767

Like
0Likes
Like

Posted 21 October 2012 - 06:43 PM

I have tried fisherYates shuffle but it still does not work.here is my code

void Computer::move_player_O()
{
srand(time(NULL));

const int length=10;
int array[length];
for(int t=1;t<=9;t++)
array[t]=t;
fisherYates(array,length);
player_O=array[t];
t++;
}


void Computer::check_player_O()
{
board[player_O]='O';
}


#19 Bacterius   Crossbones+   -  Reputation: 9304

Like
2Likes
Like

Posted 21 October 2012 - 06:57 PM

Why are you incrementing t again inside the loop... the t++ inside the for construct already takes care of that :(

The slowsort algorithm is a perfect illustration of the multiply and surrender paradigm, which is perhaps the single most important paradigm in the development of reluctant algorithms. The basic multiply and surrender strategy consists in replacing the problem at hand by two or more subproblems, each slightly simpler than the original, and continue multiplying subproblems and subsubproblems recursively in this fashion as long as possible. At some point the subproblems will all become so simple that their solution can no longer be postponed, and we will have to surrender. Experience shows that, in most cases, by the time this point is reached the total work will be substantially higher than what could have been wasted by a more direct approach.

 

- Pessimal Algorithms and Simplexity Analysis


#20 phil67rpg   Members   -  Reputation: 767

Like
0Likes
Like

Posted 21 October 2012 - 07:08 PM

ok i took the t++ out but it still does not work,I am so close to fihishing,any more help would be great.




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS