May 2015

[science_man_88]

Originally Posted by TheMawn

[506,255,1]->->[506,0,256]

This cannot legally happen. And this is clearly not a case where a player starts with zero.

You end up at [506,128,128] and you cannot get to [506,0,256] because the rules of the game state that if two players with equal amounts of money are matched up, then the game ends.

A player CANNOT end up with 0 dollars because they would have lost to someone with the same amount of money as them which ends the game. I don't know how else to say this.

okay okay sorry, clearly I've pissed in the sandbox. I get that 0 can't happen after game start I forgot at that time. the reason I got to it is because that's where the branch could end up if it went on. there's a lot of ratios of the numbers ruled out, because of how the stems work, if the same two are always picked they end in the equal fashion if one is a mersenne number times the other. so we can work out how far a stem can go for the main stem of the counter for two over 255 the first step is easy to work out and so is the second the next eight can happen because 506> 255*1 and the rest is simply shifting things.

[TheMawn]

Yeah, okay. That makes sense.

[science_man_88]

Originally Posted by TheMawn

Yeah, okay. That makes sense.

I have a script right now that has pari printing them ( I reduced to irreducible form since my known properties don't change if the same ratio is held) that can print all irreducible possibilities left in under 4 minutes ( wish their were less than 2 million left but I may have missed some checks and got them out of order to speed the code up). edit: part of my problem is using exclusive ORs but I don't know quite how to fix that as || is all I know I don't remember | ever working in pari, edit2:doh if using the switch case possibility might be worth trying

[TheMawn]

I have a collection of points [x,y,z] which I call legal starting configurations, where x, y and z are all <= 255. I have a numbering scheme which uses a single integer to denote each point.

Each point is currently tagged as ending the following turn (because it contain duplicates) OR is tagged with the identifier of each of the three configurations it can potentially lead to. My goal is to check each of those ID's to see if they reference an ID tagged with ending on turn 1. If any of them does, then that config ends on turn 2.

The hiccup I had is that some of the points which can be reached are not legal starting configs (like I discussed earlier) so I have a second set of points which I call reachable points. I have eliminated from them all legal starting configurations so that all legal points throughout the game are inside only one of the two sets.

However, with some thinking, I have determined that a large number of my "reachable points" are not in fact reachable. I am working on a list of criteria for points which cannot be reached within the mechanics of the game. For example:

The points x, y and z cannot all be odd, because one of the players had to double his money to get to where he is.

I'm starting to do more thinking and less crunching and I think this line of thinking is what science_man_88 has been doing. Depending on how much work it is to trim the points list and start over, it might help to expand the list of criteria. This of course is assuming people are interested in helping.

I think I'll go it alone for now because I finally feel like I have trimmed things down to a manageable amount (down to 7 million entries from 30-some, and this is before removing the all-odd cases).

[science_man_88]

Originally Posted by TheMawn

I have a collection of points [x,y,z] which I call legal starting configurations, where x, y and z are all <= 255. I have a numbering scheme which uses a single integer to denote each point.

Each point is currently tagged as ending the following turn (because it contain duplicates) OR is tagged with the identifier of each of the three configurations it can potentially lead to. My goal is to check each of those ID's to see if they reference an ID tagged with ending on turn 1. If any of them does, then that config ends on turn 2.

The hiccup I had is that some of the points which can be reached are not legal starting configs (like I discussed earlier) so I have a second set of points which I call reachable points. I have eliminated from them all legal starting configurations so that all legal points throughout the game are inside only one of the two sets.

However, with some thinking, I have determined that a large number of my "reachable points" are not in fact reachable. I am working on a list of criteria for points which cannot be reached within the mechanics of the game. For example:

The points x, y and z cannot all be odd, because one of the players had to double his money to get to where he is.

I'm starting to do more thinking and less crunching and I think this line of thinking is what science_man_88 has been doing. Depending on how much work it is to trim the points list and start over, it might help to expand the list of criteria. This of course is assuming people are interested in helping.

I think I'll go it alone for now because I finally feel like I have trimmed things down to a manageable amount (down to 7 million entries from 30-some, and this is before removing the all-odd cases).

I started off thinking of conditions as well I originally tried to get back 5 from the end but then I realized the mersenne number connection I've talked about already and some of my conditions didn't start to make sense because they'd gone off target. I then searched my list a little and started saying why isn't this one eliminated by this check and checked what the functions I was doing did description wise one of the functions I'm using leaves a hole I can fill partially with another check. when I started out on here with pari and looked into books I had previously the hard part is knowing the data if you know for example that one check can get rid of x% well that's 100-x% that go through the more gruesome second checks etc. if you could get checks to take off x% of the remaining it's like having negative compound interest towards the amount you start with, then it comes to a matter of time to do the checks which is what you are trying to optimize to get the programming to work faster. anyways I'm babbling like I always do and you probably know all of this already.

I did some arithmetic using counter variables on the whole problem and my first check took 473477 of 2796152 (using forpart ( short for for partitions basically for those who don't know) I gave it pre-conditions of both minimum and maximum length of 3 and values of 1-255) or 16.93 ..... % off that top that don't even see my second check for example.

[axn]

If I have done my programming correctly, there are 3 solutions that terminate in exactly 12 iterations (and none longer).
1_5,1_9,2_3
1_7,2_5,2_3
2_9,2_7,2__

[Batalov]

I think I see four solutions.

[axn]

Originally Posted by Batalov

I think I see four solutions.

I was hoping that I had covered everything ...

[Batalov]

Some ideas:
1. Note that in each game the amount of coins is constant.
2. All possible game states can be split in 757 game families (from 6 to 762 coins total in all hands)
3. Always keep the game state sorted: a<b<c
4. In each game family (s=a+b+c), nodes can be enumerated by the two poorest players' hands (a,b).
5. Catch and prune cycles, especially the most trivial: where one player is exactly twice richer than another.
6. Prune useless paths early
7. Memoize visited nodes

[axn]

I use a bruteforce approach. Pseudocode to follow.
1. Start with a length[763][763][763] 3D array. Set length[i][j][k] = 0 for invalid points (either 0 or sum > 763). set to 1 if at least two indexes are same. Everything else = infinity
2. For pass = 2, 3... Examing distinct i,j,k (i<j<k) where length[i][j][k] > pass. compute the three child nodes, and get the minimum of length of those three. set newlength = min child length +1. If that is an improvement ( newlength < currentlength), record it for all 6 combinations of i,j,k.
3. Exit when a particular pass doesn't improve any node.

[science_man_88]

Originally Posted by Batalov

Some ideas:
1. Note that in each game the amount of coins is constant.
2. All possible game states can be split in 757 game families (from 6 to 762 coins total in all hands)
3. Always keep the game state sorted: a<b<c
4. In each game family (s=a+b+c), nodes can be enumerated by the two poorest players' hands (a,b).
5. Catch and prune cycles, especially the most trivial: where one player is exactly twice richer than another.
6. Prune useless paths early
7. Memoize visited nodes

I would counter that one being twice another isn't the problem it's in cases like 7=[1,2,4] that a problem arises that's because although 2 and 4,and 1 and 2 can cycle fine that 1 and 4 would only cycle fine if 2 wasn't there. I would argue it's cases like [1,3,9] that can't exist because we get [2,2,9] if 1 and 3 are compared and [1,6,6] if 3 and 9 are compared. and the 1,9 combination wouldn't run into a problem without the 3 there because they end up cycling so [1,x,9] or [1,9,x] may work as it would make the path [1,9,x],[2,8,x],[4,6,x],[4,2,x] and from here the 4 and 2 cycle. it's only in combination with an inappropriate x that these two would fail. #6 is equivalent to go to irreducible form if you are dealing with ratio related constraints only.

I did mess up my checks, but here's a list of incompatible formulations among the cash of two people the count of eliminated assumes you haven't gone to irreducible form:
1:3 -> 84 such pairings eliminated
1:7-> 36 such pairings eliminated
1:15-> 17 such pairings eliminated
1:31-> 8 such pairings eliminated
1:63-> 4 such pairings eliminated
1:127-> 2 such pairings eliminated
1:255-> 1 such pairing eliminated
152 such pairings eliminated each that can be paired with 253 other numbers in theory which eliminates 38456 groupings before going to irreducible form ( 1771 from irreducible form). edit: of course by eliminating 1:2:4 we can disprove another 63 if not in irreducible form. edit2: sorry I read twice richer as twice as rich for some reason.