Poker-AI.org
http://poker-ai.org/phpbb/

Fast simulation (MCTS etc..)
http://poker-ai.org/phpbb/viewtopic.php?f=26&t=2683		 Page 1 of 1
Author:  ibot [ Thu Jan 16, 2014 2:14 am ]
Post subject:  Fast simulation (MCTS etc..)
I've been working on an agent that focuses on opponent modelling at the moment.
It's a relatively typical simulation bot, i.e. model an opponent then use MCTS or similar to guess the best action to take.

However, the problem i'm finding is that I can't simulate the game enough times when making a decision. I would ideally like to simulate the game a few thousand times (minimum) within a second or so. The actual simulation of gameplay is capable of this, but I need to make a new copy of the GameInfo object (Java) for each iteration.
Profiling the code shows that the majority of the time is taken up making deep copies of the objects..

I've tried several different deep copy solutions in order to speed this up, however it seems that it can only get so fast.
Right now I can simulate a few hundred games in a couple of seconds.

Does anyone have an experience with a similar issue? Is there an obvious workaround that i'm missing?

The only step I can think of is optimising the GameInfo object as much as possible. However, since it's used to create a lot of features and that would be a major headache, which could also only result in a small decrease in copy time, i'm hoping for something different :!:

Thanks for any help.
Author:  spears [ Thu Jan 16, 2014 9:38 am ]
Post subject:  Re: Fast simulation (MCTS etc..)
How about creating a tree of FutureGameInfo objects once? On each simulation, walk the tree, initializing the objects on the outward traversal and summing the evs on the return. Would you have enough memory?

Do you deal out cards in the simulation? If so, I think you should be able to get faster convergence by dealing out "strength buckets" in a way slightly reminiscent of CFRM.
Author:  OneDayItllWork [ Thu Jan 16, 2014 11:05 am ]
Post subject:  Re: Fast simulation (MCTS etc..)
I'm no Java expert, but I'd say work with structs, not objects. You want stuff on the stack, not the heap.
Author:  PolarBear [ Thu Jan 16, 2014 7:33 pm ]
Post subject:  Re: Fast simulation (MCTS etc..)
In Java the only things you can put on the stack are primitives (numerics, booleans) and references (pointers) to objects.
Author:  ibot [ Thu Jan 16, 2014 10:08 pm ]
Post subject:  Re: Fast simulation (MCTS etc..)
spears wrote:
How about creating a tree of FutureGameInfo objects once? On each simulation, walk the tree, initializing the objects on the outward traversal and summing the evs on the return. Would you have enough memory?

I'll give this a try. I've got 12gb of memory on my home computer and around 50gb using the university compute server. Working at home mostly so hopefully 12gb will do!

spears wrote:
Do you deal out cards in the simulation? If so, I think you should be able to get faster convergence by dealing out "strength buckets" in a way slightly reminiscent of CFRM.

Good idea, although I may look into it later though. The simulation and dealing of cards seems to run quite fast.

OneDayItllWork wrote:
I'm no Java expert, but I'd say work with structs, not objects. You want stuff on the stack, not the heap.
PolarBear wrote:
In Java the only things you can put on the stack are primitives (numerics, booleans) and references (pointers) to objects.


AFAIK java will do it's best with the objects when compiling, so not sure if i have much flexibility in regards to this.

I ran a few tests (last time I did so was quite a while ago) and found that I can get much better performance with kryo deep cloning.

Code:
20000 iterations -
Kryo serialisation: 2814.0ms
Cloner :22921.0ms
Improved java serialisation:13230.0ms
Kryo deep copy:2293.0ms


Not sure how I missed this when I last looked at the code. I'll let you know how it goes, hopefully i'll get a decent amount of iterations in now!
Author:  OneDayItllWork [ Fri Jan 17, 2014 8:36 am ]
Post subject:  Re: Fast simulation (MCTS etc..)
PolarBear wrote:
In Java the only things you can put on the stack are primitives (numerics, booleans) and references (pointers) to objects.

Surely there must be some way to define a collection of primitive types that can be thrown on the stack?
Author:  spears [ Fri Jan 17, 2014 9:13 am ]
Post subject:  Re: Fast simulation (MCTS etc..)
- omg serialization. little wonder it was slow.
- multi thread to use all cores/processors
Author:  PolarBear [ Fri Jan 17, 2014 12:01 pm ]
Post subject:  Re: Fast simulation (MCTS etc..)
OneDayItllWork wrote:
PolarBear wrote:
In Java the only things you can put on the stack are primitives (numerics, booleans) and references (pointers) to objects.

Surely there must be some way to define a collection of primitive types that can be thrown on the stack?


No sir :)
Author:  OneDayItllWork [ Fri Jan 17, 2014 12:43 pm ]
Post subject:  Re: Fast simulation (MCTS etc..)
PolarBear wrote:
OneDayItllWork wrote:
PolarBear wrote:
In Java the only things you can put on the stack are primitives (numerics, booleans) and references (pointers) to objects.

Surely there must be some way to define a collection of primitive types that can be thrown on the stack?


No sir :)

:roll:
Author:  HontoNiBaka [ Sun Jan 26, 2014 2:03 pm ]
Post subject:  Re: Fast simulation (MCTS etc..)
Do you need the copies, or do you actually just need one instance, that keeps track of the current gamestate?

If you only need the current gamestate, don't copy it every time, just refresh the important primitives in the object with setters.
Author:  ibot [ Sat Feb 08, 2014 1:01 am ]
Post subject:  Re: Fast simulation (MCTS etc..)
HontoNiBaka wrote:
Do you need the copies, or do you actually just need one instance, that keeps track of the current gamestate?

If you only need the current gamestate, don't copy it every time, just refresh the important primitives in the object with setters.

I had a look at this a while back, but I would need to reset almost every variable, resulting in more or less a clone. With the current speeds it doesn't seem worth the work.. If I was starting from scratch I'd probably keep this in mind though!

I also wonder if there is any advantage in MCTS versus simple monte carlo simulations for each possible action..
Author:  PolarBear [ Sat Feb 08, 2014 3:01 pm ]
Post subject:  Re: Fast simulation (MCTS etc..)
ibot wrote:
HontoNiBaka wrote:
I also wonder if there is any advantage in MCTS versus simple monte carlo simulations for each possible action..


The advantage is huge - the MCTS quickly abandons the branches which don't look promising.
Author:  ibot [ Sat Feb 08, 2014 3:47 pm ]
Post subject:  Re: Fast simulation (MCTS etc..)
I was thinking about this, and it could just be i'm misunderstood..
Is it not possible that some branches that at first appear unpromising are abandoned when in reality they are promising, however too few simulations have been run to be able to see. i.e. we have the best hand in current state, and if we run 1000 simulations this will be shown but after 50 simulations it appears that we've got a losing hand so the MCTS abandons the branch.

Is this possible..?
Author:  PolarBear [ Sat Feb 08, 2014 7:36 pm ]
Post subject:  Re: Fast simulation (MCTS etc..)
ibot wrote:
I was thinking about this, and it could just be i'm misunderstood..
Is it not possible that some branches that at first appear unpromising are abandoned when in reality they are promising, however too few simulations have been run to be able to see. i.e. we have the best hand in current state, and if we run 1000 simulations this will be shown but after 50 simulations it appears that we've got a losing hand so the MCTS abandons the branch.

Is this possible..?


It is possible, however unlikely.
Page 1 of 1 All times are UTC
Powered by phpBB® Forum Software © phpBB Group
http://www.phpbb.com/