Computer tournament and tie break

TAILLE · Post by **TAILLE** » Sat May 30, 2009 00:25

Hi,

It appears to me that the miniature used for the tie break in the french open championship was not a so good idea because the choice of the winner may depend on a human mistake. The past is the past and I was really happy to see TDKing winning the tournament. Damy version was not very stable and it would not have been logic to see Damy winning the tournament with this version.

Why not exchanging here in order to know what we would like to see for a tie break? Do not forget that, should Kingsrow and Damage have won their last game, then 4 programs would have been at the 1st place with 11 points!

The first idea would be to play quick games between the concerned programs but everyboby fears that we will obtain to much draws before the first win. At least we can try one or two games (if only 2 programs are concerned!).

In Arleux we used as the first criteria the Sonneborn Berger. It is a very common approach and could avoid a poor suite of draw games. Unfortunnetly this criteria was not sufficient here!

What else ?

After having classified all the programs using firstly the number of points and secondly the Sonneborn Berger, why not try to look at the best result ? If the best win of program A is against the 5th program, and the best win of program B is against the 6th program, then program A is declared the winner.

What is your feeling for the future ?

Whatever the solution, the most important point is to have a rule known before the tournament. Do you think it could be a good idea to discuss and agree between us on this rule?

Ed Gilbert · Post by **Ed Gilbert** » Sat May 30, 2009 03:02

I agree with you that using a tie break which relies on play against a human is not the right way to do it, and also that we should discuss this and agree on a system before the next tournament.

I like using the Sonneborn Berger, and also I think your idea to use the best win as a second tie break if necessary is good.

If a tie still exists after all the tie break rules have been applied, we can have 2 winners. With 2 strong programs playing each other there could be many draws before a decisive game occurs.

If the sentiment is to try to resolve the tie through games, then perhaps two games can be played using a start position that gives a significant positional advantage to one side. Each program can play the strong side for one game and the weak side for the other.

-- Ed

TAILLE · Post by **TAILLE** » Sat May 30, 2009 11:32

Ed Gilbert wrote: If a tie still exists after all the tie break rules have been applied, we can have 2 winners. With 2 strong programs playing each other there could be many draws before a decisive game occurs.

If the sentiment is to try to resolve the tie through games, then perhaps two games can be played using a start position that gives a significant positional advantage to one side. Each program can play the strong side for one game and the weak side for the other.
-- Ed

Yes Ed that could be a good solution to accept to have more than one winner for a given tournament. It happens sometimes in sport. Then we have only to list the maximum of tie break rules, in the right order, to avoid this last decision.

Let's try the following list :
1) The number of points
2) The number of victories
3) The Sonneborn Berger
4) The best result
5) The second best result
6) The third best result
...
When the 4th rule is reached I suppose that all programs are classified according to the first three rules.

If after all these rules the tie remains then we have a problem with several possible solutions
1) More than one winner : it is simple but not very satisfactory for the organisation which wishs to give a cup to only one winner
2) Quick games between the 2 (or more) reamining programs. It seems also not a very good idea because the probability is very high to see a lot of draws
3) A miniature against a human : it seems not satisfactory because the result may depend on human mistakes.

What about starting from 2 advantageous positions (Ed. proposal). I do not like very much such proposal because nobody knows if, in the two positions, the advantage is quite the same, and we have a human intervention (for choosing the positions).
In addition I think that the most important ability for a program is not to win with an advantageous position but to obtain first this advantageous position! That is another reason why I do not like to start games with already advantageous position.

I just have a new idea. If it remains a tie after all the previous rules have been applied, that means in particular that the concerned programs have the same best result say agains the 5th program(s).
Why then not try to play additionnal game(s) against this (these) 5th program(s) with 3 advantages :
1) It is certainly the opponent against which the probabilty to win is quite near the probability to have a draw
2) The concerned 5th program may be happy to show that it can also obtain a draw against the best programs.
3) The tie resolution is made only by using the programs present in the competition, without any human intervention.

BertTuyt · Post by **BertTuyt** » Sat May 30, 2009 13:39

