Continued: Team selection issues

[Sven]

This thread is intended to continue discussion about a technical issue raised here within the Tournaments subforum.

Sven

[Sven]

Martin,

[this part would actually belong into Programming subforum ...]

4461 will work for automatic, "optimized" team selection. But what will happen in case of team selection by humans? Will the upper limit of 4461 guarantee that there will be no "unsolvable" situation, whatever choice of teams is made by humans? I don't think so, we saw a counter-example in this thread. I think you need a second rule, either a lower limit or the explicit rule that for a team size of 2, one player must be from the upper half of the ranking and one from the lower (could be generalized for team size N). Otherwise selecting a team where both players have a low rating would immediately break the system.

Any idea whether this can be solved in general? I tried it but was not successful so far ...

Sven

Hi Sven, it actually returns a lower bound and I'm 100% sure you can't go below 4461. I also added the condition that the first engine MUST come from the upper half (command line parameter -half) and it boosted the search. It now takes 20 seconds to find the lower bound for 16 input engines, which is not bad I think. I just uploaded a new version to mediafire, link remains the same.
It was just meant as a helper tool to find the lower bound so that the problem is still solvable (anything below the lower bound means 100% unsolvable). When the lower bound no longer works, it has to be reestablished. Ideally, the lower bound should be recomputed each time an engine pair is selected.
Considering the upper bound, assuming we have upper and lower half pairing, the upper bound should be simply the best engine in the upper half and the best engine in the lower half.
Btw. sorry to plague tournaments subforum but I think the problem is too specific

Martin

Hi Martin,

it is possible that you slightly misunderstood the requirements. I want to give my view on it, maybe we can come to an agreement which view is matching the original scenario more closely.

The teams are selected by humans who are not necessarily using an "optimizing" strategy, which is creating quite different conditions from what you are solving with your program.

Initially the only rule was that the total elo of each team must not exceed some threshold Emax. So Emax is the "upper limit" for the total team elo. Ideally you are interested in almost equal team strength for all teams, as close as possible to the average elo of the field. That is why you are trying to minimize the upper limit Emax.

But the issue is, with no other restriction on the allowed selections it is easy to break the system, by selecting a team with a total elo low enough to make the remaining selection process "unsolvable". Here "unsolvable" means that at some point no rule-conforming selection can be made.

Redefining (raising!) the upper limit at that point solves the problem locally (until the next "offending" selection) but makes some teams being selected towards the end of the selection process stronger than those selected under more restrictive rules in the beginning. This has indeed happened in the given recent case where our discussion started from, look on the total team elo of my team for instance

So you need more than only the upper limit Emax. I mentioned two ways, one is to add a lower limit Emin (which you want to maximize, same as you want to minimize Emax) so that all selections must be within the interval [Emin .. Emax] around the elo average, and the other is (for two-player teams) to only allow selections with one team from upper and one from lower half.

Now what you understand as "solving" this kind of problem is to programmatically find an optimal team setup that satisfies the given rules while generating a field as close as possible. You have shown that this is possible, which I had no doubt about. Doing so seems not to require a lower limit or a second "upper + lower half" rule, although at least the latter can serve the purpose to speed up your solution process.

But as the real scenario is a non-optimized human selection process, my thought was to let a program calculate the optimal limits that can be set for the whole selection process (and left unchanged up to the end) such that it is impossible to break the process (go into "unsolvable" state) by any rule-conforming selection. As I explained above, for this to work you definitely need more than just the upper limit Emax. It might even turn out that only adding the "upper + lower half" rule will not be sufficient as well, since selecting the players (engines) with the lowest elo from both upper and lower halves might already lead to the same "trouble".

So my best guess is to have a program calculate an optimal interval [Emin .. Emax]. Such a program would have to check whether for a "candidate interval" being currently examined, there is any possible sequence of rule-conforming team selections that can lead to an unsolvable state. If there is, the interval must be considered as too tight and has to be extended, otherwise a tighter interval can be tried.

Does this make sense to you?

It is clear that the non-optimized selection process driven by humans will usually generate a non-optimal field. But I think that Graham, or any other TD setting up such a tournament, will be more interested in the "fun" component than in always getting the optimal selection result. But as long as it can happen that the rules must be changed during the selection process the "fun" component could be slightly affected, which is why I raised my hand in order to try to programmatically find optimal limits, without doing automated selection ...

I already tried to implement something like I described above but I obviously did it in a hurry so there are bugs preventing my success there. But it should not be too difficult to do it right.

Sven

