Arimaa Forum - Print Page


    
      
        Arimaa Forum
        (http://arimaa.com/arimaa/forum/cgi/YaBB.cgi)
      

        Arimaa >> Events >> 2007 World Championship Format
        
(Message started by: Fritzlein on Aug 18^th, 2006, 3:43pm)

Title: 2007 World Championship Format
Post by Fritzlein on Aug 18^th, 2006, 3:43pm

If the World Championship begins in mid-November like last year, that's only three months away. If registration is going to open one month in advance, we have only two months for discussing the rules. ;)

Actually, I don't think much discussion is needed, because things worked quite well last year. Here are some features of Omar's format which I think worked very well:

* Participation open to everyone
* Registration fee refunded if all games played
* Floating double elimination
* One game per player per week, scheduled by ranking time slots
* 90 seconds per move, with 120 seconds per move when only 4 players remain
* Capturing all opposing rabbits is a win

I woud rather it were triple-elimination, but I can understand not wanting to lengthen the tournament.

In a different conversation Omar had raised the possibility of limiting the tournament to 16 participants on the basis of rating. I am deeply opposed to this idea, because ratings are greatly subject to manipulation. I am of the opinion that any adult of normal intelligence and no prior Arimaa knowledge could, between now and the World Championship, learn methods by rote for winning against certain bots, and achieve a 2500 rating. If this happens, fine, but nobody who hasn't studied bot-bashing in the same way should lose a seat in the World Championships because of it.

I also have two quibbles with the floating double-elimination algorithm of last year. First, repeat pairings need to be avoided with a higher priority than assigning a bye to the most deserving player. (The issue didn't arise in last year's World Championship, but did arise in the Computer Championship.) [EDIT]I'm wrong; it did arise in round six of the World Championship too.[/EDIT]

Second, the assignment of second and third place should not be by order of elimination. Rather it should be by number of wins. If people tie for number of wins, then they should keep playing elimination games to break the tie. For example, if the records of the players end up being

6-0
4-2
4-2
3-2
etc.

then the two 4-2 players should play an additional game to determine second and third place. If the records of the players end up

7-0
6-2
5-2
5-2
5-2
4-2
etc.

then the three 5-2 players should play elimination for third place. In general, playing additional elimination games seems preferable to me in comparision to a tiebreaking scheme based on things other than wins and losses.

Title: Re: 2007 World Championship Format
Post by Fritzlein on Aug 19^th, 2006, 10:51am

on 08/18/06 at 15:43:43, Fritzlein wrote:

In a different conversation Omar had raised the possibility of limiting the tournament to 16 participants on the basis of rating. I am deeply opposed to this idea...

Oh, and I forgot to mention that adding new players doesn't lengthen the tournament much. Last year with 16 players it took eight rounds, and for up to 32 players it takes a maximum of nine rounds. One extra round seems a small price to pay for keeping the tournament open. (Actually, in my opinion, the more rounds the better. I'd like a 15-round World Championship. I know Omar feels otherwise. How does everyone else feel about the World Championship covering many weeks?)

Title: Re: 2007 World Championship Format
Post by PMertens on Aug 19^th, 2006, 11:32am

if 15 rounds means 2048 players than I think you are slightly optimistic about arimaa-popularity ...
(but I would like it)
Making rating a cutoff is not a wise idea since a certain number of top 16 players will not necessarily play.

Title: Re: 2007 World Championship Format
Post by Fritzlein on Aug 19^th, 2006, 12:29pm

on 08/19/06 at 11:32:08, PMertens wrote:

if 15 rounds means 2048 players than I think you are slightly optimistic about arimaa-popularity ...
(but I would like it)

Hehe. If I'm not mistaken, 2048 players in floating double-elimination could theoretically go 16 rounds, although 15 rounds is more typical. But when I mentioned a longer tournament, I was thinking floating triple elimination.

If we have 24 players sign up for an open World Championship this year (and I don't think that's unrealistically optimistic), then I believe floating triple elimination will be done in thirteen rounds for sure, but with an average under twelve rounds. Yes, triple elimination would mean a larger probability that you would have an irreconcilble conflict on some week, but it also means you could more easily survive that forced loss that one week and go on to win the tournament, becuase you would still have two lives left rather than one. It's not like any of us can clear our schedules for nine weeks anyway, so a possible twelve-week commitment isn't going to force anyone out who would otherwise play, would it?

Who all is with me in wanting a twelve-round triple-elimination World Championship?

Title: Re: 2007 World Championship Format
Post by seanick on Aug 19^th, 2006, 12:29pm

maybe I am dense but can you explain how the round system ends up taking x number of weeks? I don't think the actual number of people that can play will double with only one additional week, for instance.

obviously between 2 people it would take up to 3 weeks. 4 people would take.. at least 4 weeks but possibly up to 5?... etc.

-for triple elimination that might be worth thinking about. has it only been discussed (but never tried) thus far? or has it been used in the past?

Title: Re: 2007 World Championship Format
Post by Fritzlein on Aug 20^th, 2006, 12:48am

on 08/19/06 at 12:29:20, seanick wrote:

maybe I am dense but can you explain how the round system ends up taking x number of weeks?

I don't have any formula; I just work it out by hand. The number of rounds for a given number of players varies depending on when and if the last undefeated player gets a loss. With floating double elimination and 2^N players I can work out all the cases, but I can't with weird numbers of players or triple elimination. Here are the floating double elimination rounds for 16 and 32 players:

Rounds	No loss players	One loss players
0	16	0
1	8	8
2	4	8
3	2	6
4	1	4
5	1	2
6a	1	1
6b	0	3
7aa	1	0
7ab	0	2
7b	0	2
8ab	0	1
8b	0	1

So with 16 players, it takes 7 or 8 rounds, depending only on whether the eventual champion is undefeated or not.

Rounds	No loss players	One loss players
0	32	0
1	16	16
2	8	16
3	4	12
4	2	8
5	1	5
6a	1	2
6b	0	4
7a	1	1
7b	0	2
8aa	1	0
8ab	0	2
8b	0	1
9ab	0	1

So with 32 players, it takes 8 or 9 rounds, but it no longer depends only on whether the eventual champion is undefeated or not, because now it can end in eight rounds with a one-loss champion.

Since 32 players takes exactly one more round than 16, one might suppose that each doubling of players adds one more round, but in fact it seems to add slightly more than one round per doubling in general. Perhaps the general formula includes a lg(N) term and a lg(lg(N)) term.

Title: Re: 2007 World Championship Format
Post by Fritzlein on Aug 20^th, 2006, 8:59am

I just noticed that a floating double elimination tournament with 2^N players will, after N rounds of play, have exactly one undefeated player and N players with one loss. This suggests that the formula for maximum number of rounds in a FDE tournament of X players is 2+lg(X)+lg(lg(X)). Given that lg(lg(X)) is so tiny, we essentially do get to double the number of players for each additional round we are willing to play.

Title: Re: 2007 World Championship Format
Post by seanick on Aug 22^nd, 2006, 11:18am

these are usually played at about one round a week, right? so 12 rounds is 3 months?
after that it starts to be kind of a long tournament.. having to go that long without, say, a 2 week vacation away from any computers. so there is some sense to keep it under 256 players.

hmm, one month is all that is necessary to square the number of people that could enter.
That in mind, I agree it seems not to make sense to limit the entries to the top 16 by rating.

(even though I think it will probably be one of the top 6 by rating that wins. its a few months away though so if nothing else those ratings might change by then... )

Title: Re: 2007 World Championship Format
Post by PMertens on Aug 22^nd, 2006, 1:24pm

on 08/22/06 at 11:18:31, seanick wrote:

(even though I think it will probably be one of the top 6 by rating that wins. its a few months away though so if nothing else those ratings might change by then... )

at least it is not reduced to 2 titans like last year ;-)

Title: Re: 2007 World Championship Format
Post by Fritzlein on Aug 22^nd, 2006, 4:14pm

on 08/22/06 at 13:24:10, PMertens wrote:

at least it is not reduced to 2 titans like last year ;-)

Yeah, we all know that last year only two people had a realistic chance of winning according to the ratings at that time. In fact, playing out the games last year was wasted motion, since everyone knew it was between me and 99of9.

Title: Re: 2007 World Championship Format
Post by seanick on Aug 22^nd, 2006, 10:55pm

