Recommend
2 
 Thumb up
 Hide
61 Posts
Prev «  1 , 2 , 3  Next »   | 

BoardGameGeek» Forums » Gaming Related » Trades

Subject: TradeResolver version 8 out! rss

Your Tags: Add tags
Popular Tags: Math-Trade-Info [+] Math_Trade_Discussion [+] [View All]
Mikko Saari
Finland
Tampere
flag msg tools
http://www.lautapeliopas.fi/ - the best Finnish board game resource!
badge
Avatar
mbmbmbmbmb
Re: TradeResolver version 5 out!
Actually, right now I'm thinking of first comparing the first tiers, then overall result. I don't think comparing second or third or whatever tiers is that useful.

Of course, the basis of comparison can be amount of trades or quality, whichever the user wants.

So, a result is better if the first tier results are better; if they're equal, then just compare the total results to break the ties.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Michael Van Biesbrouck
Canada
St Catharines
Ontario
flag msg tools
designer
badge
Avatar
mbmbmbmbmb
Re: TradeResolver version 5 out!
msaari wrote:
Oh, yes. Should the program choose the first-tier solution that will yield most trades overall? Or should it just choose the best solution on the first tier? That's a good question, I think. Of course, this all with an assumption that we're talking about breaking ties among solutions with most trades.


If you just maximize the number of trades overall, then I think that the tiered system doesn't work. I was proposing that of several equally-good solutions to the first tier, we pick one that improves later results. Specifically, I said that given several equally-good choices for a tier, the one that most-helps the next tier be chosen.

Alternately, one could choose the one that helps all subsequent tiers (collectively) have the most trades. I think that an algorithm implementing this policy would be less efficient. It also seems to me that the first-tier choice might be chosen to screw the best-possible second-tier choice so that the third tier would maximize overall non-first-tier trades.

Based on Joe Huber's comments in using your program, an AI mode that switches between brute force and guessing as tiers are added might increase efficiency.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
James Perry
United States
Spring Hill
Tennessee
flag msg tools
badge
Ex-Term-In-Ate
Avatar
mbmbmbmbmb
Re: TradeResolver version 5 out!
I think what you are trying to get at is you have the following situtation:

Tier 1 = 10 trades; Tier 2 = 5 trades

but their may be a situtaion where

Tier 1 = 10 trades; Tier 2 = 6 trades

if the 10 trades in tier 1 were different.



The problem I see there, is that you don't know how each set of trades will affect the second or subsequent tiers until you run everything.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Michael Van Biesbrouck
Canada
St Catharines
Ontario
flag msg tools
designer
badge
Avatar
mbmbmbmbmb
Re: TradeResolver version 5 out!
Can you run your first tier to completion? If so, evaluate the second tier from each maximal solution to the first tier (you must have found all of them) in parallel.

If not, then you should be working on different tier levels simultaneously. Whenever a low-numbered tier is improved, all higher-numbered tier results are thrown away. Again, all maximal solutions at a given level should be used concurrently to search subsequent levels. As long as you cannot completely evaluate the trade, this algorithm should be more efficient at finding good trades than a non-parallel one.
 
 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: TradeResolver version 5 out!
I now have two versions of the multi-tiered trade system.

Version 1 finds the best solution for the first tier, then continues as long as there are tiers. It can use either brute force or guessing mode, but when the tiers get small enough, it switches to brute force.

Version 2 is based on the guessing algorithm. It creates a random set for the first tier, then when it can't create any more trade chains on the first tier, it adds the second tier wants and tries to make more chains and so on. It creates complete solutions, which can be compared to other complete solutions.

Version 2 seems more promising, because there it's possible to evaluate the result as a whole. It is possible to find a first-tier solution that maximizes the other tiers as well (whether that maximization is for trades or for quality).


Complete evaluation of the first tier is still a big task. I haven't tried to run the Denver trade through, it takes a while and I don't have patience to wait for hours - there are ways to get good results in seconds, so waiting for hours for the perfect solution feels like a suboptimal strategy.

So, working on the guessing method is probably the best way right now. After all, I can quite evaluating after the first tier if the first tier result isn't as good as the previous best first tier. Making a stab in the dark on the first tier takes very little time, so it's possible to go through many iterations pretty swiftly.

