James Perry
United States
Spring Hill
Tennessee
flag msg tools
badge
Ex-Term-In-Ate
Avatar
mbmbmbmbmb
Ok, I just made a HUGE discovery in terms of speeding up the algorithm.

Remember the April Fools Math trade? TradeGenie found 61 trades in 98 tradeable games in about 8 hours.

My new discovery? 90 trades in 10 seconds

One of my major issues with speed before was the DFS method kept traversing the same sets of edges but from a different starting vertex. So I needed a way to efficiently short circuit that.

What I came up with was building a tree and then finding the cycles in the tree. Each edge can only be in the tree ONCE. Since I am coding in Visual Basic, I determined the quickest way to do this is to make use of VB's TreeView control. I pick a starting vertex and add a connected vertex, I use the notation "E:v1->v2" as a key for the new node (where v1 is the first vertex and v2 is the second, this is my edge (E)). When I attempt to add that key again, VB errors and I trap it. This lets me know that I've already added this edge. I do a quick run back up the tree to see if any of the direct parent nodes have the key I just tried to add, if they do, then I found a cycle. I add the cycle to a list. Using this technique, my program found 738 cycles in the data in 6.5 SECONDS.

Right now, my program only takes the largest cycle from each component and returns that answer, which would be a 2 game cycle in the size 3 component and an 88 game cycle in the size 95 component.

The next task is how to quickly combine all the cycles from a component into sets of disjointed cycles . . .


[edit]There was a game repeated in the 88 game cycle. shake

What happened is this: As I traversed back up the tree I didn't take into account the fact that I could pass over a game more than once. Take for example this data:

1 2 3
2 4 5 1
3 2 5
4 3 2
5 1 2

It could build a tree with a branch like this:
2-4-3-2-5-1-3-5-2-4

My algorithm would find this and report it as a cycle. I added a check to remove these cycles. When run again eliminating those cycles that repeat games, the number of cycles found drops to 62. I'll have to double check for cycles that could exsist but were not found, this will be difficult.[/edit]

