Combinatorics

Joel McNary
Bartender
Posts: 1840
So, I'm working on some AI for a game. I'm writing a genetic algorithm to evolve the strategies to play the game (the German board game Adel Verpflichtet by Klaus Teuber ), and have a couple questions about setting up the tournaments to evaluate the strategies.

1). What is the minimum number of games that need to be played to ensure that every strategy plays every other strategy the same number of times? I think that it is x choose y, but I am hoping that in some cases it is less, as my strategy population is 20 and it is a 5 player game -- resulting in over 15,000 different games that need to be played. I would like to run for 100 generations, so that's a total of 1,500,000 games. My computer can do about 1000 games per minute, so that 1,500 minutes, or about 25 hours for a run. If so, then so be it (this is not the game play, just perfecting the computer's strategies...), but I would like to play with the evolution functions a bit...

2). If the minimum number of games where every strategy plays every other strategy the same number of times is not x choose y, then what is the best algorithm to produce that number and the sub-sets?

This is an extension of my senior project at college. I'm doing this mostly for the Genetic algorithm bits, but do enjoy the game. (Right now it's entirely console-based -- not GUI at all...) Any suggestions/comments are appreciated.

Jim Yingst
Wanderer
Sheriff
Posts: 18671
What is the minimum number of games that need to be played to ensure that every strategy plays every other strategy the same number of times?

Um, zero.

I think that it is x choose y

Well, the minimum number of
I think you're right, if your requirement is that each pairing occur an equal number of times - you need C(20,5) = 20!/(5!*15!) = 15504 games. (I haven't proven that this is really the minimum, but it seems right.) However I question whether you really need all the pairings to occur an exactly equal number of times. In the c(20,5) scenario here, a given pair plays in 204 games opposite each other. I'd think you could get a decent idea of their relative rankings in much less - say 10 games or so? To compare your results to other pairings, just divide by the number of games played for each pairing. E.g. for four strategies A, B, C, D:

A vs. B: 10 games, A won 7, 70%
A vs. C: 9 games, A won 4, 44%
A vs. D: 12 games, A won 10, 83%
etc.

Wouldn't these sorts of results be enough to evaluate the relative effeciveness of the strategies? So what you'd need, then, is an algorithm for selecting games that keeps the pairing totals at least approximately equal. E.g. you could keep of the total number of times each pairing had occurred so far. For any given game, find the two pairings that had occurred least often so far, and put them in the game. That gives you 4 or maybe 3 players so far. Fill the remaining spot(s) by looking for other under-played pairings involving one of the players you've already selected. Repeat this process every new game. Basically, you're always making new games using the players who have played together least. I don't know what is the exact optimal strategy here, but I suspect you can get a "pretty good" strategy without too much effort. Good enough to allow you to run many more generations, or more different strategies - which is probably much more interesting than getting more precise results. Does that sound feasible to you?

Joel McNary
Bartender
Posts: 1840
Sounds reasonable enough to me...when I did it for my senior project, I just decided to choose the strategies for each game randomly from the pool. That gave me good enough results at the time, but one of the things that I am trying to play with now is changing different things in the evolution process -- including how the strategies are choosen. I might do one of the day-long-runs just for comparison's sake, but I think that the approach of measuring how many games A plays against B and then weighting the results sounds reasonable enough.

Thanks