The code is in the SourceForge CVS if somebody wants to give it a whirl. I'll probably come up with a new release at some point, but when our baby is born (we're 11 days beyond the original release date, so it's any day now ), I won't have much time, I'm afraid.
 
 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: TradeResolver version 6 out!
I put out a new release. It has the new multi-tiered mode, where the program can maximize the results better. In case of two equally good first-tier results (be it quality or quantity), the one with better overall result is chosen.

Unless I get some bright ideas, I might start working on a graphical user interface. Feel free to chime in if you have any ideas on that. I'm thinking something simple: a way to set the options and launch the program. Is that something you would enjoy, or would prefer to keep the program as a command-line application? I'm keeping the command-line option in any case, even if I put in a GUI.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
James Perry
United States
Spring Hill
Tennessee
flag msg tools
badge
Ex-Term-In-Ate
Avatar
mbmbmbmbmb
Re: TradeResolver version 6 out!
GUI! GUI! GUI!

Actually, I've almost written an interface for it as it is.

Oh, would it be to much trouble to give us a way to change the results file name? If so, no big deal.
 
 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: TradeResolver version 6 out!
Regai wrote:
Oh, would it be to much trouble to give us a way to change the results file name? If so, no big deal.


Last two releases have this option, I think. Have I forgotten to document it? Just use the property resultFilename.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
James Perry
United States
Spring Hill
Tennessee
flag msg tools
badge
Ex-Term-In-Ate
Avatar
mbmbmbmbmb
Re: TradeResolver version 6 out!
Is there a limit to the number of games that can be in a want list? The no limit trade has some pretty lengthy want lists.
 
 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: TradeResolver version 6 out!
If you're running release 4.1 or up, there isn't. At least release 4 had a bug (or a feature) that would cap the want lists at 20 items, but that wasn't my intention. No limits, that's the spirit - I want to have as few artificial restrictions as 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: TradeResolver version 6 out!
Check out TradeResolver's SourceForge site for the new development version. It includes both of Joe Huber's excellent suggestions: logging and option to choose the random number generator seed. This would allow, for example, distributed trade resolving, as the generated results can be verified by someone else by using the same seed.

These new releases are called development releases, because they aren't complete. They do work and are all stable, but the documentation isn't up to date. Instead of waiting to come up with few more features and documentation, I've decided to share the small new features faster.

Here's the SourceForge file page: http://sourceforge.net/project/showfiles.php?group_id=169933

Any feedback on these new features is welcome. I like small feature requests like these a lot, so feel free to come up with all sorts of ideas. You can send them to me by e-mail, geekmail or using the SourceForge feature request tool.
 
 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: TradeResolver version 7 out!
The latest release of TradeResolver is out. Check the first message for features.
 
 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: TradeResolver version 7 out!
I was thinking: how about doing a distributed trade resolving architecture, using XML-RPC calls? TradeResolver would notify a central point of the results it finds and that central point (a simple PHP app) would show the best result found.

Insane, or a pretty good idea? I do think the distributed approach shows promise, particularly for larger trades, and the XML-RPC stuff is something I'm interested in learning... but would anyone actually use it? It would make distributing the trades easier and also add a spectator element, as people could check the web site to see the best results so far (though that's boring, usually).

Of course, it might be possible to distribute the brute force processing, too... how about that? I do have an idea of how to do it with XML-RPC.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
James Perry
United States
Spring Hill
Tennessee
flag msg tools
badge
Ex-Term-In-Ate
Avatar
mbmbmbmbmb
Re: TradeResolver version 7 out!
msaari wrote:
I was thinking: how about doing a distributed trade resolving architecture, using XML-RPC calls? TradeResolver would notify a central point of the results it finds and that central point (a simple PHP app) would show the best result found.

Insane, or a pretty good idea? I do think the distributed approach shows promise, particularly for larger trades, and the XML-RPC stuff is something I'm interested in learning... but would anyone actually use it? It would make distributing the trades easier and also add a spectator element, as people could check the web site to see the best results so far (though that's boring, usually).

Of course, it might be possible to distribute the brute force processing, too... how about that? I do have an idea of how to do it with XML-RPC.