I would like to be wrong here, for sure. but I think you (by which I mean you collectively, those in the top 6) are slightly better prepared for new styles and paying more attention than last year. even so, the top 6 includes some serious talent. Sure, it might be someone ranked 17th or 18th or something (especially if they just barely make the cutoff should Omar decide top 16 by rating only, and a couple people don't enter thus leaving open spots for 17 and 18 to join...), but my gut tells me it will be someone in the top 6. maybe 8 if Jean comes back by then.

Title: Re: 2007 World Championship Format
Post by robinson on Aug 23^rd, 2006, 4:55am

i want to argue for an open tournament, too
first i think it is a big motivation for newcomers, as it was for me when i first visited this site, to keep on playing here, knowing that evryone could take part and match up with the big ones.
and second i think it cant reduced to any count untill we have no clear rating system ( or maybe ratingsystem for only human games ) if someone havent time to play much bots to increase his rating, it wouldnt be fair not to allow him to play.

for the tournament i would prefer something were we have a clear final and maybe semi-final. so maybe we can play doubleelimination untill there are 4 players left and the best of 3 or something like this.
i havent liked last years situation that the game between me and adanac decided if paulM would be in the final...even though he got a second chance after it...

Title: Re: 2007 World Championship Format
Post by Adanac on Aug 23^rd, 2006, 7:09am

on 08/23/06 at 04:55:26, robinson wrote:

I'd vote for an upper limit on the number of players such as 128, which would realistically allow all interested players to join every WC for the rest of the decade but will limit the field once we have hundreds or thousands of active Arimaa players. If Omar specifies is an upper limit maximum for the number of weeks, I would prefer a 128 double-elimination tournament rather than a triple-elimination with a smaller number of players.

And with 128 players, I think the prediction contest should be reserved for spectators only - but that's not an issue for the next few years. For now, I really enjoy player participation in both competitions :)

Title: Re: 2007 World Championship Format
Post by PMertens on Aug 27^th, 2006, 11:59am

I propose a randomized pairing instead of the folded pairing of last year.

Title: Re: 2007 World Championship Format
Post by Fritzlein on Sep 10^th, 2006, 4:10pm

on 08/27/06 at 11:59:16, PMertens wrote:

I propose a randomized pairing instead of the folded pairing of last year.

I think you don't mean completely random pairings, do you? Certainly no one should have to face the same opponent twice if there is another pairing that prevents repeat matchups. Also, I quite like having winners play winners and losers play losers.

But if what you mean is simply ignoring the ratings for the purposes of pairing, I think it would be an interesting experiment. 99of9 once posted some axioms for pairing, including things like

* A higher rating never hurts you
* A lower rating never helps you
* The player with the highest true skill has the best chance of winning.
* etc. etc.

I note that if you completely ignore the ratings for the purposes of pairing, 99of9's axioms are satisfied. The player with the highest true skill still has the best chance of winning, and inflating your rating neither hurts nor helps you.

I expect some people will object to ignoring ratings for pairings, because failing to seed the tournament makes it less likely that best player will win. Maybe in a seeded tournament the #1-rated player has a 35% chance to win, and in an unseeded tournament has a 25% chance to win. The latter might still be higher than any other player's chance, but not as high as before. This goes against the principle of choosing a format with the highest possible chance of crowning the best player champion.

I see a tension between using ratings to help pick the best player, which is good, and inflating your own rating to increase your chance of winning the tournament, which is bad. We all know the ratings can be manipulated in several ways. If we put too much emphasis on the rating, then there is a huge incentive to protect one's rating and inflate it before the tournament by botbashing.

Maybe a better idea is this: instead of ignoring the ratings for the purposes of pairings, calculate seeding based on anti-human performance. For example, take every human's last 30 games against human opponents, calculate their performance rating based on those games, and seed the World Championship with those ratings.

Title: Re: 2007 World Championship Format
Post by Fritzlein on Sep 10^th, 2006, 4:25pm

on 08/23/06 at 07:09:32, Adanac wrote:

If Omar specifies is an upper limit maximum for the number of weeks, I would prefer a 128 double-elimination tournament rather than a triple-elimination with a smaller number of players.

I totally agree. A 16-player triple-elimination and a 128-player double-elimination each last about 11 weeks. I would much rather keep the tournament open to all who want to play than have an extra elimination.

There is a balance between maximizing the chance of the best player to become champion on one hand, and keeping participation open on the other. I am extreme in favoring openness. If all you really want is to find the best player, then take the top four and play triple-round-robin. Sadly, in that scheme robinson wouldn't even have been allowed to compete last year, never mind win! Come to think of it, the best scheme for giving the World Championship to the best player last year would have been for Omar to give the title directly to me with no tournament at all. That would have eliminated the possibility of my being knocked out by a weaker player.

But no, it is much more friendly and fun to let everyone have a shot at the World Championship. If you wear the crown it shouldn't just mean that you are the best, it should mean you won the World Championship against all comers.

Title: Re: 2007 World Championship Format
Post by PMertens on Sep 11^th, 2006, 3:08pm

wow .... now you are getting a bit overconfident ;D

Title: Re: 2007 World Championship Format
Post by Fritzlein on Sep 11^th, 2006, 6:32pm

Is it possible to be overconfident about something that has already happened? You must mean I am getting arrogant :P As for the coming tournament, who knows if I will even be the number one seed, never mind the eventual victor...

Title: Re: 2007 World Championship Format
Post by seanick on Sep 12^th, 2006, 4:04am

re this statement: If you wear the crown it shouldn't just mean that you are the best, it should mean you won the World Championship against all comers.

what if you lose one? but everyone else loses at least 2, including the person you lost one game to. wouldn't that mean there was no champ? besides you don't have to be the best to go on a winning streak, nor do you have to be on a winning streak to be the best. for that matter, what does "best" mean anyway? best against humans, bots, both on average, most consistent, highest win percentage, nicest car, richest parents, ...?

whatever, its a dumb game anyway :P

(and if anyone actually thinks that I believe that, I also have a bridge for sale! please send the money in cash, unmarked non-sequential small bills in multiple standard-size briefcases, directly to 123 main street, anytown, usa. 78965. thanks! )

Title: Re: 2007 World Championship Format
Post by jdb on Sep 20^th, 2006, 8:21am

Pmertens stated:

Quote:

I propose a randomized pairing instead of the folded pairing of last year

Here is my first draft at a randomized pairing system:

This description assumes two loses and the player is out. It can be extended to N losses.

Initially all players are placed in the zero losses pool.

1) If an odd number of players remain in the tournament, select a player randomly to receive a bye from those who have received the fewest byes.

2) If an odd number of players remain in the zero losses pool, select a player randomly from the one loss pool, to be paired with the zero losses pool, from those who have had to play "up" the fewest times.

3) Randomly pair the players in the zero losses pool, not allowing repeat pairings.

4) Randomly pair the players in the one loss pool, not allowing repeat pairings, unless everyone in the pool has played each other.

There is no guarantee that a valid pairing set is possible. So if no pairing is produced, try the algorithm again. After (say) 1000 tries if no valid pairing is produced, use the pairing produced by the last iteration.

Title: Re: 2007 World Championship Format
Post by Fritzlein on Sep 20^th, 2006, 1:14pm

On further reflection, I can see two possible benefits of not using the ratings for pairing. First, people won't inflate their ratings to get higher seeds. I don't think we should count this as a benefit, though, because there is a better way to achieve it. If you want to stop people from inflating their ratings by bot-bashing, a better method is for Omar to re-run his ratings algorithm on the games database, but using only HvH games, and seed the tournament based on those ratings.

The second possible benefit is fairness. I quite like the idea of everyone entering the tournament on an equal footing, with no handicaps to anyone. If low-rated players have to fight an uphill battle, that should be because they aren't as skilled as other players, not because they get terrible pairings, always against the toughest available opponent.

On the other hand, the principle of fairness conflicts with the principle of maximizing the probability of the best player becoming champion. Ratings don't in themselves accurately pick the best player, but they are a strong indiciator, and using ratings in folding pairing certainly improves the chances of the best players. If the Arimaa World Championship tournament seems to produce winners that are too random, the title of World Champion starts to lose respect. Look what happened when the international chess federation (FIDE) tried to say that Alexander Khalifman was the World Champion of chess, although he was rated around #40 in the world. Sure, he won the World Championship tournament, but nobody thought he was actually the best player, so it just made the title of World Champion look silly.

If we could have a triple-elimination format, then I guess I would go with fairness, because three losses should be enough for skill to win out even given rough pairings, but if we have only double-elimination, I think I have to cast my vote against random pairing. Seeding on the pre-tournament ratings is somewhat akin to having "the regular season" account for one elimination. If the seed are based on HvH games only, I don't think this is too unfair.

Title: Re: 2007 World Championship Format
Post by Fritzlein on Sep 20^th, 2006, 2:04pm

With floating double-elimination, and seeds based on HvH ratings, my preferred pairing algorithm for floating elimination remains:

* If an odd number of players remain, the bye must go to some player among the players with the fewest byes so far.
* Minimize the number of pairings occuring for the Nth time.
...
* Minimize the number of pairings occuring for the fourth time.
* Minimize the number of pairings occuring for the third time.
* Minimize the number of pairings occuring for the second time.
* Give the bye to the player with the fewest losses.
* Pair players with a similar number of losses against each other.
* Pair players with a similar number of wins against each other.
* Give the bye to the player with the highest rating.
* Maximize the sum of the squares of the rating differences.

Maximizing the sum of the squares of the rating differences (the lowest priority) is a way to insure folding pairing when nothing more important is going on. Notice that the ratings only influence pairings as the lowest two items on the list. Any way to increase the number of similar W/L pairings takes priority. Any way to reward in-tournament performace with a bye is higher priority than either of those. And any way to reduce the number of repeat pairings is higher priority than anything, except that you can never ever give byes unevenly.

Under this scheme, if there were an odd number of players, the highest-rated player would get the bye in the first round. In the second round the bye would go the the highest-rated winner from the first round.

If there were twice an odd number of players, there would be no bye in either the first or second round, but in the second round one winner would have to play one loser. The principle of maximizing the sum of squares of rating differences will mean that a high-rated winner plays a low-rated loser, while of course avoiding a repeat matchup. Since we already had #1 vs. #N and #2 vs. #(N-1) in the first round, it would probably be #1 vs. #(N-1) or #2 vs. #N, whichever gap is larger.

I believe that a human armed with pencil, paper, logic, and a little patience could implement this algorithm for the size of tournament we are talking about, even though it is theoretically exponential in the number of players, because in the early rounds only a couple of constraints are in play, and in the late rounds few players are left.

It's interesting to note that this algorithm would have made a slight difference in the World Championship tournament last year. The first five rounds would have been the same, but in round six the repeat matchup would have been avoided. Robinson had already beaten Adanac. Adanac had already beaten PMertens. So why did Adanac have to play Robinson again? I think it is slightly unfair that PMertens got the bye on the basis of a higher rating. Fairer would be make PMertens and Robinson play (NOT a repeat matchup) and give the bye to Adanac. So I think my current proposal would have done better for the WC.

For the Computer Championship, I formalized this algorithm precisely to prevent a repeat Bomb-Clueless pairing in the seventh round (indeed, already in the sixth round) in favor of a first-time Bomb-Aamira pairing. But I also want to point out again that my current proposal would have avoided a grave injustice already in round three of the Computer Championship. Loc, which had already lost to Aamira and Bomb, was paired against Aamira again, instead of against Clueless. If Loc happened to have some bug that only Aamira triggered, then it is an unfair advantage to Aamira to get a repeat matchup and also an unfair penalty to Loc. We didn't fuss about it much at the time, because Loc would probably have lost to any bot it played, but still it wasn't fair, and it wouldn't happen again with what I now propose.

What do you guys think, am I just too attached to the floating elimination format, or can it really work well if we do the pairings right?

Title: Re: 2007 World Championship Format
Post by PMertens on Sep 20^th, 2006, 2:21pm

I still dislike folding by ratingdelta² ... especially in round 1.
I see really no need in making it even harder for those less experienced/rated by putting them up against the worst possible opponent.
And you on the other hand do need a handicap and not a read carpet ;-)

