Analysis Algorithm
Hi!
This is a long one, but please bare with me. :)
I'm currently written an application that does the round
pairing of a chess tournament. I have a class Manager
that handles the pairing. I also have a class, Analysis, that is
suppose to analyse the possible place a player can get.
This option gets availible when there are three rounds left to play.
The problem is that to carry out an exact analysis I must
"play" (brute force) all the possible endings(the number of
points a player can get at most and least is no hard task to get,
put the problem is to find the monrad and berger points.
Definition of monrad and berger points at the end). E.g. there
are 100 players and 3 rounds to go. This makes 3 * 3^50
(3 rounds * 3 different results^50 players) =
215.369.396.075.557.766.310.747
possible endings.
It's not possible to do brute force on this so is there any algrithms/algorithm patters that do this?
Monrad: The points are given by adding the points of a
players opponents. In tourneys with 6 or less rounds the
lowest is removed, in tourneys with 7 or more rounds the
two lowest are removed. If two players have the same
number of monrad points the removed values are added one at a time.
Berger: The points are given by adding the points of the
opponents a players has won against and adding half of
the points the player has played draws with.
Sincerely Dan
[1530 byte] By [
Tykena] at [2007-9-28 2:16:42]
> > Isn't there a book on computer chess theory?
>
> This isn't a chess problem, it's an algorithm
> problem.
> Finding possible end positions of all players 2-3
> rounds before
> the tourney is done. And it shouldn't take the pc e.g.
> 6 hours
> to compute the results.
Sorry about that. When my brain is in my head again I'll think about this -:)
uja at 2007-7-7 21:49:16 >
I don't think you have to brute force ALL of it.
I'm not entirely clear as to how the pairing works, but I'll take a guess.
To maximize ones points one has to be winning against players with the most points. They also have to be winning against players with the most points. The optimal arrangement isn't clear, so we can brute force that part:
So to play 3 rounds we need only consider 8 players at a time.
The player in question (that we want to figure out the best scenario for), and the top 7 other players.
* 8 players makes 243 endings right? times running this simulation by 100 players is 24300.
> I have a class Manager
> that handles the pairing. I also have a class,
> Analysis, that is
> suppose to analyse the possible place a player can
> get.
It's not possible that every player plays 49 other players, right? Your "Manager" class handles pairing for the "current" round? So how do you determine the pairings in a round? Once that round is assigned, don't the "winners" of the round move on to the next round, thereby cutting the field in half at the same time? Rinse and repeat, should be easily brute forceable.
