Looping through variable number of arrays variable times?

[Richard Cornford]

Thanks for the feedback, and code on this one. Quite
honestly, it didn't occur to me that speed would be an
issue when I first approached this.

Thinking about what you are doing I suspect that speed isn't so much an
issue as a fatal problem.

Once I ran the code a few times, I realized that
more complex arrays were taking HOURS to run, and started
re-evaluating the code and my approach in general.

Given that you have up to 42 items with apparently 7 or so values per
item the possible total number of permutations gets so large that you
might be talking lifetimes to run rather than just hours.

Long-term, I'm working on an ajax-based Monopoly game.
At the moment, I'm focusing on some basic AI for the game.
I have relative values for each configuration of a property
in the game of Monopoly. (e.g., what is Boardwalk with 2
houses worth, long term, as opposed to Park Place with two
houses).

I gather that the board game 'Monopoly' originated in the Unites States.
Here in the UK the game uses locations in London, so we may talk about
Whitechapel and Mayfair in place of Boardwalk and Park Place, but at
least the concept of the game should be familiar to most Britons. I
gather that the game didn't catch on at all in Canada, and I don't know
about France, Denmark, the Netherlands or the rest of the world. That
may represent a problem when asking for help in an international
newsgroup as many potentially useful contributors will not automatically
be familiar with the concepts of the game.

In this project, I've created a form, where a player can
enter all the properties they own, and their current
state (e.g., mortgaged, unmortgaged, 3 houses, a hotel,
etc.), and how much cash the player has on hand.

Interesting. When I played Monopoly (and it has been quite a few years
since I last did) I recall the position of all of the other players
playing a big role in my decision making.

So if another player is 7 squares short of a property of yours on which
you can build, and he/she is cash poor so they will suffer
disproportional at having to pay a rent that exceeds their available
cash, then it may be worth risking excessive spending to build on that
property (and maybe adjacent properties) because having to roll two dice
gives then at least a one in six chance of taking that hit.

