About a year ago I did some research on the MinMax algorithm and decided to write a basic tic-tac-toe game that uses it. Originally I wrote a connect-4 game that uses it, since you can have a greater level of lookahead with that game. The code that is included with the tic-tac-toe game is a modified version of the code that I used for the connect-4 game. I am including this instead of the connect-4 game because I used different Heuristics for the different AI opponents, and I like to see how they interact with one another. The heuristics are very simple, I did this since tic-tac-toe only needs three levels of lookahead to win. The different heuristics each take a different approach to winning (i.e. defense, offense or even randomness). As I said before this is a very simple game it was only meant to be a study of the MinMax algorithm. I  am posting it to see if anyone would like to optimize the code or make the heuristics better (they are extremely basic at this point). If anyone would like the connect-4 game let me know and I will post it. The attached files have only been tested using g++, I don't think they will compile in Visual C++ or Borland C++. Any questions, comments or corrections are welcome.

bruvel

---

Creating a world: giving form to intention, manifesting a dream, visualizing the unseen...this is a job for the gods, is it not? We are only human, but as we develop this technology and build worlds for individual and social use, we assume certain responsibilities.

Virtual Worlds
- Meredith Bricken

Interesting reading, there is no code attached like you mentioned. Did you have any problem uploading your attachment or perhaps you forgot to upload it?

Thanks

---

Sign-up For Data Mining Source Code Newsletter

I seemed to have a problem uploading it, I am trying to remedy that as we speak.
Thanks,
bruvel

---

Creating a world: giving form to intention, manifesting a dream, visualizing the unseen...this is a job for the gods, is it not? We are only human, but as we develop this technology and build worlds for individual and social use, we assume certain responsibilities.

Virtual Worlds
- Meredith Bricken

I am going to upload the file again, here it is.
bruvel

---

Creating a world: giving form to intention, manifesting a dream, visualizing the unseen...this is a job for the gods, is it not? We are only human, but as we develop this technology and build worlds for individual and social use, we assume certain responsibilities.

Virtual Worlds
- Meredith Bricken

Here is a brief description of what the MinMax algorithm actually does. Basically what the MinMax algorithm does is look ahead to see which move will result in the state with the best possible evaluation function. Our goal is to get the best evaluation function, while our opponents goal is to get the worst evaluation function. The MinMax algorithm does the following steps:
1)Expand game tree as far as possible (look ahead)
2)Evaluate all states of tree
3)Use those states to determine the best move:
4)Choose the move at the root that will lead to the best move.
After each move this is repeated using the current state of the board(in tic-tac-toe for example), until their is a winner or the board is full. This is just a basic outline of how the MinMax algorithm works, I thought I would include this just to help explain how the MinMax algorithm works. If anyone has more they would like to say about the MinMax algorithm, I would certainly like to hear about it. Any questions, comments or correction are welcome.

bruvel

---

Creating a world: giving form to intention, manifesting a dream, visualizing the unseen...this is a job for the gods, is it not? We are only human, but as we develop this technology and build worlds for individual and social use, we assume certain responsibilities.

Virtual Worlds
- Meredith Bricken

Hi Bruvel,

I was going through your code and found some problem in that...I have not actually implemented it but just looked it a bit..

In players you have use some code like

1 if(board[row][col] == selec1 && board[row][col + 1] == selec2 && board[row][col + 2] == selec2) max=400;

  2 if(board[row][col] == selec1 && board[row][col - 1] == selec2 && board[row][col - 2] == selec2) max =400;

    3 if(board[row][col] == selec1 && board[row + 1][col] == selec2 && board[row + 2][col] == selec2)max=400; ................................

9  if(board[row][col] == selec1 && board[row - 1][col] == selec2) max = 950;

10  if(board[row][col] == selec1 && board[row][col - 1] == selec2) max = 950;

11 if(board[row][col] == selec1 && board[row][col + 1] == selec2) max = 950;

These are lines from the player mary...If you see the 1 & 11 line & similarly 2 & 10 line all the cases satisfying line 1 will satisfy line 11 & same with 2 & 10...I guess there should be a break so that if any condition satisfies it will move out of the inner for loop.  just check it

And can you please forward me some good links for MIN-MAX algorithm or other gaming algorithms

Thanks

Maestro

Maestro
Thanks for the heads up on the code, I never noticed that before. I will have to check out the code in more detail. If you have a better implementation for that code, I would love to see it. Your post gives me a good reason to go back over it and see if I can optimize the code, to make the AI characters better. Also here is a link for minmax and other AI related stuff, I think this site does a good job of explaining things.<a href="http://ai-depot.com/LogicGames/MiniMax.html">ai-depot.com</a>.
Thanks,
bruvel

---

Creating a world: giving form to intention, manifesting a dream, visualizing the unseen...this is a job for the gods, is it not? We are only human, but as we develop this technology and build worlds for individual and social use, we assume certain responsibilities.

Virtual Worlds
- Meredith Bricken

Thanks for the Link.

I am working on the game in C#, not yet started the AI part...if I get something better I will definitely post it.

Maestro

Hey u know what? The code is  very good !!

I'm working on a Gomoku implementation and

it would be very helpfull if u upload the connect4 source.

And another thing.I did'nt pay any attention , did you

considered implementing an alpha-beta pruning optimization ?

I really need that connect4 source fast .It would meean the world to me.

take care now !