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! :)

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).

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.




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 ;)

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).

@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!!

@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...

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.