Board index FlightGear The FlightGear project News

15 years of FlightGear, screenshot contest

News from the ever evolving world of FlightGear.

Re: 15 years of FlightGear, screenshot contest

Postby curt » Tue Aug 07, 2012 1:25 pm

I think I see where you are coming from with a bubble sort comparison, but I don't think it's equivalent. Element rankings are based on win/loss percentage (more of a statistical approach.) In a bubble sort we can only swap adjacent elements. In a worst case bubble sort, if the highest ranking item starts at the bottom of the list it may take n*n passes to get everything properly placed -- but in our voting system a rough win/loss percentage can be arrived at very quickly with only a few comparisons -- and elements shift position directly without needing to "bubble" up. For example, if an element has won 4 of 6 contests (66.6%) and then wins the next contest (now 5 of 7 = 71.4%) it could jump up many places with a single comparison.

I see an analogy to a mipmapping system, where we start out with a really low level mipmap and as votes are casts we add detail and then we can add more and more detail as votes are cast over time. But factor in integer math, voting over a period of a couple weeks, voting by many people at different times with potentially wide ranging preferences and it becomes more interesting and harder to predict.

Another analogy would be the "schedule" for a sports league where each team plays every other team twice (home and away.) 2*(n-1) matches. Is this enough to perfectly rank the entries if we have a consistent scoring mechanism? The problem in computer science is that we'd then still have to sort by rank to actually spit out the list in correct order.

Edit: each entity would play 2*(n-1) rounds, but there would be n/2 matches in each round which does put us at bubble sort level comparisons. :-) We have 165 entries -- bubble sort would require 165*165=27,225 comparisons. At the moment we have done about 28,000 comparisons with our voting system and each entry has played about 2*(n-1) rounds. So I still contend that this is not bubble sort (we get good results much earlier, and we can play much longer and factor in more "human element") but there are undeniable parallels. :-)

Here is wikipedia's take on our approach:

http://en.wikipedia.org/wiki/Pairwise_comparison
curt
Administrator
 
Posts: 1117
Joined: Thu Jan 01, 1970 12:00 am
Location: Minneapolis, MN

Re: 15 years of FlightGear, screenshot contest

Postby Thorsten » Tue Aug 07, 2012 2:47 pm

Simple argument: Assume only I vote. Assume further that there is the best-ranked image winning against all others and the second-best ranked image, winning against all others except the best. How many rounds do I need to vote in order to tell them apart?

I can only tell them apart in the one case when I'm seeing them both on the screen. The probability of that occurring is 1/165 * 1/164, i.e. about 1/27.000. I need to cast about this number of votes to be relatively sure to discriminate between my two leading choices if I don't want to 'game' the system by doing tactical votes.
Thorsten
 
Posts: 10157
Joined: Mon Nov 02, 2009 8:33 am

Re: 15 years of FlightGear, screenshot contest

Postby curt » Tue Aug 07, 2012 3:14 pm

This voting system is much more fun than a bubble sort though because many people are voting, preferences and impressions can change, there is "noise" in the system. The statistical noisiness can actually give us good/useful results far quicker than n^2, but also means we may not have "perfect" ordering even far beyond n^2 matches.

There are many cases where statistics, randomization, and probability can get us to a "good" solution much more quickly than an exhaustive approach which presumably finds the optimal solution (except in our case the comparisons are subjective so there is no optimal ordering and no way to know if we've achieved it.)

In our system it's statistically possible (although very unlikely) that the two top images will never be directly compared against each other. And on average the better images will win more matches, even in the early rounds. So a bubble sort has no validity until n^2 comparisons are finished (or we finish an entire pass without needing to swap any elements), but our voting system evolves a good idea of the final results early on (the current grand champion picture actually jumped right to the top early on and has stayed there -- but a couple other images have made challenging moves and have gotten close so it wouldn't surprise me if this image ultimately got knocked off the throne, and it wouldn't surprise me if it hangs on for victory.) There is a very dynamic unpredictable nature to our system that taps inside people's heads to their unconscious preferences, yet in other ways is very deterministic.

I think the key difference (aside from underlying mechanics) is that a statistical approach achieves a good solution right away and you can run the system longer and longer to get a better solution (but you may never reach an optimal solution.) A pure bubble sort finds and optimal solution, but you have to wait to the end to see it.

In a past life I worked on a project that was basically an A* AI search. However rather than exhaustively search the entire 7 dimensional space which would have been impossible, we partitioned the search space "statistically" and used multiple processors to each search out a random path. The result was that we could almost always find a good solution quickly, but we could throw in more processors or run more searches to find better solutions -- and our results improved super-linearly with the number of CPU's. The difference here is (for example) can I find a way to remove the oil filter from my car engine without disassembling any other parts versus finding the "optimal" shortest path out of the engine compartment. If I can find a "good" route in 1 second statistically, why wait for the optimal route to be computed in 100 hours after an exhaustive search?

I still maintain the two approaches are different in significant ways, but converge towards a similar result over enough time. And our system is much more interesting than a pure computer science style bubble sort. :-)
curt
Administrator
 