Title: Re: 2007 World Championship Format
Post by Fritzlein on Sep 20^th, 2006, 3:58pm

on 09/20/06 at 14:21:10, PMertens wrote:

And you on the other hand do need a handicap and not a read carpet ;-)

Hmm... I guess when I argue for folding pairing, I'm arguing for my own benefit, since I temporarily have the #1 rating. Maybe I should recuse myself from the discussion, since I have a stake in the outcome.

Anyway, like I said, I can see both sides. I don't want the Arimaa World Championship title to become a joke, but the idea of everyone starting the tournament on a level playing field is attractive too. I'll be happy whatever Omar decides.

If ratings are not used in the pairings, I still want all the other pairing guidelines there, though, in the same priority, i.e.

1) Equal distribution of byes
2) No repeat pairings
3) Bye to player with fewest losses
4) Equal records play each other.

None of those give anyone a red carpet...

Title: Re: 2007 World Championship Format
Post by jdb on Sep 20^th, 2006, 4:07pm

Quote:

If ratings are not used in the pairings, I still want all the other pairing guidelines there, though, in the same priority, i.e.

1) Equal distribution of byes
2) No repeat pairings
3) Bye to player with fewest losses
4) Equal records play each other.

I am curious what the rationale is for rule number three. I'm not offering an opinion for or against it, I just wish to know the reason for the rule. Thanks

Title: Re: 2007 World Championship Format
Post by Fritzlein on Sep 20^th, 2006, 7:26pm

on 09/20/06 at 16:07:29, jdb wrote:

I am curious what the rationale is for rule number three.

The problem with assigning byes is that in some cases one player will be able to win the tournament with fewer total wins than another player. In the run-up to last year's tournament, I was expecting fewer than 16 players to participate. As I played out several scenarios for floating double elimination with fewer than 16 players, it became clear that some players would have to win six games to become champion, whereas players on a different path could become champion with only five wins. It made sense to me that if any player should get the easier path, it should be the one who has the best record so far in the tournament.

(By the way, contrast the difference between five and six wins in a twelve-player FDE with a fixed-bracket twelve-player double-elimination. In the fixed bracket a player who gets the early bye and wins out needs only four wins to become champion, but a first-round loser has to win seven to become champion. So the potential unfairness of floating double elimination is still less than of fixed-bracket double elimination.)

Anyway, to my surprise, it turned out that in a 16-player floating double elimination, with the first bye going to the one undefeated player after four rounds, there is perfect equity. Every player, no matter their seed or order of wins and losses, has to win six to become champion.

When David Levy proposed giving the bye to the lowest loser instead, Ryan Cable pointed out that it not only destroys the perfect equity, but could indeed result in a two-game disparity in winning path:

on 01/25/06 at 19:44:05, Ryan_Cable wrote:

If we had followed David Levy’s system in the WC, robinson would have had to win seven games if he went undefeated:

Round 5
Adanac - bye
robinson - PMertens
Fritzlein - 99of9

Round 6
Fritzlein/99of9 - bye
robinson - Adanac

Round 7
robnson - Fritzlein/99of9

But worse still, if in Round 5 PMertens beat robinson and Fritzlein beat 99of9, robinson would have to face PMertens again.

Round 6
Fritzlein - Adanac
robinson - PMertens

Round 7
Adanac/Fritzlein - PMertens/robinson

Perhaps the most horrible thing is that Adanac would be able to win the Championship with only 5 wins as a reward for being the lowest rated loser.

My hope, although I haven't proven this by any means, is that by giving the bye to the player with the fewest losses, the disparity in the number of wins required to become champion is kept down to ONE at most, and furthermore, the player(s) with the championship route requiring one less win is(are) the player(s) getting an early bye for not having lost up to that point.

Title: Re: 2007 World Championship Format
Post by omar on Sep 20^th, 2006, 10:19pm

With our current FxE algorithm do pairing problems only occur in rounds where a bye is required or could they also occur in rounds where there are even number of players?

If the problem is only in rounds where a bye is required then I can have it cycle through giving a bye to each player to generate a set of possible pairings (equal to the number of players) and score each pairing and pick the one with the best score.

Title: Re: 2007 World Championship Format
Post by Fritzlein on Sep 21^st, 2006, 8:33am

I'm afraid the best pairing can be hard to find both when there is a bye to be given and when there isn't. It's not enough to try one pairing for each possible bye. For example, look at round three of the 2005 Computer Championship. Bomb is the obvious choice for a bye, because Gnobot and Clueless already had byes, while Aamira and Loc have losses, but Bomb is undefeated. However, There are three possible pairings of the other bots once Bomb has the bye, and only one of the three avoids repeat matchups. If you just create one pairing which gives Bomb the bye, you might incorrectly conclude that Bomb shouldn't be given the bye.

The good news is that with only five players (or six) there are only fifteen possible pairings total. We could look at all fifteen. The top priority (even distribution of byes) knocks out six with Gnobot and Clueless getting a bye compared to any of the nine where Bomb, Aamira, or Loc gets a bye. The second priority is repeat matchups, and of the remaining nine possibilities six are rejected for creating a repeat matchup, leaving only three. The third priority, giving a bye to a player with few losses, breaks the tie between those three, leaving only one possible pairing, and making the further criteria irrelevant.

Remember that Paul Pogonyshev wrote some branch-and-bound code to seek the best pairing, so you wouldn't have to start from scratch in getting a computer pairing algorithm:

on 01/22/06 at 13:31:06, doublep wrote:

OK, I implemented an overkill solution (1000 lines of C++.) You can grab it at http://download.gna.org/quarry/tournament.cpp (modified BSD license, use as you please.)

Usage: compile and run with tournament data redirected to its stdin, e.g.

Code:

$ g++ tournament.cpp -o tournament
$ ./tournament <test-tournament

Data is in the following format:

Code:

tournament-scheme [parameters]

number-of-players-initially
player-name rating
...

number-of-rounds-player

player-1 player-2 winner
...

...

With ellipsis standing for repetition. E.g. for the WCC 2006 it would be:

Code:

elimination 3

5
bot_Gnobot 1667
bot_Loc 1586
bot_Aamira 1580
bot_Clueless 1574
bot_Bomb 1484

2

bot_Gnobot
bot_Loc bot_Bomb bot_Bomb
bot_Aamira bot_Clueless bot_Clueless

bot_Clueless
bot_Bomb bot_Gnobot bot_Bomb
bot_Aamira bot_Loc bot_Aamira

The penalties are not perfect, but produce more or less sensible results. Feel free to experiment. And happy reading, the code is almost uncommented :)

Title: Re: 2007 World Championship Format
Post by Janzert on Sep 21^st, 2006, 8:56pm

Just wanted to add a note on my thoughts on the WC format goals (I thought I posted something similiar a year or so ago but can't find it at the moment).

I personally do not think the primary goal in determining the world championship tournament format should be to make it "fair". Rather the primary goal should be to make it accurate, i.e. having the greatest likelyhood that the truly best player in the world wins. Now in many ways I think this still leads to a "fair" tournament as I don't think it's at all out of the question with the current state of Arimaa for a relatively new player to be way underated and actually be the best player. But I don't think accuracy should be compromised for the goal of fairness. Of course determining the accuracy, or even relative accuracy, of given formats is not simple and probably very open for argument.

Also as a secondary goal I think the rules for any tournament should be as transparent as possible. Random pairing to me seems to be about the worst possible option in that regard. I think the FxE formats are already bad enough in that you can't "tell at a glance" if the pairings are correct¹ but I think they make up for it by the gain in accuracy.

Janzert

¹. e.g. not made as to give any player a special advantage. I was also going to say that the random pairing doesn't allow for independently checking the pairing, but this could probably be done by publishing the prng algorithm and seed for each round before the tournament begins.

Title: Re: 2007 World Championship Format
Post by omar on Sep 21^st, 2006, 10:27pm

Thanks for reminding me about Paul's program. I've downloaded it and started trying to work it into the tournament simulator.

Title: IRe: 2007 World Championship Format
Post by PMertens on Sep 22^nd, 2006, 10:42am

hmm ... in my humble eyes the primary goal should be fun ... and nothing else ... ;-)

There is just very little point in participating as worst rated of the crowd if you will always be paired against the best rated available ...
Limiting the tourney to the top 4-8 does not make it much fun ... even if the rest of the crowd does not really stand a chance ... no matter how you pair them.

Betting is not really fun if a top-dog is fighting a mouse ... neither is watching.
Sorry, but watching 2 beginners to battle it out while blundering all the time does sound more interesting to me than watching Fritzlein punish every mistake on the spot and finishing up his opponent ... slowly but unavoidable ... ;-)

Promoting the best-rated does not make it more accurate anyway ... as can be seen in our recent fun tournament.

Title: Re: 2007 World Championship Format
Post by Fritzlein on Sep 22^nd, 2006, 4:08pm

on 09/21/06 at 20:56:35, Janzert wrote:

Also as a secondary goal I think the rules for any tournament should be as transparent as possible.

Thanks for bringing up the issue of transparency, Janzert. I agree with you in thinking the pairing system should be transparent. It is a disadvantage if the optimal pairing can't be determined by a casual observer who doesn't write a program to exhaustively check all possibilities.

However, floating elimination is transparent in one very important way: if you think you have a better pairing than the official one, it is simple to check whether or not it is actually better. Anyone who thinks they got an unfair deal is free to propose an alternative pairing, and we can easily show how the alternative is worse according to clearly-defined priorities. We may realize the priorities are sub-optimally ordered, as last year's tournament showed, but at least (even then) they are clearly defined by whatever Omar writes into the rules.

Quote:

I personally do not think the primary goal in determining the world championship tournament format should be to make it "fair". Rather the primary goal should be to make it accurate, i.e. having the greatest likelyhood that the truly best player in the world wins.

I've been trying to figure out why "fairness" and "accuracy" should be pitted against each other. Why can't we be fair and accurate both? Indeed, on general principles, it would seem that the most accurate system is also the fairest.

The bone of contention is the extent to which ratings (a.k.a. pre-tournament performance) should be taken into consideration. If you believe in accuracy above all, there is definitely some information contained in ratings. You can infer reasonably well from a player's rating the likelihood that he is in fact the best player in the world. Last summer Omar demonstrated that (depending on our assumptions about ratings) triple-elimination is not as accurate in crowning a World Champion as giving the title to the highest-rated player with no tournament at all.