Interesting Discussion !
First of all I agree that i don't hope the tiebreak experiment as we have seen last tournament will be continued.

It is a computer - computer tournamant and we should not have some human intervention.

We could at least decrease the change of multiple programs on the first place, when we play more games.
I know everyone has limited time, but I would prefer a 2-day tournament where we play each opponent twice.

Next to that i would like to see a barrage with real fast games for example only 5 minutes per side.
We can only do that when we completely automate moves (for example trough damExchange).
Is after a number of games the score iis still a draw, then we could introduce all kinds of criteria as mentioned by Gerard.

Bert

TAILLE · Post by **TAILLE** » Sat May 30, 2009 14:36

Hi Bert,

BertTuyt wrote:Interesting Discussion !
First of all I agree that i don't hope the tiebreak experiment as we have seen last tournament will be continued.

It is a computer - computer tournamant and we should not have some human intervention.

I agree entirely

BertTuyt wrote: We could at least decrease the change of multiple programs on the first place, when we play more games.
I know everyone has limited time, but I would prefer a 2-day tournament where we play each opponent twice.

I prefer also a 2-day tournament in order to play more games

BertTuyt wrote: Next to that i would like to see a barrage with real fast games for example only 5 minutes per side.
We can only do that when we completely automate moves (for example trough damExchange).

I understand the idea but I am a little reluctant for several reasons :
1) A tie break is a privilege time for the spectators who will certainly prefer to see a real board and a real clock.
2) What about a bug in recording the move sent to the opponent ? The two programs will continue with a different position until an impossibility is detected by one program
3) Automated games between computers can be organised during all the year. As soon as programmers have been travelling to the same place it would be a pity to play automated games
4) All programs have not yet introduced the damExchange interface (though it seems not a difficult task!)

Ed Gilbert · Post by **Ed Gilbert** » Sat May 30, 2009 14:41

BertTuyt wrote:We could at least decrease the change of multiple programs on the first place, when we play more games.
I know everyone has limited time, but I would prefer a 2-day tournament where we play each opponent twice.

I also think that we should play more games. I would prefer to see 2 games played between each pair of opponents. This could still be accomplished in a 1-day event if we were willing to play into the early evening.

-- Ed

Ed Gilbert · Post by **Ed Gilbert** » Sat May 30, 2009 16:52

What about starting from 2 advantageous positions (Ed. proposal). I do not like very much such proposal because nobody knows if, in the two positions, the advantage is quite the same, and we have a human intervention (for choosing the positions).

There is only one start position, and each side gets to play it as black and then as white, so the advantage and disadvantage is the same for both opponents. This is done in 8x8 checkers all the time, in the form of 3-move opening ballots. There is no human intervention involved. A list of difficult 2-move or 3-move opening ballots can be prepared before the tournament, and then one can be selected at random in the case of a tie-break. The idea is that these ballots increase the chances for a decisive game. Without something like this the probability of a decisive game between 2 strong programs is pretty small.

-- Ed

TAILLE · Post by **TAILLE** » Sat May 30, 2009 18:00

Ed Gilbert wrote:There is only one start position, and each side gets to play it as black and then as white, so the advantage and disadvantage is the same for both opponents. This is done in 8x8 checkers all the time, in the form of 3-move opening ballots. There is no human intervention involved. A list of difficult 2-move or 3-move opening ballots can be prepared before the tournament, and then one can be selected at random in the case of a tie-break. The idea is that these ballots increase the chances for a decisive game. Without something like this the probability of a decisive game between 2 strong programs is pretty small.

-- Ed

Thank you Ed. I understand now.
I have two comments :
1) after the first game the 2 programs have, in their hashtable, a certain knowledge of the initial position that can be used in the second game
2) it is a pity to not try and take into account the ability of the program to take an advantage (which is imposed by the proposed position)
Of course it is far better than nothing!

Ed Gilbert · Post by **Ed Gilbert** » Sat May 30, 2009 18:48

1) after the first game the 2 programs have, in their hashtable, a certain knowledge of the initial position that can be used in the second game