To be frank, I was toying with a distributed math trade program using SOAP services. But if you are ready to try it, I say go for it. We'll need a big ass trade to test it with though! devil
 
 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: TradeResolver version 7 out!
I think I'll start small, though... perhaps something like HTTP POST-based system for collecting results, basically a web form. The XML-RPC stuff seems complicated, and looks like the PHP support is patchy for now.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Michael Van Biesbrouck
Canada
St Catharines
Ontario
flag msg tools
designer
badge
Avatar
mbmbmbmbmb
Re: TradeResolver version 7 out!
Just don't use Java RMI -- its design is incompatible with firewalls and NAT.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Michael Van Biesbrouck
Canada
St Catharines
Ontario
flag msg tools
designer
badge
Avatar
mbmbmbmbmb
Re: TradeResolver version 7 out!
msaari wrote:

The latest release adds logging and random seed selection (for testing and verification purposes). If the trade administrator uses the guessing algorithm and publishes the random number generator seed used, all participants can verify the results themselves. This also opens possibilities for parallel resolving.


Note that this only provides security if the seed is announced before the program is run. The moderator could run several instances in parallel and report only one of them. Iteration limits should also be published ahead of time so that intermediate results are not used.
 
 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: TradeResolver version 7 out!
mlvanbie wrote:
Note that this only provides security if the seed is announced before the program is run. The moderator could run several instances in parallel and report only one of them. Iteration limits should also be published ahead of time so that intermediate results are not used.


How come? If the program prints out the seed as it's run and produces a result X, I should be able to replicate that result by running the program with the same seed. The program should print out the exact same results in same order (the times will be different, of course).

I don't see why anything would need to be published ahead of time, but maybe there's something I don't get here.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
James Perry
United States
Spring Hill
Tennessee
flag msg tools
badge
Ex-Term-In-Ate
Avatar
mbmbmbmbmb
Re: TradeResolver version 7 out!
mlvanbie's concern is the use of parallell processing to generate a better result set for the trade moderator.

There are alot of things a trade moderator could do to influence the outcome of the trade programs. The seed number actually makes it harder for the trade moderator to influence the outcome of a trade even when published after the run since it makes the run verifiable.

Really, it comes down to trust. Do we trust the moderator to not tilt the outcome into his or her favor? For most of the people who have run math trades to this point, I'd say yes.

msaari wrote:
mlvanbie wrote:
Note that this only provides security if the seed is announced before the program is run. The moderator could run several instances in parallel and report only one of them. Iteration limits should also be published ahead of time so that intermediate results are not used.


How come? If the program prints out the seed as it's run and produces a result X, I should be able to replicate that result by running the program with the same seed. The program should print out the exact same results in same order (the times will be different, of course).

I don't see why anything would need to be published ahead of time, but maybe there's something I don't get here.
 
 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: TradeResolver version 7 out!
Well, if the moderator is aiming for the best set for himself and screw the rest, then there's little the program can do.