I think Omar was right. If accuracy is our only objective in crowning a World Champion, a tournament might be the wrong way to go. I could claim that I have already proven I am the best player in the world at present, and playing a tournament for the World Championship only introduces the possibility of error.

Seeding a tournament by ratings falls somewhere between the extremes of ignoring ratings totally on the one hand, and having ratings decide everything on the other hand. There is a lot of gray area in the middle. Floating double-elimination favors high seeds less than fixed-bracket double-elimination. Swiss pairing (winners play winners, losers play losers) favors high seeds less than straight folding pairing every round. Giving byes based on W/L record favors high seeds less than giving byes based on seed. Indeed, I think I've supported just about every way to de-emphasize ratings apart from random pairing, which goes a bit too far for me.

Being World Champion, in my opinion, should recognize a specific over-the-board achievement against everyone else who chooses to compete for the same prize. Fairness in this context is allowing everyone to compete in that event on reasonable terms. I think it is reasonable to have the "regular season" be part of the total achievement, in the form of seeding, but to me the focus should remain as much as possible on performance in the actual tournament.

That's my wishy-washy middle-ground position, and I'm sticking to it!

Title: Re: IRe: 2007 World Championship Format
Post by Fritzlein on Sep 22^nd, 2006, 5:27pm

on 09/22/06 at 10:42:47, PMertens wrote:

hmm ... in my humble eyes the primary goal should be fun ... and nothing else ... ;-)

Fun is good, but a bit hard to define. If we're only out for fun, for example, should we really keep track of winners and losers? Let's just play lots of Arimaa! Oh, wait, we do that all year already just for fun...

Quote:

There is just very little point in participating as worst rated of the crowd if you will always be paired against the best rated available ...

What do you mean there is little point for the worst-rated to participate? Do you think that nobody would want to sign up unless they had, say, at least a 1% chance to win all the marbles? I respectfully disagree. The worst-rated player plays for fun, just like you and I do. Having fun is precisely the point. (And for the record, the worst-rated player won a game last year before being eliminated.)

If a 1500-rated player doesn't want to get clobbered, that's fine; nobody is forcing him to sign up for the World Championship. He can play all year against opponents of his own choosing, if that is more fun. He can play in the Postal Tournament and get paired only against players on his end of the bracket. I like that pairing scheme. But it is also fun (for a somewhat different reason) to take a one-in-a-million shot at winning the biggest prize in your sport. Fun comes in all different colors, and trying to be best in the world is a valuable shade of fun too.

Quote:

Betting is not really fun if a top-dog is fighting a mouse ... neither is watching.

OK, you make it clear what is fun in your book, namely games between roughly equal players. I agree that level games are the most fun to watch, and the most fun to bet on. I think it would fit this definition of fun best if the top four entrants played double round robin for the "A-level World Championship", the next four played for the "B-level World Championship", the next four for the "C-level World Championship", etc.

Quote:

Limiting the tourney to the top 4-8 does not make it much fun

Oh, wait, you also don't want to limit the field, because that's not fun. I entirely agree. I think having an open tournament is one of the funnest things about the Arimaa World Championship. I love the thought that everyone starts six wins from becoming World Champion, and if they win those six games, nothing else matters. Each player controls his own destiny, regardless of everything that has happened up to that point.

But there's an inherent contradiction between wanting an open tournament, and not wanting any mismatched games. You can't avoid mismatches by random first-round pairing; sooner or later they have to happen. To take the idea to the extreme, if you intentionally paired #1 vs. #2, #3 vs. #4, #5 vs. #6, etc., you would get matches as even as possible for the first round, but the mismatches would still have to occur in later rounds. For round two, the winner of #23 vs. #24 has to play someone... David has to take on Goliath at some point if they are competing for the same prize. In order to preserve the fun of an open tournament, you simply must embrace the David vs. Goliath matches.

Playing friendly Arimaa games for fun is a great idea. I devote a considerable percentage of my life to it. However, I believe that it is also good and fun to have one event per year be an everybody-plays fight to be King of the Hill. It is (and should be) an integral part of The World Championship tournament that everyone is trying to play the best Arimaa, not just better than their opponent du jour, but better than everyone else in the world.

Given a tournament where everyone is fighting to be best, and given that mismatches must occur later if they don't occur sooner, I am definitely in favor of having them sooner. If the first round randomly pairs #1 vs. #2 and also #3 vs. #20, the loser of the top game has a legitimate complaint. Player #3 will likely score a win, not primarily because he's a great player, but because he got lucky. Player #2 will likely score a loss and be half-dead in the tournament, not primarily because he's a poor player, but because he got unlucky. With two lives left rather than one, Player #3 will have a much better shot to win it all than Player #2, due to pure chance.

You could turn my argument around on me to say that #2 will probably have to play #1 eventually to win, which is true, but it is still a pure-luck benefit to #3 that one of the players above him must lose while #3 advances easily, and perhaps backs into the championship game.

A perfectly "fair" way to decide the tournament would be to have a lottery among all players, in which each has an equal chance to become World Champion. This is silly, though, because then being World Champion has nothing to do with playing well, and everything to do with luck. On this point I'm not in the middle ground, rather I'm towards the opposite extreme. Being World Champion should have everything to do with playing well, and nothing to do with luck, to the extent that we can make it so.

Title: Re: 2007 World Championship Format
Post by omar on Sep 22^nd, 2006, 7:24pm

I think next summer we should start the Arimaa Open Classic tournament. The puropose of the tournament will just be to have fun and see who comes out on top and it will not be designed to select the best player. The tournament will be single elimination and pair players who are close in rating. The time control will about 30 sec per move.

Title: Re: 2007 World Championship Format
Post by omar on Sep 22^nd, 2006, 7:32pm

I got Paul's program integrated into the tournament simulator. The progam runs a bit slow with 16 players and sometimes even crashes so I have not been able to run it through a lot of trials yet.

Here's a result of one trial.

##### Player List #####
player true measured
p1 1988 1977
p2 1968 2000
p3 1944 1918
p4 1904 1892
p5 1902 1931
p6 1859 1823
p7 1817 1805
p8 1795 1845
p9 1735 1762
p10 1671 1649
p11 1665 1683
p12 1654 1663
p13 1654 1632
p14 1649 1659
p15 1619 1574
p16 1503 1536
#######################

----- From Tournament Format -----
* Round 1
pick p1 p15
pick p10 p3
pick p11 p6
pick p12 p8
pick p13 p5
pick p14 p4
pick p16 p2
pick p7 p9
----------------------------------

===== From Game Simulator =====
* Round 1
pick p1 p15 winner p1
pick p10 p3 winner p3
pick p11 p6 winner p6
pick p12 p8 winner p8
pick p13 p5 winner p5
pick p14 p4 winner p14
pick p16 p2 winner p2
pick p7 p9 winner p9
==================%3

Title: Re: 2007 World Championship Format
Post by Fritzlein on Sep 22^nd, 2006, 10:14pm

on 09/22/06 at 19:32:24, omar wrote:

I got Paul's program integrated into the tournament simulator. The program runs a bit slow with 16 players and sometimes even crashes so I have not been able to run it through a lot of trials yet.

Here's a result of one trial.

Awesome. I'm glad you could get it hooked up. It's good to see that it at least gets folding pairing right in the first round.

It's not too surprising it runs slowly on 16 players, since there are 2,027,025 possible pairings the first round. Indeed, if we have 24 players as I expect, it probably won't ever finish running, given the 316,234,143,225 possible pairings in the first round. Fortunately the first two rounds of pairings can be easily done by hand, after which there are eliminations which reduce the number of players.

Would you be willing to post a complete tournament or two on, say, 11 players or 13 players, so we can see the pairing algorithm in action when lots of byes are flying around?

Title: Re: 2007 World Championship Format
Post by Fritzlein on Sep 22^nd, 2006, 10:19pm

on 09/22/06 at 19:24:52, omar wrote:

I think next summer we should start the Arimaa Open Classic tournament.

I think there is room and interest in the summer for at least one extra tournament, and probably more. There could be a fast or blitz tourney. There could be a partial round-robin, paired like the postal tourney, but with live games. I'd even like to see a revival of the Ryder Cup concept, maybe the EU vs. North America vs. the Rest of the World this time.

I hope your new job and new house work out fantastically, so that by next summer you'll have tons of free time on your hands to devote to Arimaa. :-)

Title: Re: 2007 World Championship Format
Post by 99of9 on Sep 23^rd, 2006, 1:55am

on 09/22/06 at 22:19:37, Fritzlein wrote:

EU vs. North America vs. the Rest of the World

Ok thorin and blue22... let's start warming up now! :-)

Title: Re: 2007 World Championship Format
Post by omar on Sep 23^rd, 2006, 8:08am

I ment to post the whole run, but I guess it got chopped off. Use the following links to view the trial runs.

FTE 16 players
http://arimaa.com/arimaa/tourn/compare/fte/paul/tr1
http://arimaa.com/arimaa/tourn/compare/fte/paul/tr2
FTE 17 players
http://arimaa.com/arimaa/tourn/compare/fte/paul/tr3
http://arimaa.com/arimaa/tourn/compare/fte/paul/tr4

FDE 16 players
http://arimaa.com/arimaa/tourn/compare/fde/paul/tr1
http://arimaa.com/arimaa/tourn/compare/fde/paul/tr2
FDE 17 players
http://arimaa.com/arimaa/tourn/compare/fde/paul/tr3
http://arimaa.com/arimaa/tourn/compare/fde/paul/tr4

Title: Re: 2007 World Championship Format
Post by PMertens on Sep 23^rd, 2006, 9:09am

Forgive me for not answering in the same length as you posted Fritzl ;-)

A lottery would be neither fair nor fun ...
I do not want to intentionally make games as level as possible ... I just do not want to intentionally make them as unlevel as possible ;-)

Anyway ... since few people else seem to be much interested in this and I personally will have no real advantage one way or the other I will stop continuing to explain my way of thought ;-)
I will play you in the WC and I will beat you ... 8)

Title: Re: 2007 World Championship Format
Post by omar on Sep 23^rd, 2006, 5:13pm