Posts: 1117
Joined: Thu Jan 01, 1970 12:00 am
Location: Minneapolis, MN

Re: 15 years of FlightGear, screenshot contest

Postby Thorsten » Tue Aug 07, 2012 4:14 pm

I'm not saying it's bad, or not interesting, or should be replaced. I'm just saying its characteristics could have been anticipated up front :D I actually think it's quite neat, because it's comparatively hard to cheat or vote tactically even without user verification and finite number of votes. Sorry if that came across the wrong way.
Thorsten
 
Posts: 10157
Joined: Mon Nov 02, 2009 8:33 am

Re: 15 years of FlightGear, screenshot contest

Postby curt » Tue Aug 07, 2012 4:32 pm

It has been fun to think about the nature of the voting system. And the human element makes it that much more interesting and leads to some extra dynamics. Thus even though we have more then n^2 comparisons now made, I still expect some shuffling and still am hoping more people vote. Like you say, this is a hard system to game. If you click randomly, you are just adding noise and presumably not skewing the actual results. If you intentionally miss vote, or intentionally vote for your own entry, you don't see it often enough relative to all the other people voting to hopefully make a big statistical difference.
curt
Administrator
 
Posts: 1117
Joined: Thu Jan 01, 1970 12:00 am
Location: Minneapolis, MN

Re: 15 years of FlightGear, screenshot contest

Postby Johan G » Wed Aug 08, 2012 6:42 pm

While the system is fascinating, my ears are not pointed enough that I can follow this discussion effortlessly. :wink:
Low-level flying — It's all fun and games till someone looses an engine. (Paraphrased from a YouTube video)
Improving the Dassault Mirage F1 (Wiki, Forum, GitLab. Work in slow progress)
Johan G
Moderator
 
Posts: 5296
Joined: Fri Aug 06, 2010 5:33 pm
Location: Sweden
Callsign: SE-JG
IRC name: Johan_G
Version: 3.0.0
OS: Windows 7, 32 bit

Re: 15 years of FlightGear, screenshot contest

Postby Thorsten » Thu Aug 09, 2012 6:47 am

While the system is fascinating, my ears are not pointed enough that I can follow this discussion effortlessly.


This comes to my mind...

Image
Thorsten
 
Posts: 10157
Joined: Mon Nov 02, 2009 8:33 am

Re: 15 years of FlightGear, screenshot contest

Postby Gijs » Fri Aug 17, 2012 11:20 pm

Results of the screenshot contest are now up at flightgear.org/contest! I would like to thank all people who sent in screenshots and/or voted on their favourites. Congratulations to the winning photographers!
Airports: EHAM, EHLE, KSFO
Aircraft: 747-400
User avatar
Gijs
Moderator
 
Posts: 9306
Joined: Tue Jul 03, 2007 2:55 pm
Location: Amsterdam/Delft, the Netherlands
Callsign: PH-GYS
Version: Git
OS: Windows 10

Re: 15 years of FlightGear, screenshot contest

Postby prince.muga » Wed Aug 22, 2012 11:12 am

yey! atleast I got 56th and 123rd.....
:D


56th
Image


123rd
Image
"Just remember, if you crash because of weather, your funeral will be held on a sunny day."

- Layton A. Bennett

F-16 THE BEST :D

EAF-013
User avatar
prince.muga
 
Posts: 122
Joined: Mon Apr 09, 2012 9:20 am
Callsign: Carrier,EAF13
Version: latest
OS: Windows 7

Previous

Return to News

Who is online

Users browsing this forum: No registered users and 1 guest