Info about Making a Game AI

[Nisheeth]

I wanted to know what all do I need to know in order to make a simple AI(in a console program).
I was trying to make a Tic-Tac-Toe for honing my C++ skills.
Now I have done every-thing I need apart from create the computer's moves.
I wanted to make an AI to do that, basically so that It may properly understand where to make the move without me having to define every possibility.

[anonymous23323124]

When I created a noughts and crosses game, I had a second, virtual, board, and I had the AI try each move of its on there to check for victory. If it found a move that it could win with, it did that.

If it couldn't find a winning move, it did the same again for the opponent's moves to see if there were any moves that would make it lose. If so it blocked one.

Failing both of these, I just had it choose a random empty square, because I didn't want to spend too much time on it. However, you could, I suppose, try letting the AI go 'two moves into the future', although things would quickly get complicated as it would have to predict the opponent's move.

Disclaimer: This is the way I implemented it, but I am sure there are many better approaches, so please no-one get annoyed at me for this (perhaps inefficient) one...

PS: You might want to change the title to "Info about Making a game AI". When I saw it, I immediately thought "chatbot" ;)

[Nisheeth]

This is how I make my original grid.

char Grid_pos [3][5] = 
{
        {' ','|',' ','|',' '},
        {' ','|',' ','|',' '},
        {' ','|',' ','|',' '}
};
//...............................
//...............................
for (int i = 0;i < 3; i++)
{
	cout <<" "<< i+1 <<"  ";
	    for (int j = 0; j < 5;j++)
	    {
	        cout << Grid_pos[i][j];
	    }
	cout <<  endl;
	if ( i == 2)
	{
		break;
	}
	cout << "    -|-|-\n";
}

Now I should create another array, of dimensions 3 X 3, and make the changes appear in both of them.
Then create if statements to check for possible moves.
Will this be a good method?

And I don't know how to make an AI, that was my first question:

What topics must I know before I will be able to fully understand and make an AI?

[z05DSL3A]

What topics must I know before I will be able to fully understand and make an AI?

First define what you mean by AI. In the above you talk about a computer player for tic-tac-toe, this can be written with a simple eight step (max) decision making process that you will not be able to best. Then there is something at the other end to the scale where you tell it what the rules of the game are and let it learn how to 'play' and I may learn the strategy to be unbeatable.

[Nisheeth]

By AI I mean that I put up the basic conditions for the game and the computer uses them to play the game at a level near a human player.

In the above you talk about a computer player for tic-tac-toe, this can be written with a simple eight step (max) decision making process that you will not be able to best.

Could you please tell give me help in defining those steps?

[z05DSL3A]

Could you please tell give me help in defining those steps?

See strategy in http://en.wikipedia.org/wiki/Tic-tac-toe

[ultifinitus]

I was excited when I read this

Then there is something at the other end to the scale where you tell it what the rules of the game are and let it learn how to 'play' and I may learn the strategy to be unbeatable.

But then...

[Nisheeth]

Well, I had devised 5 of those strategies myself, but I couldn't put them in definite terms (in C++ coding). i.e. I couldn't make the computer understand what a fork(I didn't know it by that name) is, or how to identify one before it is actually made. Nor could I define how to make the PC attempt to make a fork.
Any help?

[z05DSL3A]

Top of my head:
A 'fork' would be an empty location where the number of rows, columns, and/or diagonals that intersect that location, having one occupied location, is greater than 1.

First analyse the lines and give them a ranking.
three unoccupied locations = empty line
two unoccupied locations = potential line
one unoccupied location, with both occupied locations the same side = winning line
one unoccupied location, with each occupied locations on sides = lost line
no unoccupied locations = full line.

If you find a winning line for you, the move is the unoccupied location.
if you find a winning line the them, the move is the unoccupied location.
If you find two(or more) potential lines (for you) whos intersection is an unoccupied location, the move is the intersection point.
Same as above for the other side....
and so on.

[quirkyusername]

a minimax search is perfect for this. read up on minimax.

What grey wolf just posted is a heuristic function, a way of summarising how strong a current board position is, this is needed for larger games where you can't possibly predict every possible move, but I'm pretty sure you won't even need a heuristic as tic tac toe is small enough to just compute every possible move.

[Nisheeth]

@quirkyusername:
As per the Wikipedia article Grey Wolf posted

Ignoring the sequence of Xs and Os, and after eliminating symmetrical outcomes (i.e. rotations and/or reflections of other outcomes), there are only 138 unique outcomes.

So I assume writing 138 conditions is also a very large.

I read the minimax theorem. Didn't understand anything about it, or how this will be useful in this condition.

[ultifinitus]

@nisheeth: I think you misunderstood.

If by conditions you mean writing out if statements for each permutation, I agree that's nuts. However he could simply write a program to precompute all possible combinations, and store that in a file, to be read in later.

Minimax in this case would be useful because you could assign points to certain moves. Such as

-0-
-0-
x-x

the bottom middle would have lotsa points =]

