Recommend
2 
 Thumb up
 Hide
29 Posts
1 , 2  Next »   | 

BoardGameGeek» Forums » Gaming Related » Trades

Subject: Math trade algorithms rss

Your Tags: Add tags
Popular Tags: Math_Trade_Discussion [+] math_trade [+] Math-Trade-Info [+] [View All]
Lindsey Dubb
United States
Seattle
Washington
flag msg tools
badge
Avatar
mbmbmb
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 2-covers 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 promising-looking 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/ajc-v21-p179.pdf

Another, potentially more directly useful paper is Gopal Pandurangan "On a simple randomized algorithm for finding a 2-factor in sparse graphs."
http://www.cs.purdue.edu/homes/gopal/rgh.pdf
which gives an explicit algorithm for finding 2-factors.

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?
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
B. Perry
United States
Colorado Springs
Colorado
flag msg tools
Avatar
mbmbmbmbmb
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 time-consuming 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 mutually-recursive 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
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Canada
Montreal
Quebec
flag msg tools
badge
Avatar
mbmbmbmbmb
Hmmm, I like this result, I would have got my first choice.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Chris
United States
Michigan
flag msg tools
badge
http://www.penny-arcade.com/comic/2007/03/28
Avatar
mbmbmbmbmb
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 2-3 minutes to run, but come up with many sub-optimal results before finding a high number of trades...and as you have seen, even then it isn't the highest possible result.

--Chris
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Michelle Zentis
United Kingdom
London
flag msg tools
badge
Avatar
mbmbmbmbmb
Damn, your trade finder would have gotten me Europe Engulfed AND Siege of Jerusalem, my two top choices (instead of my next-to-last choice for one and no trade for the other)!

crycrycry

Sometimes it's better not to know...
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
B. Perry
United States
Colorado Springs
Colorado
flag msg tools
Avatar
mbmbmbmbmb
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.)
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Ken
United States
Portland
Oregon
flag msg tools
badge
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
Avatar
mbmbmbmbmb
Quote:
Sometimes it's better not to know...


Yep. I would have been included in a trade if this process had been used. shake

Sour grapes.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
E.R. Burgess
United States
Glendora
California
flag msg tools
designer
publisher
badge
Avatar
mbmbmbmbmb
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.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
George Kinney
United States
Bellefontaine
Ohio
flag msg tools
badge
Avatar
mbmbmbmbmb
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, brute-force, 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 user-1 to user-2 for every user via their 'want' lists.

Then it proceeds to put together every possible non-intersecting set of 'loops' that it can. The goal of course is to come up with the (or possibly several) sets of non-intersecting '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 50-75 entry lists take about 2-5 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 10-20% 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.

 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
B. Perry
United States
Colorado Springs
Colorado
flag msg tools
Avatar
mbmbmbmbmb
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 10-20% 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 most-wanted 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.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Jonathan Franklin
United States
Seattle
Washington
flag msg tools
designer
Avatar
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 run-time could be turned into "entertainment."
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
B. Perry
United States
Colorado Springs
Colorado
flag msg tools
Avatar
mbmbmbmbmb
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?
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Michelle Zentis
United Kingdom
London
flag msg tools
badge
Avatar
mbmbmbmbmb
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. next-to-last 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 run-time 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.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
George Kinney
United States
Bellefontaine
Ohio
flag msg tools
badge
Avatar
mbmbmbmbmb
Lindsey wrote:
Another, potentially more directly useful paper is Gopal Pandurangan "On a simple randomized algorithm for finding a 2-factor in sparse graphs."
http://www.cs.purdue.edu/homes/gopal/rgh.pdf
which gives an explicit algorithm for finding 2-factors.


It also contains:
"Finding Hamiltonian cycles in graphs is a difficult NP-hard problem that remains NP-hard 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 NP-complete (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 non-intersecting 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 non-deterministic 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 NP-hard problem to solve.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Jonathan Franklin
United States
Seattle
Washington
flag msg tools
designer
Avatar
I think we even do it for fun . . . every time we play Elfenland (or think about travelling salesman variants in general).
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
B. Perry
United States
Colorado Springs
Colorado
flag msg tools
Avatar
mbmbmbmbmb
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.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
George Kinney
United States
Bellefontaine
Ohio
flag msg tools
badge
Avatar
mbmbmbmbmb
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.

 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
B. Perry
United States
Colorado Springs
Colorado
flag msg tools
Avatar
mbmbmbmbmb
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.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Lindsey Dubb
United States
Seattle
Washington
flag msg tools
badge
Avatar
mbmbmb
Gecko23 wrote:
[from the Pandurangan paper]
"Finding Hamiltonian cycles in graphs is a difficult NP-hard problem that remains NP-hard 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 NP-hard, finding a 2-factor cover can be solved in polynomial time. [A Hamiltonian cycle here is a single trade loop involving every game entry. A 2-factor 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 NP-hard problems.

Unfortunately, I’m not sure where I first came across the mention of a polynomial algorithm for 2-factor 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 NP-hard problem to solve.

Naturally. If it were easy to solve, it wouldn’t really count as a game.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Matt B
United States
Tampa
Florida
flag msg tools
Avatar
mbmbmbmbmb
heh
Nearly every real world worthwhile problem turns out to be NP-Hard. Assigning classes to classrooms is NP-Hard. Visiting places in an optimal order is NP-Hard (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.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
B. Perry
United States
Colorado Springs
Colorado
flag msg tools
Avatar
mbmbmbmbmb
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.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
George Kinney
United States
Bellefontaine
Ohio
flag msg tools
badge
Avatar
mbmbmbmbmb
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.


 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
B. Perry
United States
Colorado Springs
Colorado
flag msg tools
Avatar
mbmbmbmbmb
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.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
George Kinney
United States
Bellefontaine
Ohio
flag msg tools
badge
Avatar
mbmbmbmbmb
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 non-intersecting 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 non-intersecting 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 non-determinism 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 XML-RPC based distributed non-intersecting 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.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
B. Perry
United States
Colorado Springs
Colorado
flag msg tools
Avatar
mbmbmbmbmb
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.
 
 Thumb up
1.00
 tip
 Hide
  • [+] Dice rolls
1 , 2  Next »   | 
Front Page | Welcome | Contact | Privacy Policy | Terms of Service | Advertise | Support BGG | Feeds RSS
Geekdo, BoardGameGeek, the Geekdo logo, and the BoardGameGeek logo are trademarks of BoardGameGeek, LLC.