[mar]

Hi Sven, yes it makes perfect sense to me
Considering EMax:
I tried to look for the minimum solvable upperbound (EMax) and verified that by brute force search.
My conclusion is that anything below "combined elo of best two engines that form a valid pair" can always end up being unsolvable.

So EMax = maximum combined elo of a valid pair (or two highest rated engines that can make a valid pair)
anything above or equal to EMax means 100% solvable

EMin is what my program tries to solve. So anything below EMin means 100% unsolvable.
Note that even when using the upper/lower half optimization, incremental EMin/EMax updates will still work.
When updating incrementally: EMin will rise and EMax will drop until they meet (that was my case when I was left with only one possibility

Please note that my aim was not to do automated optimized selection (that was a byproduct of finding EMin) nor to break the fun of doing manual selection . But I found the problem interesting so I tried to think about it.

Martin

[mar]

P.S. The latest version of my program which I believe calculates the optimal limits where EMin is much more important than EMax since calculating EMax is trivial can be found here: http://www.mediafire.com/?557qge58fqq83j5 (I reached file update limit and now mediafire wants me to go pro
bestvalue <=> EMin
upper combined limit <=> EMax
best pairing <=> proof that EMin is valid; as a byproduct it should return optimized (balanced) pairings (minimizes max-min elo difference)

Martin

[Sven]

O.k., so let's verify whether your result will survive the practical test

Here are the 16 programs again:

Code: Select all

Jazz 444 32-bit                      2299
ECE 11.01                            2295
FireFly 2.5.10                       2286
KMTChess 1.2.1 32-bit                2284
Chesley r323                         2258
Parrot 07.07.22                      2240
Prophet 2.0                          2229
Kurt 0.9.2 32-bit                    2220
Ice 0.1                              2215
Clarabit 1.00                        2212
Carballo 0.5 32-bit                  2198
Bubble 1.5                           2189
BikJump 2.01                         2177
Protej 0.5.7                         2158
Jabba 1.0                            2152
PLP 1661571                          2149

The rules are:
- You and I alternatingly select a team consisting of two programs. You start, I follow, and so on.
- For any team selected, the total ELO must never exceed EMax which is defined as 4461.
- For any team selected, the total ELO must never fall below the value EMin which you, Martin, define prior to your first selection. (Since the average ELO of all programs is 2222.5 I would EMin expect about 4429 but it is totally up to you.)
- EMin and EMax remain unchanged until all eight teams have been selected.
- Within the given limits EMin/EMax, both you and me are free to select a team as desired.

Do you agree?

Sven

[mar]

O.k., so let's verify whether your result will survive the practical test

Here are the 16 programs again:

Code: Select all

Jazz 444 32-bit                      2299
ECE 11.01                            2295
FireFly 2.5.10                       2286
KMTChess 1.2.1 32-bit                2284
Chesley r323                         2258
Parrot 07.07.22                      2240
Prophet 2.0                          2229
Kurt 0.9.2 32-bit                    2220
Ice 0.1                              2215
Clarabit 1.00                        2212
Carballo 0.5 32-bit                  2198
Bubble 1.5                           2189
BikJump 2.01                         2177
Protej 0.5.7                         2158
Jabba 1.0                            2152
PLP 1661571                          2149

The rules are:
- You and I alternatingly select a team consisting of two programs. You start, I follow, and so on.
- For any team selected, the total ELO must never exceed EMax which is defined as 4461.
- For any team selected, the total ELO must never fall below the value EMin which you, Martin, define prior to your first selection. (Since the average ELO of all programs is 2222.5 I would EMin expect about 4429 but it is totally up to you.)
- EMin and EMax remain unchanged until all eight teams have been selected.
- Within the given limits EMin/EMax, both you and me are free to select a team as desired.

Do you agree?

Sven

Hi Sven

It's clear to me now that I probably misunderstood what you meant with EMin/EMax.
What I meant was valid bounds for chosing ELimit (=value defined by TD), while you seem to like the idea that ELimit is a range (EMin..EMax).
So I take a timeout now until I read all your posts again and rethink all of that

[Sven]

O.k., so let's verify whether your result will survive the practical test

Here are the 16 programs again:

Code: Select all

Jazz 444 32-bit                      2299
ECE 11.01                            2295
FireFly 2.5.10                       2286
KMTChess 1.2.1 32-bit                2284
Chesley r323                         2258
Parrot 07.07.22                      2240
Prophet 2.0                          2229
Kurt 0.9.2 32-bit                    2220
Ice 0.1                              2215
Clarabit 1.00                        2212
Carballo 0.5 32-bit                  2198
Bubble 1.5                           2189
BikJump 2.01                         2177
Protej 0.5.7                         2158
Jabba 1.0                            2152
PLP 1661571                          2149

The rules are:
- You and I alternatingly select a team consisting of two programs. You start, I follow, and so on.
- For any team selected, the total ELO must never exceed EMax which is defined as 4461.
- For any team selected, the total ELO must never fall below the value EMin which you, Martin, define prior to your first selection. (Since the average ELO of all programs is 2222.5 I would EMin expect about 4429 but it is totally up to you.)
- EMin and EMax remain unchanged until all eight teams have been selected.
- Within the given limits EMin/EMax, both you and me are free to select a team as desired.

Do you agree?

Sven

Hi Sven

It's clear to me now that I probably misunderstood what you meant with EMin/EMax.
What I meant was valid bounds for chosing ELimit (=value defined by TD), while you seem to like the idea that ELimit is a range (EMin..EMax).
So I take a timeout now until I read all your posts again and rethink all of that

Fine for me.

Just as a further note, when assuming EMin=4429, the test I proposed above would already have failed if you had started with the selection "Kurt + Parrot" (4460) and I had continued either with "Prophet + Ice" (4444) or "Prophet + Clarabit" (4441), since after that either Clarabit or Ice would have been left with no regular choice. So the interval EMin=4429, EMax=4461 would be "solvable, but breakable".

EDIT: "ELimit" needs to be a range IMO, otherwise it will be even easier to break the setup with "low-valued" selections.

Sven

[mar]

Ok I still can't crunch 16 engines but I think I have found EMin, EMax for these 12:

Jazz 444 32-bit 2299
ECE 11.01 2295
FireFly 2.5.10 2286
KMTChess 1.2.1 32-bit 2284
Chesley r323 2258
Parrot 07.07.22 2240
Prophet 2.0 2229
Kurt 0.9.2 32-bit 2220
Ice 0.1 2215
Clarabit 1.00 2212
Carballo 0.5 32-bit 2198
Bubble 1.5 2189

Ok I say EMin = 4387, EMax = 4594 => always solvable (and unbreakable) for these 12

EDIT: EMin = 4429, EMax = 4528 if we add the "half" rule
note that AbsoluteMin = 4387, AbsoluteMax = 4594; So there is only ONE solution in this case (the full legal interval)

[Sven]

Ok I still can't crunch 16 engines but I think I have found EMin, EMax for these 12:

Jazz 444 32-bit 2299
ECE 11.01 2295
FireFly 2.5.10 2286
KMTChess 1.2.1 32-bit 2284
Chesley r323 2258
Parrot 07.07.22 2240
Prophet 2.0 2229
Kurt 0.9.2 32-bit 2220
Ice 0.1 2215
Clarabit 1.00 2212
Carballo 0.5 32-bit 2198
Bubble 1.5 2189

Ok I say EMin = 4387, EMax = 4594 => always solvable (and unbreakable) for these 12

EDIT: EMin = 4429, EMax = 4528 if we add the "half" rule
note that AbsoluteMin = 4387, AbsoluteMax = 4594; So there is only ONE solution in this case (the full legal interval)

Can we find a tighter interval than [4387 .. 4594] for these 12 that is unbreakable, with or without "half" rule?

Maybe also a tighter one than [4429 .. 4528]?

Sven

[mar]

Ok I still can't crunch 16 engines but I think I have found EMin, EMax for these 12:

Jazz 444 32-bit 2299
ECE 11.01 2295
FireFly 2.5.10 2286
KMTChess 1.2.1 32-bit 2284
Chesley r323 2258
Parrot 07.07.22 2240
Prophet 2.0 2229
Kurt 0.9.2 32-bit 2220
Ice 0.1 2215
Clarabit 1.00 2212
Carballo 0.5 32-bit 2198
Bubble 1.5 2189

Ok I say EMin = 4387, EMax = 4594 => always solvable (and unbreakable) for these 12

EDIT: EMin = 4429, EMax = 4528 if we add the "half" rule
note that AbsoluteMin = 4387, AbsoluteMax = 4594; So there is only ONE solution in this case (the full legal interval)

Can we find a tighter interval than [4387 .. 4594] for these 12 that is unbreakable, with or without "half" rule?

Maybe also a tighter one than [4429 .. 4528]?

Sven

If my implementation is correct (exhaustive search), then I fear no, it's impossible