Probably not in the typical transposition hashtables, as these are complete games with 40 pieces at the start positions and ~75 moves. At the start of the second game the hashtables would only have positions from the end of the first game. But of course there are other more permanent forms of "learn" storage that could be used. As a practical matter the second game would very likely soon diverge from the path of the first, so it is unlikely that anything learned from the first game would help.

2) it is a pity to not try and take into account the ability of the program to take an advantage (which is imposed by the proposed position)
Of course it is far better than nothing!

I agree. But anything which increases the probability of a decisive game goes against the concept of using "the ability of the program to take an advantage". Blitz games cannot be made fast enough to change the probability very much. Blitz games also make the operator reaction time a significant factor, which is undesirable, unless they are automated with something like DamExchange.

-- Ed

TAILLE · Post by **TAILLE** » Sat May 30, 2009 19:05

Ed Gilbert wrote:I agree. But anything which increases the probability of a decisive game goes against the concept of using "the ability of the program to take an advantage". Blitz games cannot be made fast enough to change the probability very much. Blitz games also make the operator reaction time a significant factor, which is undesirable, unless they are automated with something like DamExchange.
-- Ed

Yes Ed. I agree with you.
What about the suggestion to play additionnal game(s) against the first program (typicaly the 5th or the 6th program) which lost against the programs in tiebreak. Isn't it a good way to measure the ability of the programs to take an advantage ant transform it into a win ?

Ed Gilbert · Post by **Ed Gilbert** » Sat May 30, 2009 20:43

What about the suggestion to play additionnal game(s) against the first program (typicaly the 5th or the 6th program) which lost against the programs in tiebreak. Isn't it a good way to measure the ability of the programs to take an advantage ant transform it into a win ?

When I look at the decisive games that occur against the weaker programs, what I often see is not that the stronger program slowly builds a positional advantage which culminates in a win. Certainly this happens in some games, but in maybe half of the games the positions are roughly equal and then somewhere in the late midgame the weaker program makes a bad blunder and from there the game is essentially over. This happens often enough that I would not want the tie break to be decided by a random blunder of a weaker program.

-- Ed

TAILLE · Post by **TAILLE** » Sun May 31, 2009 11:16

Ed Gilbert wrote: When I look at the decisive games that occur against the weaker programs, what I often see is not that the stronger program slowly builds a positional advantage which culminates in a win. Certainly this happens in some games, but in maybe half of the games the positions are roughly equal and then somewhere in the late midgame the weaker program makes a bad blunder and from there the game is essentially over. This happens often enough that I would not want the tie break to be decided by a random blunder of a weaker program.-- Ed

Yes I understand your point but isn'it the specificity of a tournament?
For me it exists two very different competitions :
1) Match betweens 2 computers
2) Tournament with a lot of computers

In the first case (match) the idea is to know which of the two computers is the best. We need for that a lot of games; most of them will be concluded be a draw and an automatic way of playing these games is necessary. As a consequence these matches can be played with a remote access between the two computers and the two programmers do not need to meet physically.

In the second case (tournament) the idea is more like a spectacle with the opportunity for the weaker programms to compete against the best ones, the opportunity for a spectator to see a lot of winning games (comparing to a match) and the opportunity for the programmers to meet physically. The winner is not necessaraly the "real" best program, it is simply the program which have the maximum wins against the weaker programs. As a consequence the chance is highly present and the winner will often change from one tournament to the other.

In this spirit the last french open tournament comfirmed that 4 programs (TDKing, Damy, Kingsrow and Damage) dominate the draughts world but of course nobody will deduce which is the best one.

Coming back to the tie break problem I think it should be also a spectacle. We cannot ignore the number of people that were interested and came to see this tie break.
I do not like at all the approach with a miniature against a human and I would not be happy to continue that way, but, at least, the spectators where happy with this spectacle.
My view is that we have to do our best in order that our tounaments can continue to be viewed as a spectacle. Automatic matches with rapid games between two computers cannot be a spectacle and, in this sense, will decrease the interest of a tournament for the spectators.