[edit #2]After some tweaking and research, I have fixed the algorithm. It still does everything above except instead of looking for the same edge above, it looks for the first instance of the ending vertex in the parent of the node. Time is the same, 10 seconds, but the number of cycles found is 493 with no duplicates games in any of those cycles.[/edit #2]
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Mikko Saari
Finland
Tampere
flag msg tools
http://www.lautapeliopas.fi/ - the best Finnish board game resource!
badge
Avatar
mbmbmbmbmb
Re: Math Trade Theory & Algorithms (Warning: Can Hurt Brain
Here's a list I'd like to see examined: http://www.melankolia.net/gameblog/metalli2.txt

It's from my metal trade. It used to be 369 entries, but this version is semi-weeded by removing all unwanted entries (to make it fit in the TradeGenie 200 entry limit). It's really 90 entries, I think. While not bigger, it's different from Geek lists in that it has multiple entries from same people (thus the identical want lists), with one guy posting something like 70 entries. That might make a difference, or not.

TradeGenie got 66 trades pretty fast, my resolver can get to 72 swiftly. That shouldn't be the maximum. I'm curious what you can get (preferably soon; I'm not the kind of guy to wait a day for a computer program to compute) and what SCC (which I haven't implemented, though I clearly should) can do with it.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Tim Mitchell
Canada
Victoria
British Columbia
flag msg tools
Avatar
Re: Math Trade Theory & Algorithms (Warning: Can Hurt Brain
Gecko23 wrote:
very long want lists are real processing killers
Would it be useful to cap want lists at a medium-sized number? As you say, the very long lists are typically low-value items looking to luck out (and I say this as someone who got Talisman for Werewolf). If we had to cap our want list, people would have an incentive to focus on the more likely trades.

I suppose this could be done automatically. If a game is wanted by more than X people, then remove it from lists with over Y wants.

Regai wrote:
A game wanted by 50 people but has no wants is not a cycle. Similary if the game only wants one or two games that in turn want it only, means that it is only part of one or two cycles.

The best game to start with should be the game that is in the highest number of cycles. But how to determine that without find all of the cycles first?
Perhaps you could rely on a rule of thumb that will tend to pick a high-cycle game, such as "we'll start with the most-wanted game that has at least three wants." Make the rule public so some people teetering between two or three wants will have an incentive to list three.

Yogurt
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Mikko Saari
Finland
Tampere
flag msg tools
http://www.lautapeliopas.fi/ - the best Finnish board game resource!
badge
Avatar
mbmbmbmbmb
Re: Math Trade Theory & Algorithms (Warning: Can Hurt Brain
Yogurt wrote:
Would it be useful to cap want lists at a medium-sized number? As you say, the very long lists are typically low-value items looking to luck out (and I say this as someone who got Talisman for Werewolf).
It could also be a bunch of items from same person who's trying to get everything traded. The example list I posted has want lists of 20-30 items. Is 20-30 a medium-sized number or a lot, because that seems like a very reasonable want list to me.

Yogurt wrote:
I suppose this could be done automatically. If a game is wanted by more than X people, then remove it from lists with over Y wants.
Nice, but I wouldn't like to have my first preference removed just because someone else wants it and I want something else.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Tim Mitchell
Canada
Victoria
British Columbia
flag msg tools
Avatar
Re: Math Trade Theory & Algorithms (Warning: Can Hurt Brain
msaari wrote:
The example list I posted has want lists of 20-30 items. Is 20-30 a medium-sized number or a lot, because that seems like a very reasonable want list to me.
Your example list deals with CDs, which have a smaller range of values than board games. I think this might lead to more trades that seem acceptable and thus longer want lists.

The recent high demand board game trade list had 206 entries. Only 37 entrants (18 percent) had 20 or more wants. 21 entrants (10 percent) had 30+ wants.

I suspect some of these long lists could have been trimmed. The person offering Mystery Rummy (an $8 game) started his 30+ want list with Command and Colors, Wallenstein and Railroad Tycoon. (And why not, under the rules of the trade!) But such a trade would have been an unlikely coup, and a more focused list probably would have omitted these items.

msaari wrote:
Nice, but I wouldn't like to have my first preference removed just because someone else wants it and I want something else.
But the math trade algorithm would effectively do this for you anyway. If there are many ways to connect you to other traders (because you have other wants), you'll probably end up with the oddball or low value item on your list, not the high-demand item.

Yogurt

 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Mikko Saari
Finland
Tampere
flag msg tools
http://www.lautapeliopas.fi/ - the best Finnish board game resource!
badge
Avatar
mbmbmbmbmb
Re: Math Trade Theory & Algorithms (Warning: Can Hurt Brain
Yes, I think board game trades will have more unlikely trade attempts. With CDs, almost anything can be traded with almost anything. People aren't really that selective...

I implemented the SCC thing in my resolver (it was very easy, thanks to the elegant pseudocode). All items in my metal trade list form a single component, except the items I would've weeded out anyway. I'll have to check my previous CD trade, but I suspect the situation is pretty much the same. With the long want lists, I suppose that's bound to happen.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
James Perry
United States
Spring Hill
Tennessee
flag msg tools
badge
Ex-Term-In-Ate
Avatar
mbmbmbmbmb
I've only seen SCC create two components once, and that is in the April Fools Trade (one component was only three games in size, the other much larger). The thing about SCC is that it is uberfast and can eliminate games that otherwise would not have been weeded out.

msaari wrote:
Yes, I think board game trades will have more unlikely trade attempts. With CDs, almost anything can be traded with almost anything. People aren't really that selective...

I implemented the SCC thing in my resolver (it was very easy, thanks to the elegant pseudocode). All items in my metal trade list form a single component, except the items I would've weeded out anyway. I'll have to check my previous CD trade, but I suspect the situation is pretty much the same. With the long want lists, I suppose that's bound to happen.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
George Kinney
United States
Bellefontaine
Ohio
flag msg tools
badge
Avatar
mb
Re: Math Trade Theory & Algorithms (Warning: Can Hurt Brain
Regai wrote:
I've only seen SCC create two components once, and that is in the April Fools Trade (one component was only three games in size, the other much larger).
It doesn't tend to do much with the initial graph. Its just too dense, and more importantly, too massively connected. But once you've culled a cycle or two out of it, the SCC algo does start to break-up the remainder pretty effectively.

Once the SCC algo starts kicking in and breaking up the remaining graph, you can avoid a lot of fruitless searching by (obviously) skipping singleton groups, and also by simply comparing the length of your current working set plus the SCC group to see if its possible to exceed the last maximum found. If not, ditch it and go on to the next one.

There is probably some sweet spot where the overhead of doing the SCC search exceeds the time required to search a given sized set, but I haven't done enough profiling to have any good guesses at that yet.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
James Perry
United States
Spring Hill
Tennessee
flag msg tools
badge
Ex-Term-In-Ate
Avatar
mbmbmbmbmb
Gecko23 wrote:
It doesn't tend to do much with the initial graph. Its just too dense, and more importantly, too massively connected. But once you've culled a cycle or two out of it, the SCC algo does start to break-up the remainder pretty effectively.

Once the SCC algo starts kicking in and breaking up the remaining graph, you can avoid a lot of fruitless searching by (obviously) skipping singleton groups, and also by simply comparing the length of your current working set plus the SCC group to see if its possible to exceed the last maximum found. If not, ditch it and go on to the next one.

There is probably some sweet spot where the overhead of doing the SCC search exceeds the time required to search a given sized set, but I haven't done enough profiling to have any good guesses at that yet.
I agree whole heartedly with you on this. Running an SCC on the remaining games after each cycle significantly reduces the amount of games needed to search. It gives such a nice way of weeding out games that cannot trade in the remainder. I hadn't thought about using the size of the new components to determine if further searches are worth while, but that is an excellent idea and would be a quick way to short circuit a few thousand unnecessary searches....
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Mikko Saari
Finland
Tampere
flag msg tools
http://www.lautapeliopas.fi/ - the best Finnish board game resource!
badge
Avatar
mbmbmbmbmb
Re: Math Trade Theory & Algorithms (Warning: Can Hurt Brain
Yes! I now have SCC running in my guessing algorithm after each round, and whee, I've got a new record for my metal trade list: 76 trades (in about 10 minutes). That's a significant improvement over the 66 trades we had. The program is a lot slower (when counting runs per second), but I don't care, as it gets better results with fewer runs.

I also implemented quality control in my resolver. It's particularly important in the guessing algorithm, which doesn't care for preference order (the brute force doesn't either, but at least it iterates in order starting from the first preference).

I count the quality so that first preference gets n/n points (that is, 1), the last preference gets 1/n points and the rest of it falls between. The score is averaged to make it easier to compare. Looks like an average of 0.30 is pretty darn good.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Mikko Saari
Finland
Tampere
flag msg tools
http://www.lautapeliopas.fi/ - the best Finnish board game resource!
badge
Avatar
mbmbmbmbmb
Re: Math Trade Theory & Algorithms (Warning: Can Hurt Brain
Something came to my mind: I'm going to develop my guessing algorithm to use brute force to solve smaller components given by SCC (why go guessing at five-item components, when you can just solve them for good?). I've got a feeling I'll bump into same components more than once, so why solve them more often than you really need? I could save the optimal results in a table, where I could do lookup when I find a smaller component: is there a solution for this set? That should speed up the handling of components that repeat.

I haven't tried it yet, but I suppose it could speed up the process a bit. I'll report if and when I get results.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Flying Arrow
United States
Pennsylvania
flag msg tools
badge
Avatar
mbmbmbmbmb
Re: Math Trade Theory & Algorithms (Warning: Can Hurt Brain
I probably won't have time to get very involved in this, but I haven't seen anyone mention Hamilton circuits yet. Finding a "perfect trade" (where every game is traded) is equivalent to breaking the graph into strongly connected components and then finding a Hamiltonian circuit in each strongly connected component (if one exists). Finding Hamilton circuits isn't trivial, so my comment here doesn't really make the problem any easier, but if you're looking for existing algorithms to apply to this problem, it would be worthwhile to study Hamilton circuits.

http://en.wikipedia.org/wiki/Hamilton_circuit
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
James Perry
United States
Spring Hill
Tennessee
flag msg tools
badge
Ex-Term-In-Ate
Avatar
mbmbmbmbmb
FlyingArrow wrote:
I probably won't have time to get very involved in this, but I haven't seen anyone mention Hamilton circuits yet. Finding a "perfect trade" (where every game is traded) is equivalent to breaking the graph into strongly connected components and then finding a Hamiltonian circuit in each strongly connected component (if one exists). Finding Hamilton circuits isn't trivial, so my comment here doesn't really make the problem any easier, but if you're looking for existing algorithms to apply to this problem, it would be worthwhile to study Hamilton circuits.

http://en.wikipedia.org/wiki/Hamilton_circuit
May not hurt to try it, but the first SCC is most likely NOT a Hamilton Graph. Find a Hamilton cycle in the later components may bear fruit....

 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
George Kinney
United States
Bellefontaine
Ohio
flag msg tools
badge
Avatar
mb
Re: Math Trade Theory & Algorithms (Warning: Can Hurt Brain
I don't think searching for Hamiltonian circuits in particular would bring anything new to the table. The search for them is also an NP-hard problem, and any search that is complete must (by definition) uncover one if it exists.

Also, the SCC groupings change depending on which nodes are involved in whatever arbitrary cycles you've removed up that point, so there is no guarantee that a cycle that is a maximum in a given SCC group is a part of the maximum coverage group of the graph as a whole. It might be, given the breakdown at the moment, but you still have to take into account all the other possible groupings as well to be sure.

And then of course you have the possibility that the longest cycle doesn't necessarily provide as complete coverage as several smaller cycles might. so searching for longest cycles in general isn't all that useful IMO.

 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Randy Cox
United States
Clemson
South Carolina
flag msg tools
designer
1024x768 works just fine - Don't Wide the Site!
badge
Missing old BGG
Avatar
mbmbmbmbmb
Sorry to jump in so late and sorry if I touch upon very old ideas that are somehow obsolete now.

I haven't looked at math trades since the first week or so that they were proposed here. At that time, the algorithm was extremely simple: the most desired game (yes, integer weighting of the edges if you think in terms of graphs) always got first pick. It was a single-pass process from most-desired game (by the collective) to least-desired game. Of course, when a stumbling block was hit, a game was removed and you started over (key being that someone is eliminated, even if another path could have yielded them a game--since they are the stumbling block, they're out and start over). I can see the non-NP-complete issue.

However, I'm guessing I missed something. Did at some point someone say "it's better to get a lot of trades than to get the right trades?" It seems that the current philosophy is to make sure more people are involved with the final results--to hell with preference lists.

The reason I'm interested is because I just entered my first math trade in a long time and I'm horrified to think that I may have the most desired offering (not particularly likely, but work with me here) and then get my #8 pick or something like that. I meticulously ranked the 11 games I'm interested in and would hope that any algorithm would ensure that I get my #1 pick if my game is most desired by the masses. So, are preferences really not very important these days--with any old game on your "want" list being almost equal in the eyes of the algorithm?

On a different issue...I like the idea of limiting the number of games a person can put on their preference list. For what it's worth.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
James Perry
United States
Spring Hill
Tennessee
flag msg tools
badge
Ex-Term-In-Ate
Avatar
mbmbmbmbmb
Randy Cox wrote:
Sorry to jump in so late and sorry if I touch upon very old ideas that are somehow obsolete now.
That's okay, all comers are welcome. (though this is more of a topic for the FAQ thread: http://www.boardgamegeek.com/thread/93555)

Randy Cox wrote:
I haven't looked at math trades since the first week or so that they were proposed here. At that time, the algorithm was extremely simple: the most desired game (yes, integer weighting of the edges if you think in terms of graphs) always got first pick. It was a single-pass process from most-desired game (by the collective) to least-desired game. Of course, when a stumbling block was hit, a game was removed and you started over (key being that someone is eliminated, even if another path could have yielded them a game--since they are the stumbling block, they're out and start over). I can see the non-NP-complete issue.

However, I'm guessing I missed something. Did at some point someone say "it's better to get a lot of trades than to get the right trades?" It seems that the current philosophy is to make sure more people are involved with the final results--to hell with preference lists.
The problem is that giving the #1 game its #1 choice sometimes meant that 50 people couldn't trade, but if you gave the #1 it's #2 or #3 choice then those 50 people could be involved. So maximizing the number of trades means a more satisfying math trade for everyone, not just the person who put in the most desired game.

Preference lists are still very important. As was stated above, a math trade with 150 games will never (most likely) run to completion so the order the games are in the lists is the order that they are processed. TradeGenie starts with the most desired game, so it will likely still get its #1 or #2 pick.

TradeGenie admittedly does not weight trades, so it is possible that it will find a solution that has the same number of games as its current best that yeilds better quality trade, but then promptly ignores it. This is unlikely due to the fact that it uses the order the games are in the priority list, but not improbable.

The current effort is to find first an algorithm that is faster than TradeGenie and second to add in weighting to improve trade quality. Mikko has a solution that proposes to do this, it hasn't been field tested yet, but it soon will be.

Randy Cox wrote:
The reason I'm interested is because I just entered my first math trade in a long time and I'm horrified to think that I may have the most desired offering (not particularly likely, but work with me here) and then get my #8 pick or something like that. I meticulously ranked the 11 games I'm interested in and would hope that any algorithm would ensure that I get my #1 pick if my game is most desired by the masses. So, are preferences really not very important these days--with any old game on your "want" list being almost equal in the eyes of the algorithm?
This is the way TradeGenie works (to the best of my knowledge): If your game is the #1 want, it will try to make a chain that starts with your game and your #1 pick. It will move down the list until a chain is formed. It will then try to make chains out of the remaining games. It will continue doing this until all variations off of your #1 pick have been exhausted, it will then move to your #2 pick and repeat. It will only replace a solution if a solution with a higher number of trades is found.

Since in a large trade the likely hood of ever searching the #2 pick of the #1 game is small, the order of your picks is VERY important. In a small trade, the likely hood of running to completion is high and thus the order of picks diminishes somewhat. Remember that TradeGenie only replaces a solution if it finds a solution with MORE games.

Most people will get a game that is high in their want lists, a few people will get one that is deep in their lists. The main point is don't put games in your want list that you don't want.

Randy Cox wrote:
On a different issue...I like the idea of limiting the number of games a person can put on their preference list. For what it's worth.
I like the idea since it reduces the number of possible branches, but at the same time, it can limit the number of trades made. With weighting, the longer the list the less the games at the end matter (especially if an exponential factor is used).
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Randy Cox
United States
Clemson
South Carolina
flag msg tools
designer
1024x768 works just fine - Don't Wide the Site!
badge
Missing old BGG
Avatar
mbmbmbmbmb
Regai wrote:
The problem is that giving the #1 game its #1 choice sometimes meant that 50 people couldn't trade, but if you gave the #1 it's #2 or #3 choice then those 50 people could be involved. So maximizing the number of trades means a more satisfying math trade for everyone, not just the person who put in the most desired game.
Maybe for the other 50 people, that's true. For the top dog, it's not. I guess I'm in the camp of "better trades" not "more trades." If 90% of the people don't get anything (which is probably never the case), I'm ok with that, as long as those who did get something got their preferred pick. But I can see that that is just a philosophical issue.

Thanks for the answers.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Chris Okasaki
United States
White Plains
New York
flag msg tools
badge
Avatar
mbmbmbmbmb
Randy Cox wrote:
I guess I'm in the camp of "better trades" not "more trades." If 90% of the people don't get anything (which is probably never the case), I'm ok with that, as long as those who did get something got their preferred pick. But I can see that that is just a philosophical issue.
There is a philosophical issue here, but aside from that there's also a practical issue. You're assuming that if I list eight games, then I have a significant preference for the first game over the eighth game. But, often, I might list eight games that are all equally good to me, and the order in which I listed them was completely arbitrary. In that case, I would hate for the trade algorithm to bias itself toward giving me my first pick over my eighth pick if doing so increases the chances of not giving me any trades at all.

In the current format, there is no way to tell whether somebody really has a preference for the first game over the eighth or whether they are all equally good. I once ran a math trade where the format was "1 2 3 4; 5 6; 7 8 9" where 1 is my game and the semicolons indicate differences in preference level. So this example list says "2, 3, and 4 are equally good to me, but I prefer all of them over 5 and 6, which I prefer over 7, 8, and 9". I thought this format worked pretty well, but I think many of the other organizers for these things worry that it would lead to more user errors.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
George Kinney
United States
Bellefontaine
Ohio
flag msg tools
badge
Avatar
mb
Re: Math Trade Theory & Algorithms (Warning: Can Hurt Brain
Regai wrote:
Preference lists are still very important. As was stated above, a math trade with 150 games will never (most likely) run to completion so the order the games are in the lists is the order that they are processed. TradeGenie starts with the most desired game, so it will likely still get its #1 or #2 pick.
The thing to keep in mind is that in a DFS, the lower branches of the search tree (the nodes visited first, in this case the more wanted offers) change much, much more slowly than those further down. So the apparent preference for the popular offers is partially due to the run being terminated before it is done, and those offers still being in every result set up to that point.

If TradeGenie were allowed to run to completion, then it would simply return the maximum set, and the order of the want lists would be completely irrelevant.

Either way, the more popular offers are still more likely to make it into the result set for no reason other than there are far more in-paths to them than there are to other nodes.

And honestly, the more I think about it, the more I realize a 'preference' rating is just silly. If you wouldn't be perfectly happy with a trade, then why bother to put it in a want list to begin with?

On a side note, some more poking around has revealed a large group of folks that are investigating the same issues we are: software testers. Turns out the 'complete coverage of a digraph' (our basic goal) is being heavily pursued by folks designing source code coverage tools, since it's essentially their goal as well.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Mikko Saari
Finland
Tampere
flag msg tools
http://www.lautapeliopas.fi/ - the best Finnish board game resource!
badge
Avatar
mbmbmbmbmb
Re: Math Trade Theory & Algorithms (Warning: Can Hurt Brain
The way I see it is that you should only list games on your want list if you're going to be satisfied to get it. If a game on your want list is going to be a disappointment if you get it, don't list it.

That said, my program aims first for max trades, then for best quality. I can't see why that couldn't be reversed - it's trivial to make the program choose first by quality of trades and then by number of trades. I can see how someone could prefer that option (I don't - I think more trades means more happiness for everyone involved), so perhaps I'll add that to the next release. I should definitely try it and see how good results that can get...

The algorithm I use, by the way, doesn't care which is the most popular entry. It's all completely random. It only cares about the number of trades and the preference lists, in that order of importance.

Also one reason why I don't care about the most wanted item is that one trader can sometimes dictate that. My second metal trade had a trader with over 50 items, all with the same want lists. It's pretty much up to him which the most wanted item is, really. Doesn't make sense to care about that, really.

The way people trade in BGG isn't the only way - I wouldn't imagine having an one entry per trader restriction, for example, that wouldn't make a smidgeon of sense!
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Randy Cox
United States
Clemson
South Carolina
flag msg tools
designer
1024x768 works just fine - Don't Wide the Site!
badge
Missing old BGG
Avatar
mbmbmbmbmb
Drew1365 wrote:
I don't necessarily agree that just because a person has the list's most-desired game (which I take to mean, the game that appears on the most want lists) means that person should get first pick. It could be on everyone's list, but ranking low on everyone's list.
No, I wouldn't say the one that appears on the most lists is the best. I'd calculate a weighted average based on position in all those lists. Might have to smoothe it out a little (a la Bayesian padding here on BGG) so that a game at the #1 position on only 1 list doesn't look like the most desirable. Or I would keep it simple and just add up total points (n-1 for being at the top of someone's list, n-2 for 2nd position, etc).
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Mikko Saari
Finland
Tampere
flag msg tools
http://www.lautapeliopas.fi/ - the best Finnish board game resource!
badge
Avatar
mbmbmbmbmb
Re: Math Trade Theory & Algorithms (Warning: Can Hurt Brain
I did some testing. I made TradeResolver choose the best solution first by quality, then by quantity. On my metal list with 76 trades possible (at least), choosing by quantity produced the best score with four trades.

That would be a complete disaster for a result in my opinion, there would be many disappointed participants left without any trades at all. Thus, I took a lower limit: the program must trade at least 25% of the items on the list, choosing the best solution by quality after that.

That got 28 trades with a clearly better quality than usual (0.5, when usually 0.3 is pretty good; on my scale 1 would be everyone getting their first pick).

So, that's how I'll set it up in TradeResolver. You can choose if you want to prioritize quality or quantity, and you can also set a lower limit, as in "get at least this many trades". That can be zero, of course.

However, I'm not sure if math trades are really the tool to use to get quality trades. The suggestion to pair up people with matching wants is nice, but I'm not sure if I want to do that instead of making a longer chain of trades.

It just needs to be made clear that you can end up with anything on your want list, and it's likely that you won't get your first pick. If you realize that, the trade really is no-risk.

After all, I've seen people leave their most valuable items out of the trade once they've seen the list of stuff available, and some have set more selective lists on their better stuff. That's how it works, and I think it works better than anything else I've ever seen.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
James Perry
United States
Spring Hill
Tennessee
flag msg tools
badge
Ex-Term-In-Ate
Avatar
mbmbmbmbmb
I concur 100% with Mikko.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Flying Arrow
United States
Pennsylvania
flag msg tools
badge
Avatar
mbmbmbmbmb
Re: Math Trade Theory & Algorithms (Warning: Can Hurt Brain
Mikko, have you tried changing your formula for quality? You said quality was calculated by averaging the quality of trade for everyone who trades. What if you also factored in everyone who doesn't trade by saying they got a trade quality of zero. So if you have 6 people and 2 people trade, and they both get their first pick (out of four), then the quality would be (1 + 1 + 1 + 0 + 0 + 0)/6 = 1/3. On the other hand, if all six trade, but they all get their third pick (out of four), then the trade quality would be (1/2 + 1/2 + 1/2 + 1/2 + 1/2 + 1/2)/6 = 1/2.

I think using that formula would avoid the case where only 4 trades are made when 76 are possible.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Mikko Saari
Finland
Tampere
flag msg tools
http://www.lautapeliopas.fi/ - the best Finnish board game resource!
badge
Avatar
mbmbmbmbmb
Re: Math Trade Theory & Algorithms (Warning: Can Hurt Brain
That should drive the amount of trades to right direction. I'll have to try that and see what happens.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Prev «  1 , 2 , 3  Next »   |