I also recall that one of the strategies I used when playing Monopoly
was to keep an accurate mental tally of how much money I, and all of the
other players, had at any time, but to keep my own cash in a loose heap
(with the bigger denominations nonchalantly concealed at the bottom of
the heap) so that none of the other players had an accurate idea of how
much money I had and they tended to assume that I had less cash than I
really did (unless they bothered to keep their own mental tally). As a
strategy it worked quite well, and eventually resulted in my siblings
resolving to never play Monopoly with me again (and they haven't).

I'm then running through all the various options
they have available to them (e.g., mortgage one property
to get cash, then build on another). I'm then calculating
the relative value of that complete configuration and
comparing them. So, yes, I'm actually running some calculations
based on each array. At the end, I tell the player their best
possible option. Pretty straightforward, but my approach had been
to run through all the permutations. It's taking far too long,
when a player owns more than one Monopoly, so I'm open to any
ideas you may have.

You are going to have to quickly prune out entire classes of possible
permutations, but you have not provided any details of your decision
making algorithm so it is impossible to judge what might represent a
class of permutations, let alone how they may quickly be eliminated form
consideration.

Let me see if I can follow your code samples, and see how it
performs in the context of my script.

Whatever happens it won't be good enough. Once the number of
permutations is in the billions it doesn't matter if the algorithm is 10
or 100 times faster the user is still not going to hang around waiting
for the result.

Richard.

 

[RobG]

<SNIP>

Richard,

Thanks for the feedback, and code on this one. Quite honestly, it didn't
occur to me that speed would be an issue when I first approached this. Once
I ran the code a few times, I realized that more complex arrays were taking
HOURS to run, and started re-evaluating the code and my approach in general.

The number of loops will be the product of how many of each element you
have (where A0 is one element, A1 another, etc.):

[["A",7],["B",7],["C",7],["D",7],["E",7],["F",7]]

Thats 7^6 loops of 6 pairs, or 117,649*6 pairs = 705,894 elements.

The general formula is n*x^n, where n is the number of elements (in the
above case 6 - A-F inclusive) and x is the number of possible values
each can have - in the above case 7. That assumes that they all have
the same number of possible values.

If you work out how many you have using 7 values for each element:

Terms values of each e.g.
1 7 [[a,7]]
2 98 [[a,7,[b,7]]
3 1,029 [[a,7,[b,7],[c,7]]]
4 9,604 etc.
5 84,035
6 705,894
7 5,764,801
8 46,118,408
9 363,182,463
10 2,824,752,490
11 21,750,594,173
12 166,095,446,412
13 1,259,557,135,291


You crack 1 billion element pairs at just 10 elements with 7
combinations each, and 1 trillion at 13 elements.

As Richard said, speed isn't really an issue, it's a roadblock. You
need quantum leaps in speed, not incremental gains.

Some comments:

I don't know how you did your testing, but according to me the recursive
function is easily the fastest.

Which browser you use makes a huge difference to the times but not the
rankings of each method. The following results were obtained using 5
elements (A,7 to e,7) in IE and Firefox:

Iterative Recursive Dynamic 'Cornford'
Firefox 3,844 609 1,079 1,046
IE 13,562 7,094 10,096 10,688


Why is Firefox up to 10 times faster than IE?


The only way you will finish the task in this lifetime (41*7^41 values
which is 1.827E+36 according to Excel) is to reduce the work required -
there are various strategies for that.

Recursion is often slower than other methods, it is liked because of
it's simplicity and ability to travel along any number of forks where
they aren't known beforehand. I suspect it works quickly here because
it doesn't recurse very deeply.

Long-term, I'm working on an ajax-based Monopoly game. At the moment, I'm
focusing on some basic AI for the game. I have relative values for each
configuration of a property in the game of Monopoly. (e.g., what is
Boardwalk with 2 houses worth, long term, as opposed to Park Place with two
houses). In this project, I've created a form, where a player can enter all
the properties they own, and their current state (e.g., mortgaged,
unmortgaged, 3 houses, a hotel, etc.), and how much cash the player has on
hand. I'm then running through all the various options they have available
to them (e.g., mortgage one property to get cash, then build on another).
I'm then calculating the relative value of that complete configuration and
comparing them. So, yes, I'm actually running some calculations based on
each array. At the end, I tell the player their best possible option.
Pretty straightforward, but my approach had been to run through all the
permutations. It's taking far too long, when a player owns more than one
Monopoly, so I'm open to any ideas you may have.

You may be better off to estimate the outcome of just a couple of the
most likely scenarios based on the probability that they might occur -
the vast majority of possibilities are irrelevant in the short term.
Attempting to estimate the likely outcome of every single possible
outcome is brute force approach.

You may be better to try an approach where decisions are based on a
particular strategy, current circumstance and player positions on the board.

[...]

 

[Thomas 'PointedEars' Lahn]

You need quantum leaps in speed, not incremental gains.

Quantum leaps are the smallest possible gains or losses (of energy)


SCNR

PointedEars

 

[RobG]

RobG wrote:




Quantum leaps are the smallest possible gains or losses (of energy)

Ah yes, but we aren't discussing quantum mechanics here (heaven forbid!).

It also means (strictly) a leap from one state to another with no
intermediary step, hence the smallest possible movement. Colloquially
it means to go from one state to another in a (usually large) jump.

 

[Thomas 'PointedEars' Lahn]

Ah yes, but we aren't discussing quantum mechanics here (heaven forbid!).

It also means (strictly) a leap from one state to another with no
intermediary step, hence the smallest possible movement. Colloquially
it means to go from one state to another in a (usually large) jump.

You don't say.


PointedEars, with working Irony Detector[tm]

 

[Mike P]

Thinking about what you are doing I suspect that speed isn't so much an
issue as a fatal problem.

The speed issue has certainly forced me to focus on building a more targeted
approach to solving for best configuration. I've already eliminated most of
the unfeasible scenarios. The first thing I did was to move the
isFeasible() function before the calculations, rather than after it. This
saved considerable time by avoiding unnecessary calculations. Next, before
even coming up with the exhaustive list of viable scenarios, I determine if
a property is a colored property within a monopoly. If it is, I'll look at
the 7 possible states (mortgaged through hotel). If it's not, there are
only 2 states (mortgaged/unmortgaged) to evaluate. Given the fact that
having more than one or two monopolies is quite rare in the game, those two
changes made this whole thing seem more reasonable. So if a player owns one
monopoly and six assorted other properties, we're looking at: 7^3*3*2^6*6 =
395,136 permutations. This does takes too long to calculate, but it's far
more realistic. Calculating with a single monopoly and a few assorted other
properties became completely viable.

Specifically, what am I doing? I have an array consisting of
probabily*impact for each property in each state. So the probability of
landing on Mayfair is 2.4832%, if that property has a hotel (rent = £2000),
that gives Mayfair with a Hotel the relative value of 49.664. Once I come
up with the various scenarios, I run each through an isFeasible() function,
which sees if the properties are "evenly built", and if the player could
afford to do it given the resources at their disposal (cash, houses/hotels
and unmortgaged properties). Once I've determined the viable scenarios, I
simply add the relative values for each property in the state they're in to
find a total relative value for the scenario. I completely ignore unowned
properties, but mortgaged properties do have an effect (e.g., owning a
morgaged railroad increases the rent on other unmortgaged railroads). Then,
I compare that value among the scenarios to find the highest value.

My next thought is to, somehow, approach this from the top down (i.e.,
hotels on all monopoly properties, and unmortgaged for all non-monopolies).
If the player can afford that, we're done. If not, we can ratchet things
down a notch (i.e., all unmortgaged, hotels on all monopoly properties
except one. That one with 4 houses) then I'll switch the 4-houses among
all the monopoly properties, see if that's feasible, if not, continue
ratcheting things down until I find one. That may be more realistic.

Or, possibly, I could work from both ends. Meaning, I could do some quick
checks on the high end (built to Hotels), working my way down. At the same
time looking at the low end (everything mortgaged) and working my way up.
Once I find the general vacinity of viability. Then exhaustively check
configurations within that smaller band (up or down). In concept, that
seems workable, but I'm still trying to figure out how I'd do it.

Still another approach might take the middle and work my way outward. Or
using random scenarios to find a "band of viability", within which, I could
perform an exhaustive search.

I did notice that the calculations seem to lean toward building
houses/hotels on less expensive properties. So, for example, if one had
£400, and owned Old Kent/Whitechapel (Indigo) and Park Lane/Mayfair
(Blue)... most players would assume they should build a single house on each
of the Blue properties. But, comparing based on long-term probable income,
the script now recommends mortgaging Park Lane, and building
Kent/Whitechapel to Hotels.



As you pointed out, a smart strategy should include knowledge of the other
players networth, current board position and probability*impact of landing
on your opponents squares (e.g., how much cash should you keep on-hand).
Players often don't know how much their opponents are worth. If they did,
as you clearly do, there's no sense in over building (e.g., if your
opponent's networth is £300 don't build beyond two houses on each of the
Blue). But I've not included that aspect in the calculation. I do have
probable next roll figures, which includes probability of landing on
go-to-gaol/go-to jail, selecting a chance/community chest card, landing in
gaol or rolling doubles. I'm not, initially, figuring that in the
calculations either, though having the opponents (estimated) net worth could
allow me to target bankruptcy goals thereby streamlining my search.



Regarding internationalization, that's a simple problem, easily remedied, by
offering a dropdown list to select game version (i.e., property names &
currency) ala http://kasoft.freeyellow.com/Central/PlayK/Monopoly/Database/.
FYI, there are Canadian and French versions, though I couldn't find one for
the Netherlands or Denmark.

 

[VK]

The speed issue has certainly forced me to focus on building a more targeted
approach to solving for best configuration. I've already eliminated mostof
the unfeasible scenarios. The first thing I did was to move the
isFeasible() function before the calculations, rather than after it. This
saved considerable time by avoiding unnecessary calculations. Next, before
even coming up with the exhaustive list of viable scenarios, I determine if
a property is a colored property within a monopoly. If it is, I'll look at
the 7 possible states (mortgaged through hotel). If it's not, there are
only 2 states (mortgaged/unmortgaged) to evaluate. Given the fact that
having more than one or two monopolies is quite rare in the game, those two
changes made this whole thing seem more reasonable. So if a player owns one
monopoly and six assorted other properties, we're looking at: 7^3*3*2^6*6=
395,136 permutations. This does takes too long to calculate, but it's far
more realistic. Calculating with a single monopoly and a few assorted other
properties became completely viable.

Specifically, what am I doing? I have an array consisting of
probabily*impact for each property in each state. So the probability of
landing on Mayfair is 2.4832%, if that property has a hotel (rent = £2000),
that gives Mayfair with a Hotel the relative value of 49.664. Once I come
up with the various scenarios, I run each through an isFeasible() function,
which sees if the properties are "evenly built", and if the player could
afford to do it given the resources at their disposal (cash, houses/hotels
and unmortgaged properties). Once I've determined the viable scenarios, I
simply add the relative values for each property in the state they're in to
find a total relative value for the scenario. I completely ignore unowned
properties, but mortgaged properties do have an effect (e.g., owning a
morgaged railroad increases the rent on other unmortgaged railroads). Then,
I compare that value among the scenarios to find the highest value.

My next thought is to, somehow, approach this from the top down (i.e.,
hotels on all monopoly properties, and unmortgaged for all non-monopolies).
If the player can afford that, we're done. If not, we can ratchet things
down a notch (i.e., all unmortgaged, hotels on all monopoly properties
except one. That one with 4 houses) then I'll switch the 4-houses among
all the monopoly properties, see if that's feasible, if not, continue
ratcheting things down until I find one. That may be more realistic.

Or, possibly, I could work from both ends. Meaning, I could do some quick
checks on the high end (built to Hotels), working my way down. At the same
time looking at the low end (everything mortgaged) and working my way up.
Once I find the general vacinity of viability. Then exhaustively check
configurations within that smaller band (up or down). In concept, that
seems workable, but I'm still trying to figure out how I'd do it.

Still another approach might take the middle and work my way outward. Or
using random scenarios to find a "band of viability", within which, I could
perform an exhaustive search.

I did notice that the calculations seem to lean toward building
houses/hotels on less expensive properties. So, for example, if one had
£400, and owned Old Kent/Whitechapel (Indigo) and Park Lane/Mayfair
(Blue)... most players would assume they should build a single house on each
of the Blue properties. But, comparing based on long-term probable income,
the script now recommends mortgaging Park Lane, and building
Kent/Whitechapel to Hotels.



As you pointed out, a smart strategy should include knowledge of the other
players networth, current board position and probability*impact of landing
on your opponents squares (e.g., how much cash should you keep on-hand).
Players often don't know how much their opponents are worth. If they did,
as you clearly do, there's no sense in over building (e.g., if your
opponent's networth is £300 don't build beyond two houses on each of the
Blue). But I've not included that aspect in the calculation. I do have
probable next roll figures, which includes probability of landing on
go-to-gaol/go-to jail, selecting a chance/community chest card, landing in
gaol or rolling doubles. I'm not, initially, figuring that in the
calculations either, though having the opponents (estimated) net worth could
allow me to target bankruptcy goals thereby streamlining my search.

