Lindsey Dubb
United States Seattle Washington

I only have a pretty basic knowledge of graph theory, but was wondering if someone else here might be able to add some knowledge about cycles on graphs which could improve the algorithms used for math trades. I’m thinking specifically about the “maximize trades” algorithm, but it might be possible to come up with other worthwhile algorithms, too.
From some fiddling around with Google, I came across an apparently related topic in graph theory which talks about algorithms for finding 2covers on directed graphs, which looks pretty closely related to (but not quite the same as) the maximize trade algorithm. But a “cover” uses all vertices (i.e., game entries) in the graph, which isn’t generally possible with the usual preferences people turn in for their trades. So instead of finding a cover, we want to find the maximum number of vertices in a set of vertex disjoint cycles.
So another promising (related) direction were studies of vertex disjoint cycles on directed graphs. But most of the articles I found were about maximizing the number of cycles on such a graph, not on maximizing the number of vertices contained in the union of all of the cycles.
One particularly promisinglooking paper was Hong Wang "On the maximal number of vertices covered by disjoint cycles." But that paper appears to find minimum bounds on the number of vertices on such a graph, and doesn’t say how to find a maximal set of vertices. But maybe some of its references would be useful. The paper is online at http://ajc.maths.uq.edu.au/pdf/21/ajcv21p179.pdf
Another, potentially more directly useful paper is Gopal Pandurangan "On a simple randomized algorithm for finding a 2factor in sparse graphs." http://www.cs.purdue.edu/homes/gopal/rgh.pdf which gives an explicit algorithm for finding 2factors.
So, does anyone familiar with graph theory know if this stuff is in the right direction, or (better yet) if this is really a solved problem?

B. Perry
United States Colorado Springs Colorado