on 09/23/06 at 09:09:33, PMertens wrote:

I will play you in the WC and I will beat you ... 8)

Now, that's the Arimaa spirit :-) I would love watching this game.

Title: Re: 2007 World Championship Format
Post by Janzert on Sep 23^rd, 2006, 7:54pm

Pmertens wrote,

Quote:

hmm ... in my humble eyes the primary goal should be fun ... and nothing else ... ;)

And I think you are precisely correct, for the rest of the tournaments during the year. I was actually going to say something like that in my original post but obviously forgot. I think the WC is, and should be, a little different from the rest of the tournaments. I think if we show that we take the WC a little more seriously it will help the rest of the world to take Arimaa a little more seriously.

But remember in all that I say, I'm neither a player nor have helped to sponser these tournaments. So my words are worth basically what I'm charging you for them, i.e. hovering somewhere around zero, hopefully at least slightly to the positive side thereof.

Fritzlein wrote,

Quote:

Indeed, on general principles, it would seem that the most accurate system is also the fairest.

If no information is allowed to leak in from outside the tournament then I believe that is correct, the most accurate format would also be a fair format. By fair I mean gives a level playing field for every participant. If you are able to use information external to the tournament, then depending on how much and in what ways you trust that information to be accurate the format should bias itself to that information.

In this case of course the external information that has traditionally been used is the ratings of the players. If you were to believe that the ratings give a true ranking of all players at the time of the WC, then yes the most accurate format would be to simply hand the title to the highest ranked player. If you think the ratings are completely random then a format that ignores them make sense.

I personally think at any given moment the rating do a fairly good job at ordering, but are questionable in absolute ranking. Also the ratings carry an assumption of transitivity. I think this is a fairly safe simplifying assumption for HvH, but is much more questionable when it comes to Bots.

Janzert

Title: Re: 2007 World Championship Format
Post by Fritzlein on Sep 24^th, 2006, 4:35am

on 09/23/06 at 08:08:47, omar wrote:

Use the following links to view the trial runs.

Omar, thank you so much for posting full trial runs. I played through them all, attempting to do the pairings by hand. My conclusion is that 16-player or 17-player FDE can be accurately paired by hand throughout. You have to be very attentive and double-check everything, but it isn't that hard to find the optimal pairing. The early rounds have few constraints, and the late rounds have few players.

Triple elimination, on the other hand, gets too complicated somewhere in the middle for me to do accurately by hand. Around round five to seven of the triple-elimination tournaments, there were enough possible repeat matchups to confuse me, but also too many possible pairings for me to be sure I had the optimal one.

I agree that the program produced the best pairings in every round of all eight tournaments except in two cases:

http://arimaa.com/arimaa/tourn/compare/fte/paul/tr1

In round seven of this tournament there is exactly one pairing of the five players that avoids repeat pairings, namely 5-bye, 1 vs 2, 3 vs 4. Unfortunately, the program instead accepted a repeat pairing in order to give the bye to the highest-ranked eligible player. I strongly feel that avoiding repeat pairings should be in all ways more important than pre-tournament ratings.

http://arimaa.com/arimaa/tourn/compare/fte/paul/tr4

In round nine of this tournament, the same issues arises. The three remaining players, 1, 4, and 10, have each had one bye. The pairings 1 vs 4 and 1 vs 10 have each occurred once so far, while the pairing 4 vs 10 has occurred twice. The one totally wrong pairing is to give 1 the bye and pair 4 vs 10 for the third time. I can see using rating to break a tie, i.e. to give 4 the bye rather than 10 because 4 has the higher rating, but player 1's pre-tournament rating can't justify forcing the other two players into a third match. That's just what happened with Bomb-Clueless-Aamira in last year's CC, and why we needed a new algorithm.

The formulas for weighting the various pairings are in the last couple of functions of Pogonyshev's code. After I get some sleep, I'll suggest some alternative to correct what I perceive as a bug.

Title: Re: 2007 World Championship Format
Post by omar on Sep 24^th, 2006, 11:09am

Thanks for checking this out Karl. I guess we will need to experiment with different formula's for scoring tournaments. I have not had a chance to look at that part of the code yet. Im still trying to figure out why it crashes sometimes; or produces the wrong number of pairings. I've found a couple of input files that cause this.

case1
-------------------
elimination 2

16
p1 1935
p2 2009
p3 1875
p4 1886
p5 1904
p6 1894
p7 1829
p8 1886
p9 1744
p10 1722
p11 1730
p12 1721
p13 1650
p14 1632
p15 1544
p16 1510

3

p1 p15 p1
p10 p8 p10
p11 p3 p3
p12 p4 p4
p13 p6 p6
p14 p5 p5
p16 p2 p2
p7 p9 p7

p1 p7 p1
p10 p2 p2
p11 p14 p11
p12 p13 p12
p15 p9 p9
p16 p8 p8
p3 p5 p3
p4 p6 p4

p1 p4 p1
p10 p6 p10
p11 p7 p7
p12 p5 p5
p2 p3 p2
p8 p9 p8
-------------------

case2
-------------------
elimination 2

16
p1 1960
p2 1941
p3 1888
p4 1960
p5 1882
p6 1873
p7 1784
p8 1787
p9 1761
p10 1694
p11 1694
p12 1665
p13 1743
p14 1687
p15 1607
p16 1563

1

p1 p16 p1
p10 p5 p5
p11 p6 p6
p12 p2 p2
p13 p8 p13
p14 p3 p3
p15 p4 p4
p7 p9 p7
p10 p1 p1
p2 p6 p2
p3 p5 p3
---------------------

To try it out, download Pauls pairing program:
http://download.gna.org/quarry/tournament.cpp

Complie like:
g++ tournament.cpp -o tournament

Save the above input cases to files: case1 and case2.

Run the program on the input files:
tournament < case1
or
tournament < case2

Sometimes it works, but sometimes it does not, so you have to run it a few times.

I've narrowed it down to this line:
return &best_nodes[rand () % best_nodes.size ()];
and found that changing it to:
return &best_nodes[ best_nodes.size () - 1];
fixes the problem. But I haven't figured out yet why bad pairings were getting into the list to begin with. Has anyone else look had a chance to look at Pauls program.

Title: Re: 2007 World Championship Format
Post by seanick on Sep 24^th, 2006, 12:06pm

I haven't looked at the program, but for the last line, don't you mean, instead of this:
return &best_nodes[ best_nodes.size () - 1];

you actually meant this, right?
return &best_nodes[rand() % ( best_nodes.size () - 1)];
(because leaving out the random factor would mean it was always the last player in the best_nodes arrray that was picked)

Title: Re: 2007 World Championship Format
Post by Fritzlein on Sep 24^th, 2006, 9:01pm

Here are the functions which determine the "badness" of any given pairing:

(((num_games * num_losses_to_eliminate +
abs (num_player1_losses - num_player2_losses)) * sqr (all_players.size ())) + ((sqr (all_players.size ()) - 1) - sqr (abs (player1_rating_rank - player2_rating_rank))))

and

(((num_byes * (1 + previous_rounds.size ()) + num_losses) * num_losses_to_eliminate + rating_rank)
* ((1 + previous_rounds.size ()) * num_losses_to_eliminate * sqr (all_players.size ()) * all_players.size ()))

When you parse out the size of the second function, the problem is immediately apparent. It is a huge term. In effect, it says that giving the bye to the right person is more important than anything else. This includes giving the bye to the highest-rated player, even if it will cause repeat matchups. If you fed the 2006 Computer Championship to this pairing code, it would demand the third Bomb-Clueless pairing before the first Bomb-Aamira pairing in order to give the bye to the right player. This is exactly the unfairness that prompted a protest last year. We definitely want to change the code to prevent another train wreck like that.

To this end, let me rip apart the the eval function, and put it back together in the order of my priorities. (Playing out the tournaments did convince me that the giving a bye to a more deserving player should take priority over swiss pairing winners vs. winners, a minor modification.) I'll use the notation X for the number of eliminations and N for the number of players.

1. Folding pairing, our lowest priority, is dealt with by sqr (all_players.size() - 1) - sqr (abs (player1_rating_rank - player2_rating_rank)). It was clever of doublep to realize you only need to keep track of the ranks of the players, not their actual ratings. I'm not sure why he took the absolute value of something before squaring, but I left it just in case.

The penalty is (N-1)^2 minus the difference in rank squared. The larger the difference in rank, the lower the penalty. The reason it has to be a subtraction is that all penalties must be positive for branch and bound to work, so you can't reward a mistmatch, you just have to penalize it less than an equal pairing.

2. The second-lowest priority is pairing winners vs. winners and losers vs. losers. The term abs (num_player1_losses - num_player2_losses) * sqr (all_players.size ()) has the N^2 term to make it bigger than the previous term. However, I would modify it so that a paring a no-loss player against a two-loss player is more than twice as bad as pairing a no-loss player against a one-loss player. For example, if the four remaining players have 0, 1, 1, and 2 losses respectively, this function is indifferent between pairing 0v2, 1v1 (two losses difference) and 0v1, 1v2 (two losses difference). Therefore I think we should square the difference in the number of losses between the paired players, i.e.
sqr( abs (num_player1_losses - num_player2_losses)) * sqr (all_players.size ())

3. Third-lowest priority is giving a bye to a player of higher rank. To keep it above the previous term, we need to multiply by X^2 and N^2, thus

rating_rank * sqr(num_losses_to_eliminate) * sqr (all_players.size ())

4. Fourth-lowest priority is to give the bye to the player with fewer losses. To make the number of losses weigh more than the rank of the players, we have to throw in another factor of N, the number of players, i.e.

num_losses * sqr(num_losses_to_eliminate) * sqr (all_players.size ()) * all_players.size ()

5. Second-to-top priority is avoiding repeat pairings. To outdo the previous term, we need X^3 times N^3 weighting the number of repetitions. But more than that, just as in our second-to bottom priority, two pairings which have each happened once before are not as bad as one pairing with has occurred twice before. Therefore we square the number of times the pairing has previously happened:

sqr(num_games) * sqr(num_losses_to_eliminate) * num_losses_to_eliminate * sqr (all_players.size ()) * all_players.size ()

