This is more for Nate Smith, but someone else may be able to answer the question.
Nate, could you send me your Access database. I really don’t want all the data, but just the structure. If you can’t do that, could you at least send me the code that forms that match lists. I am wondering if there is a way to change it to prevent a team from being partners / oppoents with another team more than once. Team 201 was against HOT three times. Not that i can really complain, but i just don’t think that that was fair. I know that at every competition we had a team at least twice for either partner/oppoent. I would be happy to see if there is a way to prevent this from happening. I would just try this on my own, but i need to know if you have the code written so that each team was assigned to 4 matches, or if each match was assigned 4 teams. I understant that this would be some extra code, but i think that it would be for the better. Being ‘partly random’ i think is better that totaly ‘random’. I mean, the odds that out of 22 other teams we are against the same one 3/4 times is very small if done purely by chance. BUT… because of the way that the code must make sure that every team plays 4 times, i think that some teams may be ‘favored’ to play with/against other teams. I’m not sure if you could do this w/o talking to the OCCRA people because you are removing total ‘randomness’, but i think it would allow teams a better chance of having the same ‘hardness’
I agree 100%, we at Groves noticed that we would be paired with a team then go against them in a later match. It looked like 5 teams were grouped together in various combonations making our so-called random pairings.
The way that the code is structured(at least AFTER the Rochester HS event) is such that under a # of teams divisible by 4(since there’s 4 teams in a match), you will never see an ally repeat. However, due to the nature of a 4 teams per match structure, unless you have an even multiple of 4 teams, you will see some overlap in the match sets. In an attempt to keep the pairings code from being overly restrictive and causing the program to lock up trying to meet an impossible condition, most of the pairings safeguards(ally repeat, top 4 not paired together, etc.) are disabled when generating these “overlap” matches.
Also, for those of you familiar with Visual Basic, there is a Randomize Timer line at the beginning of the generation routine. For those of you not familiar with what this does, it “seeds” the random number generator(the Randomize part) based on the # of seconds since midnight(the Timer part).
Here’s a rough pseudocode of how the generation takes place:
Get Random Team IDs for the red alliance.
If one of the following conditions are true, go back to #1
-Team IDs are the same
-Teams have been allied before in this tournament
-Teams are not currently both in the top 4 of the overall rankings
-Teams are not currently in the bottom 4 of the overall rankings
-Teams are not currently used in this match set
Set red teams as “used” for this match set
Get Random Team IDs for the blue alliance.
If one of the following conditions are true, go back to #4
-Team IDs are the same
-Teams have been allied before in this tournament
-Teams are not currently both in the top 4 of the overall rankings
-Teams are not currently in the bottom 4 of the overall rankings
-Teams are not currently used in this match set
Set blue teams as “used” for this match set
Count Remaining teams for this set. If remaining > 4, go to 1.
If remaining = 0 and match sets remaining > 0, reset all team used flags and go to 1.
If Remaining =0 and match sets remaining = 0, then all done!
[NOTE: you only get here if there’s less than 4 teams remaining to be picked from]
Scan through teams in internal ID order(not team # order), looking for teams without a match in this set, and assign to positions as found.
Clear used flags for all teams but those just found in #10, and randomly assign teams for the remaining slots.
Set used flags for randomly selected teams, then go back to #1
As you can see, there are some safeguards to help prevent repeat alliances. Repeat opponents I chose not to do for several reasons:
Due to the code preventing repeat alliances, the odds are extremely slim of a complete repeat match(same partner, BOTH opponents the same) occurring. I decided that since no match is a true repeat unless all 4 teams have played together before, a repeat opponent check would not be necessary.
Also, even with the existing code, I was forced to put in a counter which incremented every time the code had to restart part of the sequence because one of the conditions was not met. Whenever the counter reached 1000(which, by looking at the match generation logs, I can see happened on several occasions), the entire match generation routine would reset and restart. Adding a requirement which would in essence eliminate two additional teams from the running after every cycle would be overly restrictive.
What does everyone think of a system that put more emphasis on whether you won or not, over how high your score was? This game really changed between qualification rounds and elimination rounds. Is this a good thing?
What if seedings were made based on your win-loose ratio? (Like football and most other sports) Would something akin to the BCS rankings be better in the end? Would this go against the principals of OCCRA?
*Originally posted by Jim Meyer *
**This game really changed between qualification rounds and elimination rounds. Is this a good thing?
**
Well, personally, i think that the 2002 FIRST game changed even more in the finals. But that was becuase of the 3 * looser score (which was dumb)
I think that the differences in OCCRA this year were ok.
*Originally posted by Jim Meyer *
**What does everyone think of a system that put more emphasis on whether you won or not, over how high your score was?
What if seedings were made based on your win-loose ratio? (Like football and most other sports) Would something akin to the BCS rankings be better in the end? Would this go against the principals of OCCRA?
**
Personally, I think that making that change would be closer to the principals of OCCRA. This way, it would not matter if you creamed the other team, just if you won or not. It would be very interesting to see how that would turn out. Also, making that switch would increase the need for defense. You would need to just make sure your score is above your oppoents score. Now thinking about it, I guess that it may not be all that good. Some bots main thing would be just to eliminate their oppoents score, and just give them 1 point. Not sure.
In response to Nate, i can see how you don’t check for oppoents. However, if can really hurt a team’s avg. qp when they are paired with ‘not the best’ teams agains a really good team.
Personally, I’m not really sold on alliances. In the real world, people need to work together, but they don’t just begin to do so at the last minute. I mean, in football, do they have a bunch of players and just throw them together into random teams on the day of the game? - No, they deiced in the beginning who will play with who. So… i guess that if they did want alliances, it would be better to have the same one for the entire season. Then allow the two teams to desing their bots to be with one and other. If they paried ‘rookie’ teams with the older teams, it would really help the younger teams. I really don’t know. Just a thought.
I think that the main weakness of this years competition were the alliances. It would work much better if we were paired with a team right from the kickoff and keep them as partners from then on would work better. Because some teams built specialized bots (high or low), while some built all around bots. This meant the average score didn’t ability of a bot, but rather its ability to compliemnt another. I guess neither W/L or points are an acuarte way to messaure the quality of a robot when in pairs. If it were 1 on 1, I’m all for W/L it just makes more sense as far as I’m concerned.
*Originally posted by Rabid Robots *
**I think that the main weakness of this years competition were the alliances. It would work much better if we were paired with a team right from the kickoff and keep them as partners from then on would work better. Because some teams built specialized bots (high or low), while some built all around bots. This meant the average score didn’t ability of a bot, but rather its ability to compliemnt another. I guess neither W/L or points are an acuarte way to messaure the quality of a robot when in pairs. If it were 1 on 1, I’m all for W/L it just makes more sense as far as I’m concerned. **
I would definatly agree. I didn’t like the alliances. I think that it would be neet to try to have one alliance for the entire season. I would help the new teams a lot.
I guess I was pretty off-topic now that I look back. What I had done was went and talked with a Statistician in our group who has a strong interest in game theory. I asked him about methods people use for match pairing and we ended up talking about how OCCRA (and FIRST) are really different than all the other types of competitions he is familiar with, like Backgammon, Scrabble, Euker (sp?), etc. It got me thinking about why we are different. I’ve heard Dean Kamen talk about that in FIRST he wants people to achieve goals, not prevent others from doing so. I believe this is what lead us into this crazy average score qualification matches where you can make up for losses by achieving really high scores (something we were really good at).
The problem is, for the most part, that it is easier to play defense in OCCRA this year than it is to play offense. It is far easier to just park in front of the goal than it is to pick up balls and try to put them in the goal. I believe last year was better in this aspect because the huge goal made it very difficult to see your robot on the other side of the goal.
My whole point is that if we go to a 1 on 1 format where winning is what is important, we can create a much better seeding process and in the end I believe a better elimination tournament. If we keep the good lessons from FIRST like having 4 player stations for 2 robots you can play nearly twice as many matches because one team can set up while the other is leaving the playing field, and therefore play the same number of matches.
I have found an individual who has put a lot of effort into generating 2 vs. 2 pairings for bridge competitions that eliminates same partner pairing and minimizes repeat opponent pairings. He has made a lot of his results available for free on the internet (as long as you give him the credit). Here is a reply he sent to and e-mail of mine and a link to his web page:
[email protected] wrote:
> Now to the issue, both competitions use a two vs. two tournament style
> where the matches are “randomly” generated, with some restrictions applied.
> … The number
> of teams participating in OCCRA us usually in the range of 15 - 25, and for
> FIRST 45 - 100 and the number of matches is typically 5 to 11.
> matches are also set up so that every team plays a minimum number of
> matches (like 6) and as small a group as possible (1 - 3 teams) play one
> extra match.
(I like to use the word “rounds” for a collection of “matches”.)
Here are some thoughts…
My program is indeed well-suited to pick two vs two matches.
My program will not understand the “extra match” part.
My program is interruptible. It will continue to improve until
any of several conditions occur. A keyboard interrupt will
output the best solution found.
My code is free. You can download, tweak, etc. The links to
the code might not work though, let me know. My brother has
run it with the Gnu compiler under Windows.
With 5 rounds, more than 25 people should be easy, this will be
roughly scaleable up to say 11 rounds for 50 or more people.
> I believe all of our combinations of teams and matches would make it quite
> difficult to do the pairings ahead of time.
Actually, you can do the setups for 25-100 people ahead of time and
do something like N/5 rounds. These might be good enough to just
use the first set of rounds and ignore the extra. For the lower
numbers of people (or the higher numbers of rounds) it might be a
bit tougher to do ahead of time, because of the amount of time the
program takes.
> … I’ve also thought about assigning a full set of
> partners (100 unique partner sets for 50 matches) and then focusing on who
> will compete against whom.
That seems like a different kind of competition, since learning
to cooperate with your partner would be a major factor. However,
I have done a version of my program which works exclusively on
“pairs”. We have prepared charts for N teams playing N-1 rounds
for up to about N=40. They seem to get harder for larger N but
maybe playing N-2 or N-3 rounds would make it easier. Again, if
you have a perfect setup for 30 teams playing 29 rounds you can
just use the first 11 rounds or whatever.
We obviously have a lot to consider for 2003. I agree that the multiplication of 2 numbers to generate a “monstor score” has bad side effects, but it did encourage the wide range of designs and strategies we saw this year. If you do not reward scoring enough, everybody builds totally defensive machines and strategies that can be very boring. Personally, I would still like to see the importance of winning elevated in the seeding scheme (as it was last year when match scores were much lower). Devising a game where there is no simple, easy solution (like “parking in front of the goal”) is not always easy to do. I also hope that the game committee considers some totally different types of games. Contrary to what I’ve seen in a few of the postings here, alliances seem to be strongly supported by the survey respondants; we are likely to keep some kind of alliance setup, but its nature could change drastically. The committee has talked at length about keeping the same alliance partner(s) all year, starting from kick-off. As soon as FIRST ends, the committee will begin meeting to discuss all these ideas. We should have a game developed before we break for summer vacations. I hope all of you who have given this a lot of thought will come to a few of the committee meetings and get your input before the group.
I’m always looking for ways to improve the pairings system, and I’m going to read over the code that Jim linked to in order to see if there’s a way I can integrate it into the code for next year. I’ll see what else I can come up with as well…
I think the real key is how he evaluates things. He doesn’t use a “keep tyring unil it’s perfect” method but uses a scoring system to evaluate the quality of any given layout.
You could possibly have a system where repeat partners count 100 points, double repeat opponents count 10 points, and single repeat opponents count 1 point. You could evaluate an entire tournament this way, adding the points up for each match. Paul Chamberlain has some pretty sophisticated methods for trying new combinations but you could just simply run your existing program 1000 times (or how ever many time may permit) evaluate them all based on this point system and choose the best one.
Anyway, just some ideas. This is a very interesting and challenging problem.