Hi !
I'm responding in this thread as this could be helpful for other people. So here is the MrNice's message :
Quote:
Hi Pitt,
I'm still looking how to move to iterative CFR...
I have applied your advices and I have increased speeds for iterative and recursive (thanks for that)... But my recursive has the same speed (more or less) then my iterative one...
I suppose there is another way to move to iterative... I'm doing iterative with 2 passes... Is there another way ?
But due to the fact that prob/reach need to be propagated top-down and ev down-top I don't really see how...
So if you have to advice that will be great
Regards,
MrNice
First I think you should try to look at performance over bigger games, because small depth games have not many recursive calls.
And to answer how you could do it another way, I do it in a single loop that walks the tree like a recursive method.
It took me a pretty long time to do it. I'll try to explain it simple :
let's say you have a recursive method that walks your tree :
Code:
Object recCall(Node n, Object arg1, ..., argN){
Object tmp1 = doFirstPass(n, arg1, ..., argN);
Object[] childrenResults = new Object[n.childrenSize];
for(int i = 0; i < n.childrenSize; i++)
childrenResults[depth][i] = recCall(n.children[i], tmp1, argK, ...);
return doSecondPass(n, childrenResults, tmp1, argH...);
}
First identify what data you need unmodified after each child recursive call (here :
i, tmp1, argK, argH)
Identify then what are the recursive values you will need for your second pass (here : childrenResults).
If you have arrays to store all this for each depth, you can have a while loop that walks the tree exactly the same way as recursive algorithm.
Constants :
Code:
int maxDepth;
int maxChildren;
Iteration variables :
Code:
int depth : to know at what depth you are
boolean forward : to indicate the direction of your algorithm.
Iteration arrays to store all what you need:
Code:
Object[][] childrenResults = new Object[maxDepth][maxChildren];
int[] lastChildVisited = new int[maxDepth]; (to store i)
...
and other arrays with maxDepth length to store args etc...
Your algorithm will have the general form :
Code:
Object result;
Node n = getRoot();
while(true){
if(forward){
// Do the first pass
// Store what you need to keep
lastChildVisited[depth] = 0;
node = n.children[0];
depth++;
continue;
}
childrenResults[depth][lastChildVisited[depth] ] = result;
if(lastChildVisited[depth] == node.childrenSize -1){
result = // Process children results;
node = n.parent;
depth--;
continue;
}
lastChildVisited[depth] ++;
node = n.children[ lastChildVisited[depth]];
depth++;
forward = true;
continue;
}
I didn't write anything about terminal nodes and stop conditions (on depth obviously) and it's poorly pseudo-coded, but I hope you understand the principle.
Keep in mind I'm not sure it's really better than your two passes algorithm for performance. But you asked for another way, hope you'll enjoy
Just for the algo programming skills, I think this systematical way to transform recursive algo to iterative one is a good knowledge .
And don't forget to test on bigger games so that you can really benchmark performance !
Cheers, tell me if something is unclear there...
Login
Register
FAQ
Search
). Anyway don't wait for it, I can't tell when this will happen 