In conclusion my view is the following : let's organise matches between computers during the year and let's try to organise tournaments as a spectacle during which we could see a lot of wins by the top programs against the weakers ones.

As far as I am concerned I did not hesitate in Arleux to accept the challenge of a miniature because I saw it could be a spectacle. Of course it was not quite satisfactory for us and we have to try and find something else; but we have to keep in mind the spirit of a tournament (in opposition of the spirit of a match).

Ed Gilbert · Post by **Ed Gilbert** » Sun May 31, 2009 14:48

Hi Gerard,

Ok, I see your point. Perhaps you are right. Sometimes the computer tournaments do have the aspect of being a spectacle. Sometimes not, as in Culemborg in 2007, there were only one or two spectators besides the programmers. In any case it is more a social event than an extensive test of the programs. As a practical matter, if we use your suggestions for avoiding ties (SB, best result, etc.), then I don't think we have to worry too much about the exact form of a tie break competition because the probability of needing one should be quite small. I guess this could be tested by looking at past competitions that required tie break games.

Automatic matches with rapid games between two computers cannot be a spectacle and, in this sense, will decrease the interest of a tournament for the spectators.

For me automatic matches are quite entertaining. I have sat and watched them for hours at a time. I think Bert will agree also.

-- Ed

TAILLE · Post by **TAILLE** » Sun May 31, 2009 17:13

Ed Gilbert wrote:Hi Gerard,
As a practical matter, if we use your suggestions for avoiding ties (SB, best result, etc.), then I don't think we have to worry too much about the exact form of a tie break competition because the probability of needing one should be quite small. I guess this could be tested by looking at past competitions that required tie break games.
-- Ed

I agree with you Ed., by increasing the number of games (two games against each opponent) and by agreeing on some common rules for resolving tie break it becomes highly improbable that a tie remains.
Due to this very small probability I am even ready to accept that, should this tie remains, then the winner will be the program with the lower ratings in order to help promoting a new strong program (it is a little disadvantage for Damy because Damy has a good rating but it is not so important for me).

Ed Gilbert wrote: For me automatic matches are quite entertaining. I have sat and watched them for hours at a time. I think Bert will agree also.
-- Ed

I am pretty sure your are right Ed. The corresponding programmers will no doubt enjoy such matches

Now the proposition on the table looks like the following for deciding who is the winner :
1) The number of points
2) The number of victories
3) The Sonneborn Berger
4) The best result
5) The second best result
6) The third best result
...
When the 4th rule is reached all programs are classified according to the first three rules.

If the tie break remains the winner is the program with the lower rating.

At least it is quite simple and seems very efficient especially with 2 games against each opponent.

I know that we can also insert in the process the possibility to make additionnal games between the corresponding programms but I am not convinced it is a good idea. The probability to have only draw games is very high and, in addition, we may have more than 2 programs in competition for the first place. For the time being, I do prefer to apply directly the above criteria about I am of course open to discussion.

Putting aside this possibility to have additional games, do you first agree on the above criterias and their order?

Ed Gilbert · Post by **Ed Gilbert** » Sun May 31, 2009 19:05

Putting aside this possibility to have additional games, do you first agree on the above criterias and their order?

The only one that looks odd to me is '2) The number of victories'. I say that because victories are often the result of a blunder by your opponent, which is more or less a random event, but defeats, unless due to a program crash such as in your case recently, have to be attributed to a weakness in the program, because the game of draughts is a draw in the absence of mistakes. So I think it is worse to have N+1 wins and 1 loss than N wins and no losses.

I have a question on a slightly different but related topic. Are there some written rules for these tournaments which describe the conditions under which the game clock can be paused, or a program can be restarted? I don't think I saw any for the Arleux tournament. If a program crashes, is it allowed to restart (I guess so as it was in your case), and does the program's clock continue to lose time during reboot and restart, or can it be paused? I'm sure that whatever happend in Arleux was reasonable, I just think it should be written somewhere so that everyone knows what should happen in these cases.

-- Ed