6. Finally, our top priority must be to not let the byes get uneven. This must not only be bigger than the previous term, but bigger than the previous term summed across all pairings, because it is not just more important than one repeat pairing, it is more important than any number of repeat pairings. If R is the number of rounds played so far, we need R^2 times X^3 times N^4 to be safe.

num_byes * sqr(previous_rounds.size ()) * sqr(num_losses_to_eliminate) * num_losses_to_eliminate * sqr(sqr(all_players.size ()))

To plug these back into doublep's code, we sum 3, 4, and 6 to make the function dealing with byes, and sum 1, 2, and 5 to make the function dealing with all other pairings.

I hope this makes sense and I haven't made too many errors.

Title: Re: 2007 World Championship Format
Post by Fritzlein on Sep 24^th, 2006, 9:17pm

Playing out those tournaments that Omar posted has given me some further impressions:

* The seeding is truly important. Having a higher rating makes your tournament easier. Because this is true, participants have a large incentive to inflate their ratings by bot-bashing. But if the ratings are going to be distorted, that lessens the incentive for seeding. I am more convinced than ever that, if we use ratings for seeding, it should be exclusively HvH ratings.

* I like floating double-elimination, but I like floating triple-elimination better. The third life allows flukes to work out better regardless of seeding. C'mon Omar, twelve rounds isn't too many, is it?

* The low seeds do get rocked in the pairings, but if you win your games, you can still succeed. In one of Omar's 17-player triple-elimination tournaments, #4 won it all, followed by #1, #10, and tied for fourth place were #15 and #8. It's an open tournament in spite of the seeding.

http://arimaa.com/arimaa/tourn/compare/fte/paul/tr4

* If lots of players enter (say 24) and the pairing code bogs down, the pairing can be done by hand for the first four rounds until eliminations reduce the field.

* I can't wait for the fun to begin!

Title: Re: 2007 World Championship Format
Post by omar on Sep 25^th, 2006, 6:58am

on 09/24/06 at 12:06:51, seanick wrote:

Actually this array holds tournament pairings. Sometimes some of the entries do not have a vailid pairing. But it seems the last entry always does.

Title: Re: 2007 World Championship Format
Post by omar on Sep 25^th, 2006, 7:57am

Karl, thanks for the input on adjusting the penalty functions. I have made the changes and the modified program is availible from here:

http://arimaa.com/arimaa/tourn/compare/sim/formats/floatXElimRepair/tournament.cpp

I have run the new program on the same trials posted previously. The new results for those trials can be viewed here:

FTE 16 players
http://arimaa.com/arimaa/tourn/compare/fte/paul/ntr1
http://arimaa.com/arimaa/tourn/compare/fte/paul/ntr2
FTE 17 players
http://arimaa.com/arimaa/tourn/compare/fte/paul/ntr3
http://arimaa.com/arimaa/tourn/compare/fte/paul/ntr4

FDE 16 players
http://arimaa.com/arimaa/tourn/compare/fde/paul/ntr1
http://arimaa.com/arimaa/tourn/compare/fde/paul/ntr2
FDE 17 players
http://arimaa.com/arimaa/tourn/compare/fde/paul/ntr3
http://arimaa.com/arimaa/tourn/compare/fde/paul/ntr4

Title: Re: 2007 World Championship Format
Post by Fritzlein on Sep 25^th, 2006, 12:16pm

on 09/25/06 at 07:57:36, omar wrote:

I have run the new program on the same trials posted previously. The new results for those trials can be viewed here:

Excellent, thank you. I will try to pair these with a goal of predicting 100% what the computer decided on, just to prove it can be done by hand if necessary.

Title: Re: 2007 World Championship Format
Post by doublep on Sep 25^th, 2006, 2:17pm

I've fixed a bug (memory corruption) in the program, it shouldn't crash or give weird results anymore (I hope.) And feel free to modify penalty calculation algorithm, it is broken out to separate functions just for that.

Title: Re: 2007 World Championship Format
Post by doublep on Sep 25^th, 2006, 2:18pm

Ant yes, forgot to mention that the fixed version is available at the same URL.

Title: Re: 2007 World Championship Format
Post by Fritzlein on Sep 25^th, 2006, 4:30pm

on 09/25/06 at 14:17:43, doublep wrote:

Thank you so much for the code, doublep. I really couldn't think of a better way to do the pairing I wanted, other than trying all the possibilities. Your program is a great gift to the community.

Title: Re: 2007 World Championship Format
Post by omar on Sep 25^th, 2006, 4:37pm

Thanks for the quick fix Paul. It correctly handles the two cases I mentioned above. I'll add Karl's evaluation to this version and test it out further.

Title: Re: 2007 World Championship Format
Post by omar on Sep 25^th, 2006, 4:59pm

on 09/25/06 at 12:16:36, Fritzlein wrote:

Excellent, thank you. I will try to pair these with a goal of predicting 100% what the computer decided on, just to prove it can be done by hand if necessary.

Sometimes multiple pairing solutions are found which all have the same "score". Paul's program originally selected one of these solutions at random. I modified it to select the last one in list (as a work around for the problem mentioned above).

Even though Paul has fixed this problem now, I am thinking that maybe we should have it continue to select the last one in the list just so that the program will be deterministic and we can have it produce the same output with the same input (in case we ever need to prove how the pairing was generated).

Title: Re: 2007 World Championship Format
Post by Fritzlein on Sep 25^th, 2006, 8:38pm

It makes sense to me to have the program be deterministic, and thus verifiable. From a human perspective, the order in which the code generates the tied pairings is not predictable in advance, and therefore as good as random anyway.

In the eight tournaments (about eighty rounds) I just finished double-checking, there was a tie only once, and that was caused in the first round by two players having the same rating.

on 09/25/06 at 12:16:36, Fritzlein wrote:

Excellent, thank you. I will try to pair these with a goal of predicting 100% what the computer decided on, just to prove it can be done by hand if necessary.

Let me restate my ability to do this algorithm by hand:

* In the two 16-player floating double-elimination tournaments, I made no mistakes.
* In the two 17-player floating double-elimination tournaments, I made a mistake in only one round
* In the four floating triple-elimination tournaments, I made a mistake in eight rounds and only got it right in about forty rounds. Pairing the middle rounds (4-7) of FTE should not be not be entrusted to a human, at least not me.

We need to have confidence in the code. Fortunately, I'm gaining that confidence. The nine times I messed up, I was able to track down my mistake and clearly see why the computer pairing was superior. My brain is nearly fried from trying to pair all these tournaments by hand, but I think I have energy for one more check, if you don't mind producing it, Omar. We've tried it with 4N and 4N +1, but not 4N+2 and 4N+3. If you wouldn't mind producing one floating triple elimination each for 18 and 19 players, I would check those too. (If it bogs down with 18 and 19, then 14 and 15 would be fine as well.)

Title: Re: 2007 World Championship Format
Post by Fritzlein on Sep 25^th, 2006, 9:00pm

Some observations from these tournaments:

* It is quite common for order of elimination to be a poor way of settling second and third place. About half the time there was a tie for number of wins, even when the order of elimination was clear. I repeat my suggestion that there be an elimination playoff (a.k.a. consolation game(s)) among players tied for the medal positions by number of wins before elimination.

* A better seed definitely helps, but not as much as winning games does. In the tournament here

http://arimaa.com/arimaa/tourn/compare/fte/paul/ntr1

Player #9 won the first four games, and was the only undefeated player when it was time to give a bye in round five, so #9 got to kick back on the sidelines and watch the fifth-round games of #2 vs. #4 and #1 vs. #3. By inaccurate rating #9 was actually seeded tenth, but players seeded higher (1,4,5,6,7,8,10) got eliminated without ever receiving a bye, and finished behind #9 who eventually took third place.

The ninth-seeded player (twelfth in actual skill) also took third here:

http://arimaa.com/arimaa/tourn/compare/fde/paul/ntr2

* Omar, I think a very interesting experiment would be to measure whether seed or skill is more important. Run a tournament 1000 times where the top two players have their measured ratings the reverse of their real ratings, so #1 in skill is seeded below #2 in skill. Let the rest of the players have the same random inaccuracies in ratings as they have in your current experiments. Who will win more often, the better seed or the better player? One could also repeat the experiment switching #1 with #3 or lower to see how weak a player can be boosted to victory by an inaccurate high seeding.

Title: Re: 2007 World Championship Format
Post by omar on Sep 26^th, 2006, 8:22am

on 09/25/06 at 20:38:40, Fritzlein wrote:

My brain is nearly fried from trying to pair all these tournaments by hand, but I think I have energy for one more check, if you don't mind producing it, Omar. We've tried it with 4N and 4N +1, but not 4N+2 and 4N+3. If you wouldn't mind producing one floating triple elimination each for 18 and 19 players, I would check those too. (If it bogs down with 18 and 19, then 14 and 15 would be fine as well.)

Thanks so much for verifying these Karl. I generated two more trials:
http://arimaa.com/arimaa/tourn/compare/fte/paul/fte14
http://arimaa.com/arimaa/tourn/compare/fte/paul/fte15

Title: Re: 2007 World Championship Format
Post by Fritzlein on Sep 26^th, 2006, 3:03pm

on 09/26/06 at 08:22:08, omar wrote:

http://arimaa.com/arimaa/tourn/compare/fte/paul/fte14
http://arimaa.com/arimaa/tourn/compare/fte/paul/fte15

Thanks Omar. The algorithm worked fine in both cases. In the 15-player tournament note that, although players #4 and #6 were eliminated at the same time in the second-last round, their records were 5-3 and 6-3 respectively, because player #4 got a bye and player #6 never did. I think this should mean that player #6 unambiguously finishes in third place, despite the simultaneous elimination.

I expect the pairing to work more smoothly this year than last year. I love the way this kind of floating triple-elimination works, but I'm aware that parts of it may seem strange or even wrong to other people. We'll just have to test it out and see how folks react to the way things play out in practice. Maybe after this year, people will demand a return to something more familiar like fixed-bracket double-elimination or round-robin. Or maybe floating elimination will be such a smashing success it will catch on in the wider world...

Title: Re: 2007 World Championship Format
Post by omar on Sep 28^th, 2006, 8:22am

I ran 2000 trials with the new FDE format and also 2000 trials with the new FTE format. Here are the numbers:

run3 'formats/floatDoubleElimRepair' 2000 16 500 50 9999
1 35.0%
2 23.9%
3 16.1%
4 9.8%
5 6.0%
6 3.6%
7 2.5%
8 1.3%
9 0.8%
10 0.5%
11 0.1%
13 0.1%

run3 'formats/floatTripElimRepair' 2000 16 500 50 9999
1 36.6%
2 25.7%
3 16.2%
4 8.8%
5 5.1%
6 3.5%
7 1.8%
8 1.2%
9 0.6%
10 0.2%
11 0.1%
12 0.1%
14 0.1%

I was suprised to see FDE doing almost as well as FTE. Maybe it was just a fluke. I am running another 2000 trials of FDE now.

Title: Re: 2007 World Championship Format
Post by omar on Sep 28^th, 2006, 9:07am

I've decided to stay with the FDE format for this years WC tournament. The reasons are that I would like the tournament to finish in about 2 months; I don't want to over burden the winner with the number of games that need to be played to win the tournament; and FDE is not that much worse than FTE.

The rules for the turnament are now available at:
http://arimaa.com/arimaa/wc/2007/

I plan to announce the registration in the gameroom on Oct 1st, but players can begin registering now.

Title: Re: 2007 World Championship Format
Post by Fritzlein on Sep 28^th, 2006, 9:42am

Whee! I have already registered! I can't wait for the games to begin...

I have a few minor concerns about the rules. First, the pairing algorithm doesn't actually do this:

8. Give the bye to the player with the fewest losses.
9. Pair players with a similar number of losses against each other.
10. Pair players with a similar number of wins against each other.
11. Give the bye to the player with the highest rating.
12. Maximize the sum of the squares of the rating differences.

Instead it does this:

8. Give the bye to the player with the fewest losses.
9. Give the bye to the player with the highest rating.
10. Pair players with a similar number of losses against each other.
11. Maximize the sum of the squares of the differences in rank among remaining players.

It doesn't matter much, because the important thing is avoiding repeat matchups, but the rules might as well reflect what the pairing algorithm actually does.

Second, I notice the time control is listed as 90s/90s/100/7m/6h. I quite prefer the experimental time controls we have been testing in the game room for some time now. Instead of putting a low limit on the reserve, it is nice to have a higher limit, in case there is a patch with several tricky moves in a row. A higher limit allows more control to the players over time managment. On the other hand, to keep the games moving for the spectators, we had a per-move time limit of five minutes. This seems to me to capture the best of both worlds, i.e. giving control to the players but also respecting the spectators by keeping the games moving. What do you think of changing the time contol to 90s/9m/90/0/6h/5m, as has been experimentally listed in the gameroom for a while?

Third, I notice that there is no prize for second/third place, but I still think there should be a clear method for determining those places so those people can be listed in the hall of fame and receive eternal glory. My suggestion is that eliminated players are ranked by number of wins, not by order of elimination. Either people with the same number of wins end tied, or there is an elimination playoff to settle second/third. (By the way, I think Arimaa is almost mature enough to eliminate the prize money entirely, and have the whole tournament be for glory only. The computer championship, on the other hand, still needs some incentive, because developers are disheartened by how easily we crush their puny bots...)

I guess the next task is finalizing the rules for the prediction contest. Maybe I should start a new thread about that...

Title: Re: 2007 World Championship Format
Post by Fritzlein on Sep 28^th, 2006, 4:33pm

Oh, I just realized the rules say the tournament will be seeded by "rating" with no further clarification. Are you actually going to use the server ratings to seed the World Championship? If so, it is open season for botbashing. Let the ratings inflation begin!

Title: Re: 2007 World Championship Format
Post by robinson on Sep 28^th, 2006, 6:03pm

i prefer, as fritzl too, our new time controls with the bigger reserve. i think cause of arimaa is getting more and more complex with action on every traps or tricky tactics there are moments in the game were you have to think deeper for some moves in a row to hold the level.

second: is it true that the last games are 90 sec too and not 2m as last year. i liked the 2min games even if one of the last games vs adanac costed me much sleep ;) (till 4.30 in the morning i guess )

Title: Re: 2007 World Championship Format
Post by omar on Sep 29^th, 2006, 12:45am

Thanks for the feedback Karl. I've modified the WC rules page to more accurately reflect what the pairing algorithm does.

I was contemplating using a max time per move type time control for the WC, but wasn't sure if the players would be comfortable with using that yet. But looking at the recent HH game history it seems that the top players are perfering to use this type of a time control. So I think we are ready to try this time control for the WC. I don't want to use this for any of the bot games until next year so that the bot developers have sufficient time to adapt their bots to it.

Title: Re: 2007 World Championship Format
Post by 99of9 on Sep 29^th, 2006, 6:51am

I guess I'd better try out these experimental time controls a bit more! I was perfectly happy with the old ones, so I haven't made a conscious switch. One thing I don't like about the new ones is that (in the current interface) you can't see your total reserve when it is your turn. So you can't tell if you should use up this whole turn's time or not.

Title: Re: 2007 World Championship Format
Post by Fritzlein on Sep 29^th, 2006, 9:17am

on 09/28/06 at 18:03:11, robinson wrote:

second: is it true that the last games are 90 sec too and not 2m as last year. i liked the 2min games even if one of the last games vs adanac costed me much sleep ;) (till 4.30 in the morning i guess )

I didn't realize that you like the 2 minutes per move in the final games, even though it made them long. What do other people think? Right now the vote is one to one between you and me. :P

Title: Re: 2007 World Championship Format
Post by Fritzlein on Sep 29^th, 2006, 9:27am

on 09/29/06 at 00:45:19, omar wrote:

But looking at the recent HH game history it seems that the top players are perfering to use this type of a time control. So I think we are ready to try this time control for the WC.

Yes, PMertens is the only one I know who prefers it the old way. It seems everyone else who has tried both prefers the experimental new time control. There isn't much of a difference, but it seems that the difference is all in favor of the new one. Indeed, if it seems to be a success for the World Championship, I would be happy for the experimental controls to become the new standard, so I don't have to scroll down so far when I'm inviting someone to a game.

Quote:

I don't want to use this for any of the bot games until next year so that the bot developers have sufficient time to adapt their bots to it.

Good point. We needn't inflict it on the bots without fair warning, especially since time management doesn't affect bots as much as it does humans.

Title: Re: 2007 World Championship Format
Post by Fritzlein on Sep 29^th, 2006, 9:37am

on 09/29/06 at 06:51:58, 99of9 wrote:

One thing I don't like about the new ones is that (in the current interface) you can't see your total reserve when it is your turn. So you can't tell if you should use up this whole turn's time or not.

Not being able to see the full reserve bothered me too at first, but it turns out not to have much real impact. My experience in real games is that the best use of a large reserve isn't to blow it on one move anyway, but to expend a minute or two extra for several moves in a row when the position is complex. As far as I can tell, the only situation that justifies using the entire five minutes for one move anyway is when you haven't yet found a move that will stop a forced loss. Otherwise, you shouldn't use five minutes on a move regardless of whether that's your whole reserve or you have another ten tucked away. If it isn't a forced loss, you will very probably want to spread your extra time out a bit anyway.

That said, of course I would love it if Omar displayed the full reserve too somehow, but if he's too busy to do it before the games begin, it's not a big deal. If you are husbanding your resources properly, you have time to be aware between moves how your reserve is declining. It just seems rare in practice to be blindsided by an all-or-nothing situation where you would suddenly prefer to use five minutes rather than three, but aren't aware if you can afford it.

Title: Re: 2007 World Championship Format
Post by PMertens on Sep 29^th, 2006, 11:01am

I just dislike the gnobby trick: let the opponent fall asleep ... and that would happen if I need to wait 5 minutes during the middle of the night ...
My blunder-ratio goes up as soon as the opponent plays slower ;-)
Arimaa did not become more complicated than last year ... just some of us learned a few more tricks (and should be able to play even better than before with same speed)
But then I do not really mind and whatever the majority likes is fine with me - I will not try to force my will upon others 8)

Title: Re: 2007 World Championship Format
Post by 99of9 on Sep 29^th, 2006, 11:37pm

on 09/29/06 at 09:37:19, Fritzlein wrote:

the only situation that justifies using the entire five minutes for one move anyway is when you haven't yet found a move that will stop a forced loss. Otherwise, you shouldn't use five minutes on a move regardless of whether that's your whole reserve or you have another ten tucked away.

In my opinion there are at least two other situations:

1) Your internet connection dies or your computer crashes, and you need to reboot or reset your modem.

2) You need to make a crucial game-bifurcating decision, and are perfectly capable of playing quickly after that decision is made. E.g. whether to seize an opportunity to chase an enemy camel into your territory when you would have to abandon a framed horse.

[EDIT: 3) Due to bad electromagnetic reception, you need to go to the toilet 5 times during the same move ;-).]

Quote:

Yes, PMertens is the only one I know who prefers it the old way. It seems everyone else who has tried both prefers the experimental new time control.

You can add my name to this list. I have tried the experimental methodology, both in the postals, and in at least one game where someone invited me. But I admit I don't have a great deal of experience with them.

Title: Re: 2007 World Championship Format
Post by omar on Sep 30^th, 2006, 9:06am

on 09/29/06 at 06:51:58, 99of9 wrote:

This is a good point against not using the max-time-per-move time controls yet. I do need to change the client to allow showing the total reserve time left during a players turn. Also since it hasn't even been a full year of exposure to the MTPM time control, maybe we should just stick with the regular time controls for this year, but plan on using the MTPM time control next year; for humans and bots. Hopefully this should give players enough of a lead time to start using MTPM.

I've changed the rules page back to use the 90s/90s/100/7m/6h time control.

Title: Re: 2007 World Championship Format
Post by omar on Sep 30^th, 2006, 9:13am

Here's the result of running another 2000 trials with the new FDE format.

run3 'formats/floatDoubleElimRepair' 2000 16 500 50 9999
1 32.9%
2 24.1%
3 17.2%
4 10.8%
5 6.9%
6 3.1%
7 2.4%
8 1.2%
9 0.6%
10 0.5%
11 0.1%
12 0.1%
13 0.1%
15 0.1%

Still not too bad.

Title: Re: 2007 World Championship Format
Post by Fritzlein on Sep 30^th, 2006, 10:12am