[Nisheeth]

For the first part, ah good idea, just little too much work!

Minimax in this case would be useful because you could assign points to certain moves. Such as

-0-
-0-
x-x

the bottom middle would have lotsa points =]

The point is I didn't understand what is the Minimax Theorem!! So I didn't understand what this means either. :(

[kev82]

It probably won't help as it's not very clear, but to try and avoid my big pile of marking, I've just had a go at this. It needs to be massively tidied up.

The principle is similar to minimax, but the recursion is a little different.

It assumes `x' goes first. For any given board position, it will return the location (row then col) you should go to not lose. If no matter where you go, you will lose, it will return -1, -1.

You should enter the board position as a nine character string from top to bottom, then left to right. So

x| | 
 | | 
 | |o

would be x       o

It makes no attempt to win, it just picks the first move it finds that won't lose. I leave making it want to win as an exercise.

#include <iostream>
#include <utility>
#include <vector>

class Board
{
public:
	typedef enum {s_empty=0, s_isx=1, s_iso=2} Square;
private:
	int board_;

	Square nextPlayer() const {
		int played = 0;
		int temp = board_;
		while(temp>0) {
			if(temp%3 != 0) ++played;
			temp /= 3;
		}
		if(played%2 == 0) return s_isx;
		return s_iso;
	}
public:
	Board() : board_(0) {}

	Board(const std::string &s) {
		Board b;
		std::vector<std::pair<int,int> > x,o;
		for(int row=0;row!=3;++row) {
			for(int col=0;col!=3;++col) {
				int idx = row*3+col;
				if(s[idx] == 'x') {
					x.push_back(std::pair<int,int>(row,col));
				}
				if(s[idx] == 'o') {
					o.push_back(std::pair<int,int>(row,col));
				}
			}
		}

		while(!x.empty()) {
			b.move(x.back().first, x.back().second);
			x.pop_back();

			if(o.empty()) continue;
			b.move(o.back().first, o.back().second);
			o.pop_back();
		}

		*this = b;
	}

	Square operator()(int row, int col) const {
		int idx = row*3 + col;
		int mask = 1;
		while(--idx >= 0) mask *= 3;
		return Square((board_/mask)%3);
	}

	bool lost() {
		Square nm = nextPlayer();
		nm = Square(3 - int(nm));

		Board &b = *this;

		if(b(0,0) == nm && b(0,1) == nm && b(0,2) == nm) return true;
		if(b(1,0) == nm && b(1,1) == nm && b(1,2) == nm) return true;
		if(b(2,0) == nm && b(2,1) == nm && b(2,2) == nm) return true;

		if(b(0,0) == nm && b(1,0) == nm && b(2,0) == nm) return true;
		if(b(0,1) == nm && b(1,1) == nm && b(2,1) == nm) return true;
		if(b(0,2) == nm && b(1,2) == nm && b(2,2) == nm) return true;

		if(b(0,0) == nm && b(1,1) == nm && b(2,2) == nm) return true;
		if(b(2,0) == nm && b(1,1) == nm && b(0,2) == nm) return true;

		return false;
	}

	void move(int row, int col) {
		int nm = nextPlayer();
		int idx = row*3 + col;

		while(--idx >= 0) nm *= 3;
		board_ += nm;
	}

	operator int () const {
		return board_;
	}

	static std::pair<int, int> findMove(Board b) {
		static bool calculated[20000];
		static bool canWin[20000];
		static std::pair<int,int> move[20000];
		bool init = false;

		if(!init) {
			for(int i=0;i!=20000;++i) calculated[i] = false;		
			init = true;
		}

		if(calculated[b]) return move[b];

		std::pair<int,int> &m = move[b];

		if(b.lost()) {
			m.first = -1;
			m.second = -1;
			canWin[b] = false;
			calculated[b] = true;
			return m;
		}

		for(int row=0;row!=3;++row) {
			for(int col=0;col!=3;++col) {
				if(b(row,col) == Board::s_empty) {
					Board temp = b;
					temp.move(row, col);
					findMove(temp);
					if(canWin[temp] == false) {
						m.first = row;
						m.second = col;
						canWin[b] = true;
						calculated[b] = true;
						return m;
					}
				}
			}
		}

		m.first = -1;
		m.second = -1;
		canWin[b] = false;
		calculated[b] = true;
		return m;
	}
};

				
int main() {
	std::string board;
	std::getline(std::cin, board);

	Board b(board);

	std::pair<int, int> move = Board::findMove(b);
	std::cout << move.first << " " << move.second << std::endl;

	return 0;
}

[Nisheeth]

What does the above code do? BTW, I haven't understood Classes. The most I have used are Data structures, that too to a very basic level. Nor have I properly understood using Vectors.
And can someone please explain what is the minimax?

Also my prototype of my code is:

//Declerations:
int main ()
{
    //Decleration of the board (It can be seen in the third post)
    //Instructions of the Game, and How to play it in the console.
    //An user input for the number of Players (Against PC or friend)
    //A for loop that will loop 9 times.
    //The printing of the board (Also in the third post)
    //The conditions for checking whether a player has actually won:
        if ((Grid_pos[0][0] == 'X' && Grid_pos[1][2] == 'X' && Grid_pos[2][4] == 'X') || (Grid_pos[0][4] == 'X' && Grid_pos[1][2] == 'X' && Grid_pos[2][0] == 'X'))
        {
	cout << "\nConratulations "<< name_player2 <<", You have won the Game!!\n";
	break;
        }
        // This was for Diagonals, three more for the three pairs of sides and a similar set for the other player.
    //Conditions for different player modes (Computer mode doesn't work yet. The followin goes directly to the two player mode):
    //For two players:
    cout << "Please put up your move. Format: ROW-numberColumn-number [like 11, 12...]";
    if (x%2 != 0 && player_num == 2)
    {
        cin >> Player_pos;
        //Condition for putting up a character in the board:
        switch (Player_pos)
        {
        case 11: 
	if (Grid_pos [0][0] == ' ') {Grid_pos [0][0] = 'X';} //To check whether the move was in a legal position
	else {cout << "\nYou made an illegal move.Hence your turn was skipped.";}
	break;
              //Nine conditions for both the players.
        }
cout << endl << endl;
system ("PAUSE");
return 0;
}

As you will see the code is very long (319 lines, and nothing about how the computer plays!)

[kev82]

My code if you run it, will tell you for a given board position, where the player should move in order not to lose.

For example if you enter the following position

x|x|o
 | |
o| |

xxo   o  

The program will return 1 1, to tell you x should play in the middle square.

By the sounds of it, both the algorithm and implementation may be a little beyond you at the moment. You may be better to implement the heuristic suggested by someone earlier in the thread.

(I'm not sure if this will make sense to you)

Minimax is recursion based technique where you have two agents battling each other. The first agent is trying to decide what action to take that will minimize the damage done by the second agent. The second agent is trying to maximize the damage he does. So the first agent is MINImizing the MAXimum damage. In the simplest technique the first agent does this by brute forcing all the options and calling itsself recursively.

[Nisheeth]

That makes a lot more sense that the one in Wikipedia (probably because of its uber-technical language).
So in this case, the computer should Aim at Maximizing the damage to the player(playing the offensive)?

[kev82]

Well the key to this is recursion

Agent 1 is trying to minimize the damage that agent 2 will do
To calculate agent 2's move, it tries to minimize the damage that agent 1 would do next move
To calcualte agent 1's move, it tries to minimize the damage that agent 2 would do the move after
...
...
and so on

until there is a case where the exact damage can be calculated.

In minimax the computer is taking on the role of both players.

[quirkyusername]

this page explains minimax pretty well, and has pseudocode. It's what I used to help me understand minimax for my connect four agent and for your tic tac toe agent it wouldnt even need the part where it checks for a maximum search depth and returns the score from the heuristic.

http://www.fierz.ch/strategy1.htm

[Nisheeth]

The explanation is good, but it confuses me after the part of deceleration of the board.
So I will try something easier.
For Now I will try making a virtual board and just a simple placement code. I will continue into making it better later.

EDIT:
I tried to make an algorithm to check if a block is empty, and if it is not, to look for another random move.
The code had this structure:

void Comp_move()
{
    int *comps_move;
    comps_move = new int [1];
    comps_move = rand()%9;
    
    switch (comps_move)
    {
        case 0: if (Grid_pos [0][0] == ' ') {Grid_pos[0][0] = 'O'}
                    else {
                                delete[] comps_move;
                                Comp_move();
                            }
        break;
    //......Similarly for other 8 positions
    delete[] comps_move;
    }
}

Now I used a function because it allowed recursion. But hoping to prevent a stack overflow, I decided to use dynamic memory, and delete the allocated memory every time I call a recursion.
But it yet gave an stack overflow error.

So any help on how can I make a random move playing computer player?

NOTE: There may be some errors in the above code since I wrote it again just now (having deleted it from the IDE earlier), but the code was working, since the program compiled without errors