[OT] Looking for algorithm

  • Thread starter Thread starter Chris Dunaway
  • Start date Start date
C

Chris Dunaway

I am posting this here because I think someone here will either know
the answer or know a better place for me to ask this question.

I am looking for an algorithm to provide AI for a Tic Tac Toe (aka
Naughts and Crosses) style game. But not necessarily for Tic Tac
Toe.

I'm looking for an algorithm that can evaluate and arbitrary sized
board with an arbitrary win condition. So for example, tic tac toe is
a 3 by 3 board with a win condition of 3 in a row.

I need an algorithm for an m by n board with a win condition of x in a
row where x <= m and x <= n.

Does that make any sense?

I don't just want code (but I'll take anything I can get), I want to
learn the algorithm. This is for my own private project.

Does anyone have such an algorithm or know a good resource where I
could learn about such algorithms?

Thanks,

Chris
 
Chris,

Are you trying to determine whether or not, given a board with X and O's
on it, someone has won? If so, that's pretty simple.

All you have to do is analyze two edges that are perpindicular to each
other, as well as diagonals from two corners on the same edge.

So, you would cycle through the top edge. In the first cell, if there
is a mark, then you would analyze the cells beneath the top edge to see if
they possesed the same mark. If you find that condition, you know that the
player with that mark has one. If any cell does not contain the mark in the
top row, then you move to the next column.

You then do the same thing horizontally against a vertical edge.

Then you just compare the diagonals.

Hope this helps.
 
I am posting this here because I think someone here will either know
the answer or know a better place for me to ask this question.

I am looking for an algorithm to provide AI for a Tic Tac Toe (aka
Naughts and Crosses) style game. But not necessarily for Tic Tac
Toe.

I'm looking for an algorithm that can evaluate and arbitrary sized
board with an arbitrary win condition. So for example, tic tac toe is
a 3 by 3 board with a win condition of 3 in a row.

I need an algorithm for an m by n board with a win condition of x in a
row where x <= m and x <= n.

Does that make any sense?

I don't just want code (but I'll take anything I can get), I want to
learn the algorithm. This is for my own private project.

Does anyone have such an algorithm or know a good resource where I
could learn about such algorithms?

Thanks,

Chris
Click to expand...

Not sure I understand what your asking, but I found the following on
code project:

http://www.codeproject.com/vb/net/yetanothertictactoe.asp

Thanks,

Seth Rowe
 
I am posting this here because I think someone here will either know
the answer or know a better place for me to ask this question.

I am looking for an algorithm to provide AI for a Tic Tac Toe (aka
Naughts and Crosses) style game. But not necessarily for Tic Tac
Toe.

I'm looking for an algorithm that can evaluate and arbitrary sized
board with an arbitrary win condition. So for example, tic tac toe is
a 3 by 3 board with a win condition of 3 in a row.

I need an algorithm for an m by n board with a win condition of x in a
row where x <= m and x <= n.

Does that make any sense?

I don't just want code (but I'll take anything I can get), I want to
learn the algorithm. This is for my own private project.

Does anyone have such an algorithm or know a good resource where I
could learn about such algorithms?

Thanks,

Chris
Click to expand...

This page should get you started: http://www.klab.caltech.edu/~ma/tictactoe.html
 
I am posting this here because I think someone here will either know
the answer or know a better place for me to ask this question.

I am looking for an algorithm to provide AI for a Tic Tac Toe (aka
Naughts and Crosses) style game. But not necessarily for Tic Tac
Toe.

I'm looking for an algorithm that can evaluate and arbitrary sized
board with an arbitrary win condition. So for example, tic tac toe is
a 3 by 3 board with a win condition of 3 in a row.

I need an algorithm for an m by n board with a win condition of x in a
row where x <= m and x <= n.

Does that make any sense?

I don't just want code (but I'll take anything I can get), I want to
learn the algorithm. This is for my own private project.

Does anyone have such an algorithm or know a good resource where I
could learn about such algorithms?

Thanks,

Chris
Click to expand...

Chris,

Take a look at the minimax algorithm. It is used to make strategic
decisions against zero-sum games of perfect information. Tic-tac-toe,
connect four, chess, go, etc. are all in that category.

The algorithm is based on assigning a probability or bias of winning
to any given board configuration. It then constructs and scans a
decision tree of all possible successor configurations to find the
most optimal move assuming that each player wants to maximize his
benefit using that calculated value.

It's the algorithm of choice for almost all chess engines. Though,
competitive engines use insanely complex variations of it.

http://en.wikipedia.org/wiki/Minimax_theorem

Brian
 
If you are looking for a general strategy for writing two-person, turn based
games, where one of the players is the computer, then look into "alpha/beta
pruning" and the "minimax" algorithm.

You can find some C# code, discussion of the algorithms, and sample code for
Othello at http://www.frontiernet.net/~fredm/dps/Contents.htm in the chapter
on Game Trees.
 
If you are looking for a general strategy for writing two-person, turn based
games, where one of the players is the computer, then look into "alpha/beta
pruning" and the "minimax" algorithm.

You can find some C# code, discussion of the algorithms, and sample code for
Othello athttp://www.frontiernet.net/~fredm/dps/Contents.htmin the chapter
on Game Trees.
Click to expand...

Thanks Fred, and all the other responders. I will be reading what you
have suggested. Fred, is your link a book that is available in print?

Chris
 
The link is to an online book, not available in print. There is also a link
to the book's C# code as well as the SEL library on the website. The
bibliography mentions some print books that discuss the various algorithms.
 
Back
Top