[OT] Looking for algorithm

[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

 

[Nicholas Paldino [.NET/C# MVP]]

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.

 

[rowe_newsgroups]

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

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

 

[Michael Letterle]

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

This page should get you started: http://www.klab.caltech.edu/~ma/tictactoe.html

 

[Brian Gideon]

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,

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

 

[Fred Mellender]

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.

 

[Chris Dunaway]

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.

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

 

[Fred Mellender]

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.