Unfortunately I never played Monopoly game (a wasted youthhood, I know

So till now I'm not sure is this a "best algorithm" or a "best guess"
game. For example classic chesss is a best algorithm game: by finding
the best next option on each position will guarantee at least
even-to-even outcome. The poker game is a best guess game: despite
there are some best options, there is the Fatum and most importantly
human aspect involved. So you best strategy can be overrun in a minute
by cards or by your opponents unpredicted behavior.
"Best algorithm" games are really not AI domain, it's basically brute
force iteration through the branches (steps) in search of best
permutation (position). Lesser branches explored - quicklier result but
more possibility to miss really best option. If you ever played with
"mastership level"-enabled chess programs you know what I'm talking
about.

"Best guess" algorithms are really a key to AI. Pseudo-neuron systems
are working pretty much how biological thinking works. They don't
*calculate* the most possible option: they simply *know* it at each
moment based on the previous events and their "life experience".
Internally most of them are done on Shannon's algorithms. The simpliest
quantum of of such system could be Shannon's guessing machine. If
you're interested I can convert LISP into JavaScript for you, it's
really primitive (despite totally ingenious). Shannon's algorithm uses
genetic human unability to be totally random. If you play with
Shannon's gessing machine fair and long enough you will loose: it will
almost always know what number (== action) you're thinking of because
it will memorize your behavioral sequences. This approach requires
n-dimentional array with elements keeping the actions and program at
each moment has the n-long array key to the best action. The minus of
this AI is that it can get simply wrong, like any human being and "the
best action" will not be such. The plus is that it never repeats its
mistakes and more it plays - lesser mistakes it makes.

P.S. I'm not acting out, it just what I'm really involved and
interested in.

 

[Mike P]

You may be better to try an approach where decisions are based on a
particular strategy, current circumstance and player positions on the
board.

Rob,

Thanks again for these thoughts. It occurred to me that, perhaps, my
primary error is the order in which I'm doing things. I've already made one
change, which significantly reduced the amount of calculation being done.
But it's not enough. I just realized, which I think is the best approach to
this. With it, I think this whole thing is completely realistic. But
again, I'm not clear on how to code it.

Here's an example to illustrate the issue: My apologies to the non-US
members of the board, but I'm using the US board layout in the example. If
the player has $500 in cash, and three mortgaged properties: Boardwalk,
Park Place and Pacific Ave. Boardwalk and Park Place are the complete Blue
monopoly, and so the player is able to build on those properties. Pacific
is a single Green property, and therefore can not be built upon.

The initial approach was:

1) If the property is colored, evaluate for 7 states, if not (rrs & utils)
evaluate for only two (mortgaged and unmortaged).
2) check to see if each proposed scenario is feasible (i.e., the player can
afford it. That the properties are built evenly, if that rule is in effect
and buildings only exist on monopoly properties)
3) If it's a feasible scenario, tally up the relative value.
4) compare the relative value with the best one found so far. If it's
better, replace the best one found with the current, if it's the same or
worse discard it.

