Arimaa Forum - Print Page


    
      
        Arimaa Forum
        (http://arimaa.com/arimaa/forum/cgi/YaBB.cgi)
      

        Arimaa >> Bot Development >> For C++ developers: MCT
        
(Message started by: doublep on Mar 21^st, 2010, 2:31pm)

Title: For C++ developers: MCT
Post by doublep on Mar 21^st, 2010, 2:31pm

I know that part of the purpose of Arimaa bot challenge is to develop new ideas in articial intelligence field. I'm not good at theory, so I will hardly ever come up with a good idea/discovery. As a substitute, I developed something practical instead: Miscellaneous Container Templates (https://launchpad.net/libmct).

Those are very similar to STL TR1 (or Boost) unordered_(set|map) and to Google Sparsehash library. However, they are faster, don't allocate memory (often) and don't restrict values in any way.

Each board object in Badger keeps a set of previously encountered position hashes, used to implement third repetition rule. I noticed that unordered_set allocated a small amount of memory on each and every insertion, which slowed Badger down considerably, especially in multithreaded mode. Apparently, memory allocation requires synchronization (to avoid heap corruption), so malloc() calls, being bad for performance as they are, make multithreaded program slower still. I looked for an already written solution and found Google Sparsehash. However, this was not good enough, because it required to single out and never use two values, which I couldn't do. And even if I could (e.g. by sacrificing one bit out of Zobrist hashes), this just felt nasty and wrong.

So, I started writing MCT. The version contained in Badger 2010 is actually much more limited and simple. What is avaiable now was mostly written after WCC: I added exception safety guarantees, missing methods and many more tests. And even had to change internal representation, because the one I used initially didn't work with anything but integers with standard equality test. However, now MCT is very general-purpose and I tried to iron out all wrinkles and unwieldy additional requirements.

Hope this will be useful for C++ bot developers ;)

Title: Re: For C++ developers: MCT
Post by rabbits on Mar 22^nd, 2010, 9:45am

At first I thought this was a post about Monte Carlo Tree Search (MCTS).

Thanks for sharing.

Title: Re: For C++ developers: MCT
Post by omar on Mar 27^th, 2010, 7:16am

Wow, that's cool. Thanks for sharing this with us Paul. I'm sure others will find this useful.

If Arimaa helped to motivate this, I'm happy :-)

Title: Re: For C++ developers: MCT
Post by rbarreira on Apr 13^th, 2010, 5:55am

Nice of you to contribute this, but is it really worth it to have a hash table for repetition detection?

The consensus (http://www.talkchess.com/forum/viewtopic.php?t=19779&postdays=0&postorder=asc) at talkchess seems to be that a simple array is enough, as this array never gets very big (plus you can delete the whole history as soon as a capture occurs in the actual game, since captures are irreversible).

Title: Re: For C++ developers: MCT
Post by doublep on Apr 13^th, 2010, 6:16am

Frankly, I never checked this. Arimaa is not the same as chess in this regard, though, as captures are much more rare.

Title: Re: For C++ developers: MCT
Post by rbarreira on Apr 13^th, 2010, 6:35am

True, though the search depth in Arimaa is lower which at least mitigates the bigger post-capture history.

I guess I'll have to benchmark it when I can.

edit - another idea is to have a hash table for the actually played moves, and a simple list (array) for moves in the search tree.

Title: Re: For C++ developers: MCT
Post by JimmSlimm on Jan 11^th, 2015, 1:25pm

wow this helps the performance of my bot, almost 20% speedup! Thanks so much for sharing!

edit: 5 years later ^^