Sign in to follow this  
AkaToraX

Game Winning Conditions Algorithms

Recommended Posts

AkaToraX    122
Hello! I have no been able to find any resources for writing algorithms for checking game winning conditions. Specifically, board games. For example, TicTacToe is so basic a brute-force check is probably faster than any algorithm would be. Checkers is also easy, just look at each available for a legal move, no legal moves, game over. But then when you get to more complicated games it isn't as easy. Let's say GoMoku, or 5-in-a-row. From any one piece there are 20 different possible ways to win from that piece (20 different 5-in-a-rows that could have been made). Which brute forcing is slow-enough to notice. Chess I imagine might prove 'sloppy' as well... The games are old, well-known, public domain, games with lots of information, just haven't been able to find and winning-conditions algorithms. The logic can be in any language, even English. My point is, this has already been done before dozens of times and I don't want to reinvent the wheel. Thanks to anyone that can point me to any resources! :)

Share this post


Link to post
Share on other sites
Zahlman    1682
The question seems not well-defined. Every game is different, and there is no "magic" to algorithms.

There do exist techniques, of course. One powerful technique is generalization. The same code can be written to check for a gomoku win as for a tic-tac-toe win, for example, if you think of both as specific cases of the class of games "place tokens on an N by N grid until one player has made a straight line of X tokens" (tic-tac-toe: N = 3, X = 3; gomoku: N = 19, X = 5).

Share this post


Link to post
Share on other sites
marius1930    119
Having a simply array with the data,
Start at the corner and have the function call itself over and over with each +1 until it either runs out of options or finds a win.
Stopping at each row/col end going to the next.
Embarrassingly enough i can't remember the name for that...

Then run the same function with +row+1/-1 to cross downwards.
There may be '20 different moves' but there are only 4 different combinations for a win in 5-in-a-row.


int a(int i) {
if (i < INT_MAX)
return a(i + 1);
}





Anyways it may not be pretty, but unless the board game is 80x80+++ tiles you're unlikely to notice any performance issues.

It is after all, just reading a few ints ;)

Share this post


Link to post
Share on other sites
Antheus    2409
Quote:
just haven't been able to find and winning-conditions algorithms.


Thank goodness for that, or some people would find themselves rather embarrassed.

Some game-related problems are still impractical to solve, even though the games are thousands of years old.

Quote:
The logic can be in any language, even English


Each game has a set of rules written down. Those are your plain English instructions.

There should really be no problem brute forcing the conditions for most games.
5-in-a-row: scan all rows, all columns and all diagonals. If any of them contains 5 pieces of same color, player has won.

For GoMoku, each time a player adds a stone, check the area that could have changed: -5..5 pieces into every direction. At which point, you can use algorithm you have written for 5 in a row.

Quote:
Which brute forcing is slow-enough to notice


No, it's not, unless you use a really wasteful implementation. My guess would be that for some reason or another, you're getting O(n^2) or worse algorithm where one isn't necessary.

Quote:
Chess I imagine might prove 'sloppy' as well...


Not really, but chess-related problems are covered in CS textbooks, so efficient algorithms are available (although not needed).

Share this post


Link to post
Share on other sites
AkaToraX    122
@Zahlman

Let me try to reword it....I'm looking for resources for existing game winning condition logic. Someone, somewhere, has already coded how to check for a chess win, and nine-men's morris win, etc. But I haven't been able to find any resources about it. Solving the game for perfect-play returns a wealth of information, but no helpful in my little quest.

@marius
I believe it's called a recursive function, and indeed, I wrote one for GoMoku and just felt like "there has to be a better way" because even though the code is written logically, in the end it is still a brute-force check.

THANKS SO FAR!!

Share this post


Link to post
Share on other sites
AkaToraX    122
@Antheus
Lol, not SOLVING the game, checking to see if the game has been won :) And unfortunatley, yes, I'd say about a half-a-second delay noticed after each placement...maybe It is my own sloppy code instead of sloppy logic...

Share this post


Link to post
Share on other sites
drakostar    224
500ms to check for five-in-a-row on a fairly small board? How did you manage that?

The recursive maze-solver I wrote back in high school ran pretty much instantaneously on 50x50ish boards, using something like a Pentium 200.

Check your algorithm. Make sure you're not visiting the same square multiple times.

Share this post


Link to post
Share on other sites
ItsDan    104
For 5 in a row, consider that a diagonal from a spot up-and-left is the same as another spot's down-and-right, if that makes sense. That is, only check down, right, down right, and downleft, or some combination you pick. If you consider it in those terms, you've covered all the possible 'shapes'. And skip useless steps, for example if the board is 10 units wide, don't check directly to the right beyond column 6, because at column 7 you lack enough spaces to the right to win.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this