Though, the web form -driven parallel solving is a step to a direction where moderator's possibilities to mess things up are diminished. Anyone can process the data and the program keeps the best set. I'm hoping to try this with my latest metal trade (currently 380 discs on the list and more is coming, so I'm hoping to have over 100 tradeables).
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Michael Van Biesbrouck
Canada
St Catharines
Ontario
flag msg tools
designer
badge
Avatar
mbmbmbmbmb
Re: TradeResolver version 7 out!
My actual concern was that a false sense of security might be given. Given a starting seed and a number of iterations, the output is unique. If these are declared ahead of the trade, then everyone will get the same results. (As Regai clarified, if the seed is not declared ahead of time then one of several runs could be chosen.) If the number of iterations is not specified ahead of time, then the person running the algorithm may have an incentive to not return the best result found. (In a multi-resolver situation in which each participant is given a seed and number of iterations, participants might prefer to report that their computers crashed than return their results.)

I am quite happy with the idea of everyone in a math trade being able to generate solutions by methods of their own choosing and the best trade set of those turned in being chosen. There would be a level of gamesmanship in which people play chicken with the quality of their submissions. This will lead to a new era of personal trade resolvers that find the best trade set given preconditions.

 
 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: TradeResolver version 7 out!
mlvanbie wrote:
(As Regai clarified, if the seed is not declared ahead of time then one of several runs could be chosen.)


Yes, if the moderator wants to play dirty, that's nothing I can do about it.

Quote:
If the number of iterations is not specified ahead of time, then the person running the algorithm may have an incentive to not return the best result found.


But that doesn't matter! First of all, I'm taking the decision away - the program sends in the results, the user isn't asked. Besides, you gain nothing by not sending in the results found, as then you have absolutely no control over the results. You also can't compare whether the current best is better or worse for you than what you found.

Moderator will still be responsible for compiling the list and declaring the official results. I'm just looking for an easy way to add more computing cycles to the process without adding to the time it takes to get the results.

In my trade, once I get the want lists, I'll compile them and create a package of TradeResolver with the lists and all the settings correct and put that up for download. I'll say "please, if you can, take the package and run it for as long as possible until this deadline". That way we'll probably get a few more iterations than I could get by myself.

But perhaps you have a different scenario in your mind, because the I really can't see the problems you mention in this scenario. Could you enlighten me, please?
 
 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: TradeResolver version 7 out!
Here's a feature I'm adding to TradeResolver: identification of identical items. Given a list of item-to-trader mappings and a list of identical item sets, the program will discard all results where one trader gets two copies of the same item.

It's a big deal in my record trades. The current trade has a list of 809 items, with many duplicates. A way to maximize one's potential to trade one of the items while avoiding getting stuck with many copies is needed. Right now I'm solving it by checking the final lists for duplicating and distributing them on the want lists evenly (trader 1 wants copy A, trader 2 wants copy B), but that's a pain with 809 want lists to check...
 
 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: TradeResolver version 7 out!
The distributed resolving worked well! I put up a zip package with just the JAR and the datafiles and had people download it and run for as long as they could. I put it up late one night and set the deadline on next day. Few people were able to run the program overnight.

I set the initial best results, but the best result we ended up with was finally found by someone else. Too bad we only got 97 trades - we had 270 tradeables, but a large number of those had just 2 same wants, as one trader with lots of highly-desirable items just didn't find anything interesting on the list (which was, as I said, 809 items - could that be a record?).

I did some blitz coding and added the duplicate prevention system, which worked wonders (both in cutting the amount of possible big results and avoiding duplicates). It's an easy system - just list the duplicate items in a file and the traders in other and you're clear.

I'm going to put out release 8 with these features at some point.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Michael Van Biesbrouck
Canada
St Catharines
Ontario
flag msg tools
designer
badge
Avatar
mbmbmbmbmb
Re: TradeResolver version 7 out!
msaari wrote:
mlvanbie wrote:

If the number of iterations is not specified ahead of time, then the person running the algorithm may have an incentive to not return the best result found.


But that doesn't matter! First of all, I'm taking the decision away - the program sends in the results, the user isn't asked. Besides, you gain nothing by not sending in the results found, as then you have absolutely no control over the results. You also can't compare whether the current best is better or worse for you than what you found.


What you take away anyone can reintroduce. I could decide that any result that doesn't have me trading my games isn't worth sending in, or anything that doesn't have me receiving a particular game. You might think that the actions of one individual are unimportant, but I have access to more CPU power than you are likely to get from all of the other participants combined. I also have an excellent excuse for not returning results from all of my runs -- someone else running a job on these machines could cause one of my program instances to be suspended or killed. There are better results with my `help' than without it, but who benefits more than anyone else from the help?

I am not saying that there is anything wrong with getting help from self-interested sources, just that the trust model should be appropriately stated. Getting the trades that you want by presenting selected results is a game, and all of the traders are playing that game as competition. If you assume that everyone is gaming the system, then assumptions about finding best trade sets don't apply. It becomes a game of chicken in which people may have several results of varying quality (trade count, happiness, or whatever) with varying self-benefit. They choose the result that is best for themselves without being so bad that someone else will submit a better solution. How bad the submitted solutions are is a matter of groupthink and whether there exist solutions that are both globally happy and desired by single individuals.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Prev «  1 , 2 , 3  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.