Made sense, at first, but there are a number of problems with it.

Using the initial approach, the script saw three colored properties. It
evaluated all colored properties in each of the 7 possible states
(mortgaged, unmortgaged, 1/2/3/4 houses or a Hotel). So, initially, the
script evaluated 7^3 = 343 scenarios. This was massive overkill, since
Pacific isn't part of a monopoly, it can NOT have houses or hotels. So I
did a quick check for monopoly membership before determining the scenarios.
So now, if it's a colored monopoly member, then evaluate 7 states, if not
(rr, util or non-monopoly colored) only evaluate for 2 states.

After that change, the script evaluated the sample scenario for only 98
scenarios (7*7*2). That significantly improved the script. But it's still
not good enough. If a player has two (3-property) monopolies, the script
will evalute for 117649 permutations. Add a third 3-property monopoly and
we're over 40 million permutations, which based on my benchmarks, would take
about 2 hours to evaluate (not factoring in script abort prompts).

In reality, the cash and property state can significantly limit the number
of feasible permutations. Given the sample scenario above. I'm evaluating
for 98 possibilities, but there are only 9 feasible (assuming the build even
rule is NOT enabled):

1) [B/Mortgaged] [P/Mortgaged] [R/Mortgaged] == 500 cash remaining
2) [B/Mortgaged] [P/Mortgaged] [R/Unmortgaged] == 390 cash remaining
3) [B/Mortgaged] [P/Unmortgaged] [R/Mortgaged] == 307 cash remaining
4) [B/Mortgaged] [P/Unmortgaged] [R/Unmortgaged] == 197 cash remaining
5) [B/Mortgaged] [P/1 House] [R/Mortgaged] == 107 cash remaining
6) [B/Unmortgaged] [P/Mortgaged] [R/Mortgaged] == 280 cash remaining
7) [B/Unmortgaged] [P/Mortgaged] [R/Unmortgaged] == 170 cash remaining
8) [B/Unmortgaged] [P/Unmortgaged] [R/Mortgaged] == 87 cash remaining
9) [B/1 House] [P/Mortgaged] [R/Mortgaged] == 80 cash remaining

