Looping through variable number of arrays variable times?
Mike P
Within that array is one data point, and the number of times it should loop
through.
So, for example, I might pass this to the function:
example[0] = new Array("A",2);
example[1] = new Array("Q",4);
function loopIt(example);
The function will then do the following:
function loopIt(example) {
for (x1 = 0; x1 < example[0][1]; x1++) {
for (x2 = 0; x2 < example[1][1]; x2++) {
calculateArray = new Array(example.length);
calculateArray[0] = new Array(example[0][0],x1);
calculateArray[1] = new Array(example[1][0],x2);
calculate(calculateArray);
}
}
}
But loopIt() doesn't know what example.length will be. Here I showed
example.length = 2. But if example.length = 41, this function wouldn't
work. How can I create a loop like this when example.length will vary?
Thanks!
Mike
VK
Mike P wrote:
> example[0] = new Array("A",2);
> example[1] = new Array("Q",4);
> function loopIt(example);
>
> The function will then do the following:
>
> function loopIt(example) {
> for (x1 = 0; x1 < example[0][1]; x1++) {
> for (x2 = 0; x2 < example[1][1]; x2++) {
> calculateArray = new Array(example.length);
> calculateArray[0] = new Array(example[0][0],x1);
> calculateArray[1] = new Array(example[1][0],x2);
> calculate(calculateArray);
> }
> }
> }
>
> But loopIt() doesn't know what example.length will be. Here I showed
> example.length = 2. But if example.length = 41, this function wouldn't
> work. How can I create a loop like this when example.length will vary?
That means that your array elements are going by pairs: example[i][1]
gives you the value for external loop, example[i+1][1] gives you the
value for internal value. So there is no way your array may contain an
odd amount of elements. Is it correct?
Mike P
"VK" <school...@yahoo.com> wrote in message
news:1130004710.3...@o13g2000cwo.googlegroups.com...
> That means that your array elements are going by pairs: example[i][1]
> gives you the value for external loop, example[i+1][1] gives you the
> value for internal value. So there is no way your array may contain an
> odd amount of elements. Is it correct?
With the code sample, the "example" array can contain 1 to 41 elements (even
or odd), but each array within it will be 2 long.
So:
example.length = 0 to 41 elements, and any integer inbetween (even or odd)
but example[x].length will always = 2 where
example[x][0] will always contain a string and
example[x][1] will contain an integer between 0 and 8
If I were to code this a long and ugly way, I could create a switch based on
example.length like this:
function loopIt(example) {
switch(example.length) {
case 1:
for (x1 = 0; x1 < example[0][1]; x1++) {
calculateArray = new Array(example.length);
calculateArray[0] = new Array(example[0][0],x1);
calculate(calculateArray);
}
}
break;
case 2:
for (x1 = 0; x1 < example[0][1]; x1++) {
for (x2 = 0; x2 < example[1][1]; x2++) {
calculateArray = new Array(example.length);
calculateArray[0] = new Array(example[0][0],x1);
calculateArray[1] = new Array(example[1][0],x2);
calculate(calculateArray);
}
}
}
break;
case 3:
for (x1 = 0; x1 < example[0][1]; x1++) {
for (x2 = 0; x2 < example[1][1]; x2++) {
for (x3 = 0; x3 < example[2][1]; x3++) {
calculateArray = new Array(example.length);
calculateArray[0] = new Array(example[0][0],x1);
calculateArray[1] = new Array(example[1][0],x2);
calculateArray[2] = new Array(example[2][0],x3);
calculate(calculateArray);
}
}
}
break;
}
}
So on, and so forth up to case 41, but that seems excessively inefficient.
I'm hoping there's a cleaner way to accomplish this.
do you follow?
I imagine there's some way to do this with a recursive array or dynamically
creating the function (ala, new Function)... I just don't really understand
how to go about it.
Thanks for your help on this!
Mike
VK
> creating the function (ala, new Function)... I just don't really understand
> how to go about it.
Well, using runtime generated function:
<html>
<head>
<title>Test</title>
<meta http-equiv="Content-Type" content="text/html;
charset=iso-8859-1">
<script type="text/javascript">
var example = new Array();
example[0] = new Array('Q',2);
example[1] = new Array('A',4);
example[2] = new Array('B',3);
function test() {
var fun = null;
var funOpen = '';
var funBody = '';
var funEnd = '';
var x = '';
var space = '';
var len = example.length;
for (i=0; i<len; i++) {
x = 'x'+(i+1);
funOpen+= space+'for ('+x+'=0; '+x+'<arr['+i+'][1]; '+x+'++) {\n';
funEnd += '}';
space+= ' ';
}
funBody+= space+'calculateArray = new Array(arr.length);\n';
for (i=0; i<len; i++) {
x = 'x'+(i+1);
funBody+= space+'calculateArray['+i+'] = new
Array(arr['+i+'][0],'+x+');\n';
}
funBody+= space+'calculate(calculateArray);\n';
fun = new Function('arr',funOpen.concat(funBody,funEnd));
fun(example);
}
function calculate(foo) {
alert(foo);
}
</script>
</head>
<body bgcolor="#FFFFFF" onload="test()">
</body>
</html>
I would not say that it's any less ugly than 41 case, but definitely
shorter. :-)
I guess any math prof would kill me for the above. The total amount of
loops is factorial of [i][1] values in your array. It's a strong hint
that the problem could be solved in some nice and profoundly academical
way using recursions. But it requires good matrix math knowledge more
than any JavaScript skills. The last of fine by me, the first is
floating miserably :-(
It works any way...
Mike P
I'm going to have to study that a bit to figure out how you did it.
Thanks again!
Mike
"VK" <school...@yahoo.com> wrote in message
news:1130021142.3...@g47g2000cwa.googlegroups.com...
RobG
>>I imagine there's some way to do this with a recursive array or dynamically
>>creating the function (ala, new Function)... I just don't really understand
>>how to go about it.
>
>
> Well, using runtime generated function:
[...]
>
> I would not say that it's any less ugly than 41 case, but definitely
> shorter. :-)
> I guess any math prof would kill me for the above. The total amount of
> loops is factorial of [i][1] values in your array. It's a strong hint
> that the problem could be solved in some nice and profoundly academical
> way using recursions. But it requires good matrix math knowledge more
> than any JavaScript skills. The last of fine by me, the first is
> floating miserably :-(
> It works any way...
>
There *had* to be a better way. This bugged me for hours, here's one
that may do the job better and could be considered 'better' - it
iterates through the first array of arrays and keeps splicing in
elements. I think the use of concat() and splice() may restrict it to
JavaScript 1.2 browsers and newer.
The function copyA() copies a 1D array, it shouldn't be used with 2D (or
more) arrays.
I can think of a faster way - go through the first set of loops for the
first loop (A[0]), then just copy those for every subsequent loop. But
I'll leave the implementation up to the OP.
The result is a 2D array:
<script type="text/javascript">
var A = [
['Q',2]
,['A',4]
,['B',2]
,['C',2]
];
// This does some setup
function doLoops(A)
{
var B=[];
for (var i=0, aLen=A.length; i<aLen; ++i){
addElements(A, B, i)
}
alert(B.join('\n'));
}
// The real work happens here
function addElements(A, B, i)
{
var c = A[i][0];
if (0 == i){ // Do first case
for (var j=0, aLen=A[i][1]; j<aLen; ++j){
B[j]=[c, j];
}
return;
} else { // All all others
var root // root array
var loops=A[i][1]; // Number of loops
for (var k=0, bLen=B.length; k<bLen; ++k){
root = copyA(B[k*loops]);
for (var m=0; m<loops; ++m){
if (0==m){
B[k*loops] = root.concat(c, m);
} else {
B.splice((k*loops + m),0,root.concat(c, m));
}
}
}
}
return;
}
// Return a copy of a 1 dimensional array (vector)
// If a 2d array is passed, references are returned
// not a proper copy.
function copyA(A)
{
var x = [];
var i = A.length;
while( i--){ x[i] = A[i]; }
return x;
}
</script>
--
Rob
RobG
[...]
> I can think of a faster way - go through the first set of loops for the
> first loop (A[0]), then just copy those for every subsequent loop. But
> I'll leave the implementation up to the OP.
This one is a bit faster and a lot tidier, it uses concat to copy the
array instead of copyA, everything is in one function.
<html><head<title>Loopy stuff</title>
<script type="text/javascript">
var A = [['Q',2],['A',4],['B',3]];
function doLoops(A)
{
var B=[];
var c=A[0][0];
var loops=A[0][1];
// Seed B
for (var j=0; j<loops; ++j){
B[j] = [c, j];
}
// Add extras
for (var i=1, aLen=A.length; i<aLen; ++i){
c = A[i][0];
loops = A[i][1];
for (var k=0, bLen=B.length; k<bLen; ++k){
var root = B[k*loops].concat(c);
for (var m=0; m<loops; ++m){
B.splice((k*loops + m),(!m),root.concat(m));
}
}
}
// For show
document.getElementById('zz').innerHTML =
'A: ' + A + '<br>' +
'Elements: ' + B.length + '<br>' + B.join('<br>');
return B;
}
</script>
</head><body onload="doLoops(A);">
<div id="zz"></div>
</body></html>
[...]
--
Rob
Julian Turner
Mike P wrote:
If I have understood the problem correctly, here is a further addition
to all the other contributions - a method using recursion:-
function LoopIt(e)
{
this.example=e;
this.exampleLength=e.length;
this.indexArray=[];
this.recurse(0);
}
LoopIt.prototype.recurse=function(n)
{
if (n<this.exampleLength)
{
var m=n+1;
for (var i=0; i<this.example[n][1]; i++)
{
this.indexArray[n]=i;
this.recurse(m);
}
return;
}
var a=[];
for (var i=0; i<this.exampleLength; i++)
{
a[i]=new Array(this.example[i][0],this.indexArray[i]);
alert(a[i].join(","));
}
calculate(a);
};
var example=[];
example[0] = new Array("A",2);
example[1] = new Array("Q",4);
var l=new LoopIt(example); // Constructs and calls
Julian
Mike P
news:JP%6f.1122$uQ6....@news.optus.net.au...
> This one is a bit faster and a lot tidier, it uses concat to copy the
> array instead of copyA, everything is in one function.
RobG, et al,
I'm glad to know this was an interesting intellectual challenge to even the
pros... I was completely stumped. I'll play around with the different
approaches (run time compile, join/concat, and recursive object function) to
figure out, not only which I'll actually use, but to learn how they work.
Thanks again, to all!
Mike
RobG
Hey, just for the record, here's a recursive version (sorry, couldn't
help myself, this just kept popping into my brain!).
var A = [['Q',2],['A',4],['B',3]];
function recA(X, i, B)
{
var i = i || 0;
if (!B) B = [[]];
var root = B[B.length-1].concat(X[i][0]);
var loops = X[i][1];
for (var j=0; j<loops; ++j){
B.splice((B.length-1+j), (!j), root.concat(j));
if ( X[i+1] ) recA(X, i+1, B);
}
return B;
}
alert( recA(A).join('\n') );
--
Rob
VK
Aha! Did I predict it? Leverrier - John Couch Adams case :-))
Mike P
> Hey, just for the record, here's a recursive version (sorry, couldn't
> help myself, this just kept popping into my brain!).
>
> var A = [['Q',2],['A',4],['B',3]];
>
> function recA(X, i, B)
> {
> var i = i || 0;
> if (!B) B = [[]];
> var root = B[B.length-1].concat(X[i][0]);
> var loops = X[i][1];
> for (var j=0; j<loops; ++j){
> B.splice((B.length-1+j), (!j), root.concat(j));
> if ( X[i+1] ) recA(X, i+1, B);
> }
> return B;
> }
>
> alert( recA(A).join('\n') );
It clearly works, though I'm still trying to wrap my mind around how it
works. Each iteration (e.g., currentArray = [[Q,0],[A,0],[B,0]]) needs to
be fed back through calculate( currentArray ). I'm not clear where, in your
(very impressive) recursive function, that would take place.
Thanks!
Mike
Mike P
> Hey, just for the record, here's a recursive version (sorry, couldn't
> help myself, this just kept popping into my brain!).
> Rob
Wait, I think I got it:
function test() {
var n = 0;
arrays = recA(A);
for ( n = 0; n < arrays.length; n++ ) { calculate( arrays[n] ) }
}
... I'm still stepping through a debug to try and figure it out :)
Mike
RobG
Here's the explanation (with a bit of cleaning up):
var A = [['Q',2],['A',4],['B',3]];
// A value is passed for X, but not for i or B
function recA(X, i, B)
{
/* If i is undefined, set its value to zero. This will
* only happen the first time recA() is called. When it calls
* itself, it passes values for i and B.
*/
var i = i || 0;
/* If B is undefined, make it an array with one element which is
* another empty array. The logic here is identical to that
* above, only the code is a bit different. The same code
* pattern could be use for both.
*/
if (!B) B = [[]];
// Both the above lines could be replaced with the following
// It's a bit cryptic and so not great for maintenance
!i && (B=[[]]) && (i=0);
/* Get the last row of the result array, B
* Make a copy of it and append the value at X[i][0]
* 'A' will be appended the first time through,
* 'B' the second, 'C' the third, etc.
* The array concat method copies and appends in one go
*/
var root = B[B.length-1].concat(X[i][0]);
// For this iteration, get the number of loops.
var loops = X[i][1];
// Start doing the loops
for (var j=0; j<loops; ++j){
/* The original line here was:
* B.splice((B.length-1+j), (!j), root.concat(j));
* a better version is:
*/
B.splice((B.length-!j), 1, root.concat(j));
/* It calls the splice method, telling it to start at
* B.length-1 when j=0 and B.length-0 when j>0.
* slice modifies in place, so B is modified directly.
* Its return value is whatever is deleted (if anything)
* We don't need it so it's ignored.
*
* The number of lines to replace is always 1, when
* j=0 the modified line (array) replaces the last, when
* j>0 the modified line is appended. Telling splice
* to replace lines after the end of the array
* effectively does nothing.
*
* concat is used again to get a copy of root with the
* value of j appended
*
* Lastly, if we aren't at the last element of X,
* call recA() again and pass i+1 to i and B to B.
* i is local to each instance of recA and so
* doesn't affect the value of i in other instances.
* All the B's are local too, but they all reference the
* same array, so just one array keeps getting modified.
*/
if ( X[i+1] ) recA(X, i+1, B);
}
/* The return value is ignored within the recursion
* since it's just a reference to an array that we
* already have a reference to.
* Whatever called recA() should to assign the returned
* reference to a variable or do something with it.
*/
return B;
}
--
Rob
Mike P
I've been playing around with the various options, trying to learn them, and
figure out which makes sense.
I got an error @ this.recurse(0) on Julian's recursive function, and wasn't
sure how to resolve it, so I skipped testing his. I was able to run a
benchmark on both RobG's recursive function and VK's run-time compile
version. Remember, worst case, I'll be running this using example.length =
41. The numbers get pretty scary with larger arrays. I used example.length
= 6, for the test. Specifically:
example = [["A",7],["B",7],["C",7],["D",7],["E",7],["F",7]]
While I'm running a pretty slow machine, I came up with the following
runtimes:
RobG's Recursive Function = 102958 ms
VK's runtime compile = 9113 ms
...just thought you might be interested.
Thanks!
Mike
VK
Do you know *what* killed the cat?
You've almost spelled a dark secret of JavaScript related with its
interpreted (vs. compiled) nature; but your guardian angel stopped you
on time.
Search this newsgroup using keyword "evil". Look the posters' Names.
You were aware...
;-)
Richard Cornford
<snip>
> example = [["A",7],["B",7],["C",7],["D",7],["E",7],["F",7]]
>
> While I'm running a pretty slow machine, I came up with
>the following runtimes:
>
> RobG's Recursive Function = 102958 ms
> VK's runtime compile = 9113 ms
>
> ...just thought you might be interested.
If you were interested in speed you probably should have said so form
the outset, and provided considerably more detail as to the real problem
instead of just this one minor part of it.
Recursion is inevitably slow, it lends itself to working with more
complex structures than yours, such as trees. But there is no need for
the 'meta scripting' (building new scripts as strings and having them
dynamically interpreted) approach here either.
Unfortunately, in not providing details of the wider problem, and
particularly your - calculate - function, it is not possible to gauge
whether all the Array creation inherent in your original code, and the
suggested alternatives, is necessary. If the Arrays are just a way of
passing parameters to the - calculate - function, and are effectively
thrown away after the function call then there is no need to create a
new array for each call at all. The result will be considerably quicker
than all of the alternatives proposed so far:-
function loopIt(ar){
var len, c, o = [];
if((len = ar.length)){
c = --len;
do{
o[c] = [ar[c][0], 0];
}while(c--);
do{
c = len;
while((++o[c][1]) == ar[c][1]){
o[c][1] = 0;
if(--c == -1){
break;
}
}
calculate(o);
}while(c != -1);
}
}
But if the - calculate - function does preserve the Arrays in some way,
so it does need to be passes a distinct array with each call, then:-
function loopIt(ar){
var len, t, c, a1 = [];
var a3, a2 = [];
if((len = ar.length)){
c = --len;
do{
a1[c] = 0;
a2[c] = ar[c][0];
}while(c--);
do{
t = len;
while((++a1[t]) == ar[t][1]){
a1[t] = 0;
if(--t == -1){
break;
}
}
a3 = [];
c = len;
do{
a3[c] = [a2[c], a1[c]];
}while(c--);
calculate(a3);
}while(t != -1);
}
}
- gets the job done with direct code, and mostly quicker than the 'meta
scripting' approach.
In any case, the desire to pass such a complex structure to a function
suggests that the whole problem would be amenable to better (certainly
faster) solutions.
Richard.
Mike P
news:dk3lem$k09$1$8300...@news.demon.co.uk...
> If you were interested in speed you probably should have said so form
> the outset, and provided considerably more detail as to the real problem
> instead of just this one minor part of it.
<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.
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.
Let me see if I can follow your code samples, and see how it performs in the
context of my script.
Thanks again!
Mike
Julian Turner
Mike P wrote:
> I got an error @ this.recurse(0) on Julian's recursive function, and wasn't
> sure how to resolve it, so I skipped testing his.
Apologies for that. No doubt Richard's solutions are more effective,
and recursion is not the best in terms of performance, but if you were
still interested, here is a slightly adjusted version of my function to
try.
You could no doubt try speeding it up with use of "while" and "do
while" loops, and reverse loops (i.e. length-1 --> 0)
function LoopIt(e)
{
var L=e.length;
var a=[];
Recurse(0);
function Recurse(n)
{
if (n<L)
{
var m=n+1;
for (var i=0; i<e[n][1]; i++)
{
a[n]=i;
Recurse(m);
}
return;
}
var c=[];
for (var i=0; i<L; i++)
{
c[i]=new Array(e[i][0],a[i]);
//alert(c[i].join(","));
}
calculate(c);
}
}
var example=[];
example[0] = new Array("A",2);
example[1] = new Array("Q",4);
LoopIt(example);
Julian
Julian Turner
Julian Turner wrote:
> No doubt Richard's solutions are more effective,
> and recursion is not the best in terms of performance
Here is another non-recursive version:-
function LoopIt(e)
{
var L=e.length;
var c=[];
var t;
var i=L;
while(i--)
{
c[i]=[e[i][0],0,e[i][1]];
}
Outer:
while(1)
{
t=c[L-1];
while(t[1]<t[2])
{
//alert(c);
//calculate(c);
t[1]++;
}
t[1]=0;
var i=L-1;
while(i--)
{
t=c[i];
if (t[1]==t[2]-1)
{
t[1]=0;
}
else
{
t[1]++;
continue Outer;
}
}
break;
}
}
Julian
Richard Cornford
> Richard Cornford wrote:
>> If you were interested in speed you probably should have
>> said so form the outset, and provided considerably more
>> detail as to the real problem instead of just this one
>> minor part of it.
<SNIP>
>
> 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
> "Richard Cornford" <Ric...@litotes.demon.co.uk> wrote in message
> news:dk3lem$k09$1$8300...@news.demon.co.uk...
>
>> If you were interested in speed you probably should have said so form
>> the outset, and provided considerably more detail as to the real problem
>> instead of just this one minor part of it.
> <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.
[...]
--
Rob
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:
>
>
>>You need quantum leaps in speed, not incremental gains.
>
>
> 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.
--
Rob
Thomas 'PointedEars' Lahn
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
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