on 09/29/06 at 23:37:04, 99of9 wrote:

In my opinion there are at least two other situations:

1) Your internet connection dies or your computer crashes, and you need to reboot or reset your modem.

Yeah, crashes are a big issue I forgot since it hasn't happened to me in a while. I hope that nobody loses a game for this reason during the World Championship. No matter what the time control is, if your reserve gets low, you can lose due to techincal issues, which is an unpleasant way for a game to end. :(

Quote:

2) You need to make a crucial game-bifurcating decision, and are perfectly capable of playing quickly after that decision is made. E.g. whether to seize an opportunity to chase an enemy camel into your territory when you would have to abandon a framed horse.

OK, I can recognize the possibility of a single game-bifurcating decision after which you can play quickly, but then what's the problem in not knowing your full reserve? You use the max time for that one important move no matter what your reserve is, because you can move quickly thereafter, so it doesn't matter if your reserve gets low.

What you need to argue is that you are in a situation where you weren't worried before (so you aren't aware of your reserve) and suddenly happen to know you need exactly two long thinks (so need to know how to distribute your reserve between them) but you know you won't need several long thinks (or else you would dip into your reserve sparingly anyway).

Quote:

But I admit I don't have a great deal of experience with them.

I'll be interested to know your opinion when you have played more with the new time controls. Having a reserve that can grow beyond the max time per move is quite nice, in my opinion, and if you could see what the reserve was, there would be no disadvantage to it. However, I understand Omar's decision to be conservative for the World Championship. The old time control has the virtue of being tested. I'm not protesting his decision so much as urging you to try out the new time control some more to get to know its benefits.

PMertens, by the way, doesn't like accumulation of reserve for an entirely different reason: He just gets impatient...

Title: Re: 2007 World Championship Format
Post by jdb on Sep 30^th, 2006, 3:28pm

The difference between the original and the experimental time controls is the limiting of the reserve time. Under the original time control, when a player's reserve is full (or close to full), there is no incentive to play quickly. A player might as well use the 90 sec to study the position. Under the new time control, there is always incentive to play as quickly as possible, to accumulate reserve for future use.

As for the total time it takes to play the game, it makes very little difference which time control is used. In either method, each move gives a player an additional 90 seconds added to their clock. The only difference is there is more flexibility in the experimental time control on when the player decides to use it.

Title: Re: 2007 World Championship Format
Post by 99of9 on Oct 1^st, 2006, 1:02am

on 09/30/06 at 15:28:07, jdb wrote:

The difference between the original and the experimental time controls is the limiting of the reserve time.

If that was all, I wouldn't be too fussed.

As far as I can tell, there is another difference between the two 90s controls:

Under the old controls:
90s/90s/100/7m/6h (http://arimaa.com/arimaa/gameroom/timecontrol.cgi?tc=90s/90s/100/7m/6h&doit=1)
which includes:
7 minutes maximum reserve limit

so one crucial move can theoretically take 8 minutes 30 seconds.

Whereas under the experimental controls:
90s/9m/90/0/6h/5m (http://arimaa.com/arimaa/gameroom/timecontrol.cgi?tc=90s/9m/90/0/6h/5m&doit=1)

which includes:
5 minutes maximum turn time

so you cannot ever take more than 5 minutes.

Even if your computer crashes, or you need to make a game bifurcating decision.

Fritz, I agree this is a different issue to the not being able to see your full reserve. But I still think that is an issue in itself. We can chat about it sometime.

Title: Re: 2007 World Championship Format
Post by Fritzlein on Oct 1^st, 2006, 11:37am

I agree, 99of9, there are several issues:

(1) Can you see your reserve at all times? Not being able to see how much time is in your full reserve when you have more than the max time per move seems like a small issue to me, and one that can be technically remedied to be no issue at all.

(2) Should you be able to accumulate reserve beyond the amount that is the maximum for one move? I think having this ability is clearly desirable. It allows the players some additional control over time management without sacrificing the enjoyment of the spectators. No matter what we set as the theoretical maximum for one move (be it 5:00 or 8:30 or anything else) it makes sense to me to let players have reserve beyond that, but not use it all at once.

(3) What should the maximum time allowed for one move be? Five minutes, or ten, or eight and a half? We discussed this last year, and we should discuss it more. I'm happy to chat about it as well, but also I think it is good to have discussion in the forum where everyone can see what the pros and cons are.

If I recall correctly, MrBrain was philosophically opposed to any controls on the players' management of their time. He always advocated a large block of time for the players to do with as they see fit.

I'm a fan of chess where they do just what MrBrain wants, and it makes chess a terrible spectator sport. Even in the current World Championship games it annoyed me. Kramnik would reach a "game-bifurcating decision", and I would have to wait around twenty minutes or more before anything happened. Call me impatient, say I have ADD, whatever, but I get bored and go do something else rather than wait forever for a move, even if the position is intrinsically interesting.

Settling on five minutes per move maximum time for Arimaa seemed like a good idea to me. I think the needs of the spectators (not to mention the other player) to keep the game going should trump the right of time management of the players to that extent at least. Five minutes per move is already very slow for spectators, and for some players as well. PMertens would have to simultaneously play a game of blitz on the side to keep from falling asleep.

I don't mind forcing players to make critical decisions within five minutes. Frankly, I don't believe that giving players full control over their time results in better chess anyway. In chess, too many players agonize too long over midgame moves, and then end up with time trouble later which causes them to blunder away games. Forcing a steadier pace might actually improve the overall chess game quality.

But even if there are cases where the quality of games is slightly raised by giving the players more control, I come out in favor of respecting the spectator. I watch American football, and sometimes a 300-pound lineman will be bearing down on the quarterback, who has only a second or two to make a critical decision. Could he make a better decision if he had more time? Certainly, but decisions under pressure are part of what make football a fun game to watch.

Of course, there has to be a balance. You could say that the World Championship would be more exciting for spectators if all games were played at 30 seconds per move. On the other extreme, you could say the games would be of highest quality at 3 minutes per move with total control to the players. For me 90 seconds per move with a five minute maximum hits the sweet spot. The game quality won't improve all that much from more time per move, and the spectator experience will deteriorate significantly by raising the per-move maximum. Obviously other folks will feel the sweet spot differently.

I admit, the issue of protecting against disconnects is tricky. Having a flaky connection puts a player at a real disadvantage. It would be a huge shame if someone lost on time due to technical difficulties during a World Championship game. On the other hand, a large reserve can't entirely protect against it anyway. Sometimes it takes fifteen minutes or an hour to resolve something. I don't know what to do about the issue, but increasing thinking time to deal with it seems unsatisfactory to me.

By the way, I'm not writing this treatise to try to bludgeon everyone into submission. I respect that Omar has already made his decision for this year's time control. I also respect that different people will feel differently about what concessions should be made to the players rather than the spectators. I'm writing because it is worthy of discussion, and it's good for everyone to air their opinions.

Title: Re: 2007 World Championship Format
Post by RonWeasley on Oct 3^rd, 2006, 7:45am

Moaning Myrtle told Harry she's been giving advice at some muggle chess tournament. How would you stop something like that, huh?

The really creepy thing is that she watches you from inside the loo when you go.

Title: Re: 2007 World Championship Format
Post by PMertens on Oct 5^th, 2006, 9:21am

Quote:

PMertens would have to simultaneously play a game of blitz on the side to keep from falling asleep.

::)

well ... actually I start reading news or watch tv ... both does not really help my concentration ...
unfortunately my brain still is the brain of a real time strategy player .... :P
"could you please hold that missile a second, I need to ponder what unit you are going to target so I can move it away in time"

Title: Re: 2007 World Championship Format
Post by Janzert on Oct 10^th, 2006, 8:27am

I ran across this today although I haven't had time to read more than the abstract it looks like something people here (well at least Fritzlein :P) may be intrested in. Probably something to take a look at before deciding on next years tournament format.

"Bayesian optimal design of knockout tournaments" (http://math.bu.edu/people/mg/papers/knockout.pdf)

Janzert

Title: Re: 2007 World Championship Format
Post by Fritzlein on Oct 10^th, 2006, 11:15am

Wow, thanks for the fantastic link, Janzert. The paper only deals with single-elimination, but the lessons might be applicable to multi-elimination formats as well. A few nuggets of wisdom I glean from a quick first reading:

* If you are trying to determine the best player, folding pairing after each round works better than fixed-bracket pairing or random pairing. That makes sense. What is startling is that they have a method that is even better than folding pairing.

* Their method somehow gets its advantage from the uncertainty of ratings in the way it gives a break to the top-rated players. For example, if there are 8 players and folding pairing, you pair #1 with #8 because that gives the best probability of the best player not being upset. But if #8 is rated 1410 with an RU of 112, whereas #7 is rated 1420 with an RU of 30, then there is less of an upset chance if you pair #1 versus #7, because we know so little about #8, he might be a ringer. Indeed, #8 might actually be the best player, so we want to avoid hammering him the first round.

* Most important (to me): The FTE pairing algorithm doesn't have to search an exponential number of possible pairings. There exsists an O(N^3) algorithm to find the best pairing. I am so embarrassed that I didn't realize this on my own. What were my graduate math courses for, anyway? We studied exactly this in Network Flows, if I could only remember that a maximum-weight perfect matching applies also to non-bipartite graphs. But anyway, my personal humilitation aside, the existence of an efficient pairing algorithm is a good thing for the future of floating triple elimination. I was afraid FTE would be nice but impractical for large tournaments, and therefore FTE would never catch on. Now, given an efficient implementation algorithm (vastly better asymptotically than doublep's branch and bound), FTE will rise or fall on its intrinsic merits, rather than its computational difficulty.

Title: Re: 2007 World Championship Format
Post by RonWeasley on Oct 10^th, 2006, 12:59pm

Quote:

We studied exactly this in Network Flows, if I could only remember that a maximum-weight perfect matching applies also to non-bipartite graphs.

I think Hermione said the same thing in Snape's potion class last week. That was just before her cauldron spewed tapioca all over Longbottom.

Title: Re: 2007 World Championship Format
Post by Fritzlein on Oct 19^th, 2006, 8:51pm

Omar, just a quick note that the "World Championship" link in the gameroom is still pointing to last year.