I've been working on my own program and testing it against several previous results, including the recent math trade (http://boardgamegeek.com/geeklist.php3?action=view&listid=11...).
The recent trade involved 47 trades, although someone claims to have found a trade solution with 50 trades. My trade mapping program found a solution involving 56 trades (I've quoted it below).
The primary complication in my code is that it's too timeconsuming to be terribly useful right now. In this particular case, it can find 55 trades in 5 minutes and 56 in 45 minutes. For other cases time varies as well. I'm still tweaking the algorithm, but it's increasingly obvious that it will eventually require a complete overhall to be more reliable and useful than what is already available.
The current algorithm uses a pair of mutuallyrecursive funtions to check every possible solution. I need some way of weeding out bad solutions before checking them or pairing up games that must trade together (if they are to trade at all).
Quote: 56 TRADES FOUND:
1 receives from 115 115 receives from 97 97 receives from 10 10 receives from 45 45 receives from 94 94 receives from 76 76 receives from 129 129 receives from 109 109 receives from 119 119 receives from 148 148 receives from 11 11 receives from 73 73 receives from 72 72 receives from 120 120 receives from 122 122 receives from 53 53 receives from 41 41 receives from 49 49 receives from 99 99 receives from 108 108 receives from 1
2 receives from 33 33 receives from 84 84 receives from 55 55 receives from 150 150 receives from 39 39 receives from 128 128 receives from 51 51 receives from 147 147 receives from 125 125 receives from 64 64 receives from 83 83 receives from 96 96 receives from 26 26 receives from 93 93 receives from 19 19 receives from 38 38 receives from 116 116 receives from 149 149 receives from 50 50 receives from 132 132 receives from 2
14 receives from 30 30 receives from 25 25 receives from 62 62 receives from 85 85 receives from 14
71 receives from 100 100 receives from 77 77 receives from 136 136 receives from 153 153 receives from 71
86 receives from 95 95 receives from 86
117 receives from 131 131 receives from 117



Hmmm, I like this result, I would have got my first choice.

Chris
United States Michigan
http://www.pennyarcade.com/comic/2007/03/28

Damn, this would have been WAY better for me than the official result! Ah well!
My $0.02 on the algorithm: I would much rather run something like yours where you run it once, it takes 45 minutes, but comes out with a superior result. Matthew's algorithm only takes 23 minutes to run, but come up with many suboptimal results before finding a high number of trades...and as you have seen, even then it isn't the highest possible result.
Chris

Michelle Zentis
United Kingdom London

Damn, your trade finder would have gotten me Europe Engulfed AND Siege of Jerusalem, my two top choices (instead of my nexttolast choice for one and no trade for the other)!
Sometimes it's better not to know...

B. Perry
United States Colorado Springs Colorado

willythesnitch wrote: Hmmm, I like this result, I would have got my first choice.
caesarmom wrote: your trade finder would have gotten me Europe Engulfed AND Siege of Jerusalem, my two top choices
It does a good job of prioritizing simply because as it looks for a chain, it starts by checking your first want. (The other engine randomly picks a want when searching for a chain. That's why multiple runs reveal varied results.)

Ken
United States Portland Oregon
May I pass along my congratulations for your great interdimensional breakthrough. I am sure, in the miserable annals of the Earth, you will be duly enshrined.  Lord John Whorfin

Quote: Sometimes it's better not to know...
Yep. I would have been included in a trade if this process had been used.
Sour grapes.

E.R. Burgess
United States Glendora California

We'll be running on both this one and MKG's for the final trade on the Superior Game Math Trade v2. I'll be providing the wants list to Kayvon so he can run it while I run it over on MKG's. We'll have to see which one comes up with the most. Whatever the case, we've got some really amazing games on the list so I'm guessing we'll have a lot of happy people.
Post your stuff tonight! As of noon tomorrow, users can post a third item and then it will lock up quickly, I know.

George Kinney
United States Bellefontaine Ohio

Quote: Damn, this would have been WAY better for me than the official result!
Well, there is a gotcha lurking here. This result may just be one of the maximums, there could be others.
I too have been tinkering with this for a while now, and took the most basic, bruteforce, deterministic method I could. (Also incredibly slow...)
I set up an algorithm to process all the want lists to produce a list of all possible trade 'loops' that exist in the data. (I guess a graph theory person would call them 'cycles')
It doesn't care about entry order, and it isn't paying attention to 'loop' length at this point, just trying to find a path from user1 to user2 for every user via their 'want' lists.
Then it proceeds to put together every possible nonintersecting set of 'loops' that it can. The goal of course is to come up with the (or possibly several) sets of nonintersecting 'loops' that cover the most entries as possible.
The first part, finding all the 'loops' takes a few seconds. The second part, calculating all the possible unique sets of loops takes forever. This last trade's want list produces 19559 loops with some obscenely high number of potential combinations.
Basically, I pick a loop, then cull all the remaining ones that intersect it from the complete list. Then add one of those to the current set and repeat the process. I've tried to speed up the culling by precalculating a dictionary, that for each user contains a list of the loops they don't belong to. Then I can just compare those 'exclusive' lists among each other instead of the entire database. But it is still far, far too slow. (Is there a fast way to find the optimal set from all permutations of 19559 candidate loops?)
Plus, I'm not sure what an intelligent algorithm for picking the next potential candidate from the remaining list would be. Currently I'm just picking the longest each pass, which seems to give a correct answer, but I certainly can't prove it.
Currently, the 5075 entry lists take about 25 minutes to run through, and the 100+ entry lists take hours. Of course, since I'm doing an exhaustive search, the length of the want lists directly impacts the time needed to do the search.
I have noticed some interesting things though. Like I mentioned above, multiple 'peaks' in the data are common. If you just do a simple check of whether the current list is longer than the last maximum, you stand to miss other ones. Then of course you need some way to choose between them for a final answer.
Also, I tried directing the final combination search by picking paths that favored 'popular' games. In other words, the user offering the most wanted game gets to pick first. In almost every trade over the past few months, this results in 1020% fewer trades.
Just for giggles, here's the output I got after a very long wait (formatted in the same manner as the current software). I didn't have a check in there for folks requesting their own game, so 96 is trading with himself, and like I said, it might just be one of the possible solutions: 109 sends game(s) to 13 and receives game(s) from 72 72 sends game(s) to 109 and receives game(s) from 35 35 sends game(s) to 72 and receives game(s) from 42 42 sends game(s) to 35 and receives game(s) from 86 86 sends game(s) to 42 and receives game(s) from 114 114 sends game(s) to 86 and receives game(s) from 97 97 sends game(s) to 114 and receives game(s) from 10 10 sends game(s) to 97 and receives game(s) from 45 45 sends game(s) to 10 and receives game(s) from 125 125 sends game(s) to 45 and receives game(s) from 3 3 sends game(s) to 125 and receives game(s) from 76 76 sends game(s) to 3 and receives game(s) from 129 129 sends game(s) to 76 and receives game(s) from 120 120 sends game(s) to 129 and receives game(s) from 122 122 sends game(s) to 120 and receives game(s) from 148 148 sends game(s) to 122 and receives game(s) from 11 11 sends game(s) to 148 and receives game(s) from 83 83 sends game(s) to 11 and receives game(s) from 1 1 sends game(s) to 83 and receives game(s) from 33 33 sends game(s) to 1 and receives game(s) from 84 84 sends game(s) to 33 and receives game(s) from 55 55 sends game(s) to 84 and receives game(s) from 150 150 sends game(s) to 55 and receives game(s) from 19 19 sends game(s) to 150 and receives game(s) from 38 38 sends game(s) to 19 and receives game(s) from 128 128 sends game(s) to 38 and receives game(s) from 51 51 sends game(s) to 128 and receives game(s) from 147 147 sends game(s) to 51 and receives game(s) from 41 41 sends game(s) to 147 and receives game(s) from 49 49 sends game(s) to 41 and receives game(s) from 99 99 sends game(s) to 49 and receives game(s) from 77 77 sends game(s) to 99 and receives game(s) from 136 136 sends game(s) to 77 and receives game(s) from 153 153 sends game(s) to 136 and receives game(s) from 71 71 sends game(s) to 153 and receives game(s) from 21 21 sends game(s) to 71 and receives game(s) from 80 80 sends game(s) to 21 and receives game(s) from 94 94 sends game(s) to 80 and receives game(s) from 13 13 sends game(s) to 94 and receives game(s) from 109
132 sends game(s) to 50 and receives game(s) from 2 2 sends game(s) to 132 and receives game(s) from 116 116 sends game(s) to 2 and receives game(s) from 149 149 sends game(s) to 116 and receives game(s) from 50 50 sends game(s) to 149 and receives game(s) from 132
30 sends game(s) to 14 and receives game(s) from 25 25 sends game(s) to 30 and receives game(s) from 62 62 sends game(s) to 25 and receives game(s) from 85 85 sends game(s) to 62 and receives game(s) from 14 14 sends game(s) to 85 and receives game(s) from 30
117 sends game(s) to 131 and receives game(s) from 131 131 sends game(s) to 117 and receives game(s) from 117
119 sends game(s) to 138 and receives game(s) from 138 138 sends game(s) to 119 and receives game(s) from 119
96 sends game(s) to 96 and receives game(s) from 96 96 sends game(s) to 96 and receives game(s) from 96
Another bit of trivia, the single longest loop in the overall data was this 46 entry monster: 33 sends game(s) to 64 and receives game(s) from 35 35 sends game(s) to 33 and receives game(s) from 42 42 sends game(s) to 35 and receives game(s) from 86 86 sends game(s) to 42 and receives game(s) from 95 95 sends game(s) to 86 and receives game(s) from 76 76 sends game(s) to 95 and receives game(s) from 45 45 sends game(s) to 76 and receives game(s) from 94 94 sends game(s) to 45 and receives game(s) from 13 13 sends game(s) to 94 and receives game(s) from 109 109 sends game(s) to 13 and receives game(s) from 119 119 sends game(s) to 109 and receives game(s) from 148 148 sends game(s) to 119 and receives game(s) from 11 11 sends game(s) to 148 and receives game(s) from 73 73 sends game(s) to 11 and receives game(s) from 72 72 sends game(s) to 73 and receives game(s) from 120 120 sends game(s) to 72 and receives game(s) from 122 122 sends game(s) to 120 and receives game(s) from 53 53 sends game(s) to 122 and receives game(s) from 41 41 sends game(s) to 53 and receives game(s) from 49 49 sends game(s) to 41 and receives game(s) from 99 99 sends game(s) to 49 and receives game(s) from 77 77 sends game(s) to 99 and receives game(s) from 136 136 sends game(s) to 77 and receives game(s) from 84 84 sends game(s) to 136 and receives game(s) from 55 55 sends game(s) to 84 and receives game(s) from 150 150 sends game(s) to 55 and receives game(s) from 19 19 sends game(s) to 150 and receives game(s) from 38 38 sends game(s) to 19 and receives game(s) from 83 83 sends game(s) to 38 and receives game(s) from 62 62 sends game(s) to 83 and receives game(s) from 85 85 sends game(s) to 62 and receives game(s) from 14 14 sends game(s) to 85 and receives game(s) from 30 30 sends game(s) to 14 and receives game(s) from 25 25 sends game(s) to 30 and receives game(s) from 149 149 sends game(s) to 25 and receives game(s) from 50 50 sends game(s) to 149 and receives game(s) from 132 132 sends game(s) to 50 and receives game(s) from 2 2 sends game(s) to 132 and receives game(s) from 116 116 sends game(s) to 2 and receives game(s) from 153 153 sends game(s) to 116 and receives game(s) from 71 71 sends game(s) to 153 and receives game(s) from 117 117 sends game(s) to 71 and receives game(s) from 131 131 sends game(s) to 117 and receives game(s) from 23 23 sends game(s) to 131 and receives game(s) from 125 125 sends game(s) to 23 and receives game(s) from 64 64 sends game(s) to 125 and receives game(s) from 33
But notice that it isn't in the 'maximum' list up above, thus all this time consuming searching that I'd love to escape.

B. Perry
United States Colorado Springs Colorado

Gecko23 wrote: Also, I tried directing the final combination search by picking paths that favored 'popular' games. In other words, the user offering the most wanted game gets to pick first. In almost every trade over the past few months, this results in 1020% fewer trades.
I start with the same thing (most popular entry), but for a different reason. The most popular entry is the easiest to create a chain for. I haven't generated fewer trades than the math trades on file. In every case I generate as many (for smaller lists) or more (for larger ones).
You hit the key, though: processing time. I've increased the speed of my program many times over since my original posting, but it still takes too long to be practical because it is checking every possible combination. As I speed it up, however, my results come faster and more consistently among all the math trades done thus far. I've got another idea to tweak the processing algorithm that I hope will make it more useful.
So far as processing time is such an overwhelming concern, there is a benefit for the mostwanted user: he is all but guaranteed to get a trade (almost definately his top pick). Because my program iterates in order, each user is most likely to achieve his/her top pick.

Jonathan Franklin
United States Seattle Washington

Kayvon,
My sense is that most people would be happy with a better result, even if the program took 24 or more hours to run. As I gather the main issue is that the other one you have to manually run it multiple times, so a set it and forget it model that worked better than the existing one would be popular with both managers and recipients.
Would there be a way to run it so that each time it finds a better result, it sends the new optimal result to a webpage? I have the feeling that people enjoy the process almost as much as the result, so a long runtime could be turned into "entertainment."

B. Perry
United States Colorado Springs Colorado

grandslam wrote: Would there be a way to run it so that each time it finds a better result, it sends the new optimal result to a webpage?
Sure, that'd be easy. (It currently writes to a file, anyway.) The tricky thing is that finding a better solution is an inverse exponential curve. In other words, it'll find 5 better solutions in the first second. It'll maybe find 5 more improved solutions in the next 10 minutes, then not find one for a half hour after that. As time progresses, the space between stumbling upon better solutions increases exponentially. So after the first minute it probably wouldn't change much.
That's a great idea, though. Maybe I'll set it up to do that for the junk trade I'm doing. Do you think people would be patient enough to wait for the next day if the overall list only improved by, say, a couple trades?

Michelle Zentis
United Kingdom London

grandslam wrote: My sense is that most people would be happy with a better result, even if the program took 24 or more hours to run.
I'm not the most patient person (ahem!), but I'm with that thought. George's result was pretty much the same as the real result for me  i.e. nexttolast wish for one of my games and no trade at all for the other.
grandslam wrote: Would there be a way to run it so that each time it finds a better result, it sends the new optimal result to a webpage? I have the feeling that people enjoy the process almost as much as the result, so a long runtime could be turned into "entertainment."
I don't know about that, though! It sounds good in theory, but the AGONY of seeing your dream trade vanish after the next round of computations would be tremendous.

George Kinney
United States Bellefontaine Ohio

Lindsey wrote: Another, potentially more directly useful paper is Gopal Pandurangan "On a simple randomized algorithm for finding a 2factor in sparse graphs." http://www.cs.purdue.edu/homes/gopal/rgh.pdfwhich gives an explicit algorithm for finding 2factors.
It also contains: "Finding Hamiltonian cycles in graphs is a difficult NPhard problem that remains NPhard even when restricted to sparse Hamiltonian graphs"
Of course the offer lists we've been messing with aren't strictly Hamiltonian graphs to begin with. There has been no single path that covered all vertices in any of them that I have seen, and they are directed graphs to boot. But of course the Hamiltonian cycle concept can easily be extended to this situation.
I also found this: "In general, the problem of finding a Hamiltonian circuit is NPcomplete (Garey and Johnson 1983), so the only known way to determine whether a given general graph has a Hamiltonian circuit is to undertake an exhaustive search. Rubin (1974) describes an efficient search procedure that can find some or all Hamilton paths and circuits in a graph using deductions that greatly reduce backtracking and guesswork." from http://mathworld.wolfram.com/HamiltonianCircuit.html
Since we don't up front whether such a path even exists (and in our special case, how many nonintersecting ones there may be), there doesn't seem to be any way to know for certain if any long path is the actual longest (or even if it exists at all) without checking them all.
Which leads me to believe that you either take the nondeterministic approach, which mkgray's program does and the above paper seems to describe, and accept that there is a certain probability it won't give you a good result. Or you go the brute force method and are left searching every single combination, with the only potential improvements being basic optimizations. (Caching computed data, unrolling loops, etc.)
Sigh....
Leave it to us 'geeks to pick a trade method that involves an NPhard problem to solve.

Jonathan Franklin
United States Seattle Washington

I think we even do it for fun . . . every time we play Elfenland (or think about travelling salesman variants in general).

B. Perry
United States Colorado Springs Colorado

The other difficulty with the algorithm is that the longest chain doesn't necessarily yield the maximum result. Sometimes a shorter chain will allow more trades to occur overall.

George Kinney
United States Bellefontaine Ohio

Quote: Sometimes a shorter chain will allow more trades to occur overall.
Usually. But since popular games appear in more want lists, even the short ones can end up intersecting a lot more lists than you might suspect.

B. Perry
United States Colorado Springs Colorado

I found a good example of what I'm talking about. In list http://www.boardgamegeek.com/geeklist.php3?action=view&listi..., it is possible to make a chain of 10 entries. However, it is possible to make 11 trades altogether if you break up that primary chain.

Lindsey Dubb
United States Seattle Washington

Gecko23 wrote: [from the Pandurangan paper] "Finding Hamiltonian cycles in graphs is a difficult NPhard problem that remains NPhard even when restricted to sparse Hamiltonian graphs" Yeah, I sort of figured this kind of exchange would be equivalent to a travelling salesman problem. But although finiding a Hamiltonian cycle is NPhard, finding a 2factor cover can be solved in polynomial time. [A Hamiltonian cycle here is a single trade loop involving every game entry. A 2factor cover is a set of loops (of at least size 2) involving every game entry.] From what I’ve read, this is apparently sometimes used to come up with fast approximate solutions to NPhard problems.
Unfortunately, I’m not sure where I first came across the mention of a polynomial algorithm for 2factor covers. Here’s one reference which cites it as a known fact, though, and gives (offline) references for its solution (apparently by computing a “maximum bipartite matching”).
http://www.inf.ethz.ch/personal/mblaeser/pub/approx02.ps
Anyhow, that does give some hope that there might be a polynomial solution. But finding a cover and finding a set of disjoint cycles which maximize the number of vertices could well be different problems.
Quote: Leave it to us 'geeks to pick a trade method that involves an NPhard problem to solve. Naturally. If it were easy to solve, it wouldn’t really count as a game.

Matt B
United States Tampa Florida

heh
Nearly every real world worthwhile problem turns out to be NPHard. Assigning classes to classrooms is NPHard. Visiting places in an optimal order is NPHard (Traveling Salesperson). bleck The nice thing is, honestly, these problems have such a small search space that I don't know why checking every possibility should take all that long. I'm a grad student in CS, maybe you guys could write a good definition of the problem and send it to me, and I could solve it for you as prep for my qualifiers.

B. Perry
United States Colorado Springs Colorado

arrendek wrote: The nice thing is, honestly, these problems have such a small search space that I don't know why checking every possibility should take all that long.
Yeah, that was my first thought, too. You can imagine my surprise when I found out how incredibly wrong I was. I'm a Computer Engineer myself with a strong CS background, so I've got a fairly good idea what I'm doing.
Since I first made the program, I've speed it up maybe 100 fold (maybe more). It's just not fast enough. I believe I'm getting answers within a few trades of the maximum possible (58 for the trade IV; 50 for the more recent superior trade). It'd just be nice to *know* that I have the absolute maximum possible. With smaller trades I can actually run it to completion. These larger trades, involving 150+ entries, don't permit that.

George Kinney
United States Bellefontaine Ohio

I don't think finding the solution is mystifying to anyone. I know that my program will return the right answer, I just don't know when its going to do it.

B. Perry
United States Colorado Springs Colorado

I finally put my beta utility to the test on a real example: http://www.boardgamegeek.com/geeklist.php3?action=view&listi...
I was able to generate 80 trades by creating one giant, humongous chain.

George Kinney
United States Bellefontaine Ohio

Hmm... I was hoping to confirm that, but I took a different approach, and given the 70000+ unique cycles in that data, I just don't think my puny little PC is up to the task.
I think, and I wish someone would prove me wrong, that there is no actual way to know with certainty that any solution is the best one without visiting them all.
In this latest 'inferior' math trade, the want lists contain 70000+ unique cycles. My last run on a 7000 cycle list produced 50,000 unique nonintersecting sets of cycles, so I guess that this one could contain upwards of 500,000 unique sets, and quite possibly many more.
It it tugs at the back of my mind constantly that some sequences of trades are far more common than others, and there must be a way to take advantage of that information. But so far I have failed to discover that method.
At this point, I am positive that my algorithm will find the set of nonintersecting cycles covering the maximum number of offers. But I can not predict how long it will take, or whether it will exhaust my PCs memory before it gets there.
I am possibly very wrong, but it seems that the only two obvious solutions at this point are to either accept some nondeterminism in finding the answer, or to throw a lot more CPUs at the problem. (or maybe even code this thing in something much faster than Python) Insane as it may sound, I've decided to follow the latter idea.
So now I am hacking away at an XMLRPC based distributed nonintersecting set finder that I may someday seek to unleash on the BGG community. Maybe I could call it 'MathTrade@Home'?
Or maybe I should keep my mouth shut since I don't know that I'll ever get around to finishing it.
Anyways, kudos to Kayvon for sticking his neck out there and running a trade with his implementation.

B. Perry
United States Colorado Springs Colorado

For those that are interested, I've just released a public version of my algorithm. It's called TradeGenie and is available for download from www.kayvon.org. Please try it out and give me some feedback on it.


