59 Posts
BoardGameGeek» Forums » Gaming Related » Trades
Subject: Math Trade Theory & Algorithms (Warning: Can Hurt Brain)
Your Tags:  Add tags 
Popular Tags:  View All]  [

Re: Math Trade Theory & Algorithms (Warning: Can Hurt BrainWithout having played with any sample outputs, that's the metric I would use  ignoring total number of trades and maximizing trade quality using the above formula (where number of trades is implicitly taken into account). Let me know if that produces reasonable results.
 [+] Dice rolls

Re: Math Trade Theory & Algorithms (Warning: Can Hurt BrainYes, that works well. The results were around 5070 trades. That's quite reasonable. That kind of scoring will be available in the second release of TradeResolver, I'll make it an option.
Edit: Now that I've actually squashed all the bugs in the qualitycounting algorithm and changed it to count in the untraded items, it looks like the results are pretty much the same whether you're looking for most trades or most quality. Which is interesting.
The quality tends to be around 0.5 on a list where most items are traded  is that enough for those who are looking for high quality trades, I don't know, but it does mean many people are getting their first want.
Of course, if a list is harder, the quality will be lower. On those lists, the maximize quality algorithm will work hard to increase the number of trades, because that's the easiest way to get better quality. With an easier list where you can get more trades, there's more alternatives to get a better quality.
So, what I'm saying here is that TradeResolver can produce satisfying results, if the quality you want is not "as many 1st want trades as possible, screw the rest" but "as good trades for everyone as possible".

 Last edited Sun Jun 4, 2006 7:07 am (Total Number of Edits: 1)
 Posted Sat Jun 3, 2006 8:01 pm
 [+] Dice rolls

Re: Math Trade Theory & Algorithms (Warning: Can Hurt BrainI know this is an old thread and thus I might not get any results, but could someone either fill me in on how to find and enumerate all of the cycles in a digraph (without worrying if they are disjoint) or link me to some page that can?
 [+] Dice rolls

Re:Math Trade Theory & Algorithms (Warning: Can Hurt Brain)Hi,
I was wondering about the same thing yesterday, when I read the thread the first time. I thought, first find all circles, and then try an approximation of the perfect cover which satisfies the disjoint condition.
But then I noticed the following:
A complete graph (not digraph) with n vertices has (n1)!/2 cycles (if I'm right). So you come to a cover problem (which is also NPcomplete) with exponential size of the original problem. This won't help anything.
To count all cycles, I see no other way, than perform a complete DFS (or BFS) on the graph and count every cycle one by one. Simply color every vertex you visited and increase the cycle counter every time you hit a colored vertex.
Christian
 [+] Dice rolls

I have done this, but with my own algorithm and therefor may not be the most efficient.
I preformed a DFS on the list and recorded all cycles regardless of where the fell in the tree.
My program was writting in VB6 so I made use of the TreeView Control. I picked a starting game and then added its first want to the tree with a node key of the edge (ie "1>2"). I continued this for each game recursively until I hit a "key already exsists" error. This meant that I reached a vertex & edge that is already on the tree. I moved up the tree to find the starting vertex and recorded that chain. I moved to the next game in the previous vertexes want list and repeated. I added a check to make sure that each game in the chain was unique.
The problems I ran into were
1) the sheer number of chains that are found is huge and storage of the data becomes a major issue.
2) once I had an approximation of all of the chains, putting them together was extremely slow even slower.
3) there was diminishing returns (in otherwords with 50 vertexes the program might run in 20 milliseconds, 100 vertexes the program might run in 3 minutes, 200 vertexes ... well it never finished because I ran out of memory)
 [+] Dice rolls

chrikru wrote:FWIW, BFS will find short chains quickly. DFS will find long chains quickly. Neither one has proven to be the better solution.
To count all cycles, I see no other way, than perform a complete DFS (or BFS) on the graph and count every cycle one by one. Simply color every vertex you visited and increase the cycle counter every time you hit a colored vertex.
 [+] Dice rolls

Re: Math Trade Theory & Algorithms (Warning: Can Hurt BrainPatticus wrote:but could someone either fill me in on how to find and enumerate all of the cycles in a digraphA simple Depth First Search (DFS) for every offer>want pair will work. You just need to cache each complete cycle somewhere as you come across it.
http://en.wikipedia.org/wiki/Depthfirst_search
 [+] Dice rolls
 Jeff MichaudUnited States
Longwood
FloridaCaptain Kirk, Captain Picard, Captain Sisko, Captain Janeway, Captain Archer 
Never mind BFS or DFS... Chris O. has solved the problem! See
Math trades are SOLVED!

 Last edited Sun May 29, 2016 1:41 pm (Total Number of Edits: 2)
 Posted Thu Aug 30, 2007 5:32 pm
 [+] Dice rolls