29 Posts
BoardGameGeek» Forums » Gaming Related » Trades
Subject: Math trade algorithms
Your Tags:  Add tags 
Popular Tags:  View All]  [

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?
 [+] Dice rolls

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
 [+] Dice rolls
 Hmmm, I like this result, I would have got my first choice.
 [+] Dice rolls

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
 [+] Dice rolls

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...
 [+] Dice rolls

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 choicesIt 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.)
 [+] Dice rolls
 KenUnited States
Portland
OregonMay 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.
 [+] Dice rolls

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.
 [+] Dice rolls

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.

 Last edited Thu Dec 1, 2005 3:06 pm (Total Number of Edits: 1)
 Posted Thu Dec 1, 2005 2:52 pm
 [+] Dice rolls

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.
 [+] Dice rolls

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."
 [+] Dice rolls

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?
 [+] Dice rolls

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.

 Last edited Thu Dec 1, 2005 10:34 pm (Total Number of Edits: 1)
 Posted Thu Dec 1, 2005 10:32 pm
 [+] Dice rolls

Lindsey wrote:Another, potentially more directly useful paper is Gopal Pandurangan "On a simple randomized algorithm for finding a 2factor in sparse graphs."It also contains:
http://www.cs.purdue.edu/homes/gopal/rgh.pdf
which gives an explicit algorithm for finding 2factors.
"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.
 [+] Dice rolls
 I think we even do it for fun . . . every time we play Elfenland (or think about travelling salesman variants in general).
 [+] Dice rolls
 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.
 [+] Dice rolls

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.
 [+] Dice rolls
 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.
 [+] Dice rolls

Gecko23 wrote:[from the Pandurangan paper]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.
"Finding Hamiltonian cycles in graphs is a difficult NPhard problem that remains NPhard even when restricted to sparse Hamiltonian graphs"
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.
 [+] Dice rolls

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.
 [+] Dice rolls

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.
 [+] Dice rolls

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.
 [+] Dice rolls

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.
 [+] Dice rolls

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.
 [+] Dice rolls
 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.
 [+] Dice rolls