None of the remaining 89 permutations are feasible, simply because the
player only has $500 in cash with which to play. They can't afford to add
another house or unmortgage something else. If I add in the "Build Even"
rule, we'd have to eliminate the two scenarios with a house on one blue, and
the other blue mortgaged.

One tricky thing about the calcuations is that there are penalties for
unmortgaging and selling upgrades. A player receives 50% of the purchase
price, when they mortgage a property. But, must pay a 10% premium to
unmortgage. So, for example, Boardwalk costs $400 to buy. When mortgaged,
the player receives $200. But, to unmortgage the property, the player must
pay $220. Similarly, a player must pay $50, $100, $150 or $200 to upgrade a
property (based on it's board location). But, if they sell that same
upgrade, they receive only 50% of the initial investment (If they buy a
house for $200, they'll only get $100 back if they sell it).

Given this, I think a more sane approach would be:

1) Begin with the initial properties.
2) change the state of each property one at a time.
3) check it for feasibility, if it's feasible evaluate and compare it. If
not, abandon that branch.

I do know, that once I've gone beyond viability, there's no sense going any
further down that "branch". Using the scenario above, if I evaluate:

[B/1 House][P/Unmortgaged][R/Mortgaged]

I'll find it feasible (assuming no build even rule), but just bearly so. I
know that given only $500, once I Unmortgage BW (-$220) and PP (-$193), I
have only $87 left, not enough to unmortgage Reading or build a house
anywhere else. I'm at a dead end, so look for another viable branch.

If the player only had $300, that means I can only evaluate:

One unmortgaged at a time. If I unmortgaged BW, I'd have $80 left, and
couldn't go any further. Unmortgage PP, I'd have $107 left, not enough to
go any further. Unmortgaging Pacific, gives me $124 left over... again,
can't unmortgage anything else.

It does get more complex with more cash. But honestly, if I can figure out
how to do this, I believe it's realistic to exhaustively evaluate all
feasible scenarios.

Any thoughts on how to accomplish this?

Thanks!

Mike