Welcome, Guest. Please Login or Register.
Mar 26th, 2019, 9:38am

Home Home Help Help Search Search Members Members Login Login Register Register
Arimaa Forum « For C++ developers: MCT »


   Arimaa Forum
   Arimaa
   Bot Development
(Moderator: supersamu)
   For C++ developers: MCT
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: For C++ developers: MCT  (Read 2563 times)
doublep
Forum Guru
*****



Badger author

   


Gender: male
Posts: 82
For C++ developers: MCT
« on: Mar 21st, 2010, 2:31pm »
Quote Quote Modify Modify

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.
 
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 ;)
IP Logged
rabbits
Forum Guru
*****




Arimaa player #1337

   
WWW

Gender: male
Posts: 103
Re: For C++ developers: MCT
« Reply #1 on: Mar 22nd, 2010, 9:45am »
Quote Quote Modify Modify

At first I thought this was a post about Monte Carlo Tree Search (MCTS).
 
Thanks for sharing.
IP Logged

omar
Forum Guru
*****



Arimaa player #2

   


Gender: male
Posts: 971
Re: For C++ developers: MCT
« Reply #2 on: Mar 27th, 2010, 7:16am »
Quote Quote Modify Modify

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 Smiley
« Last Edit: Mar 27th, 2010, 7:16am by omar » IP Logged
rbarreira
Forum Guru
*****



Arimaa player #1621

   


Gender: male
Posts: 605
Re: For C++ developers: MCT
« Reply #3 on: Apr 13th, 2010, 5:55am »
Quote Quote Modify Modify

Nice of you to contribute this, but is it really worth it to have a hash table for repetition detection?
 
The consensus 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).
« Last Edit: Apr 13th, 2010, 6:00am by rbarreira » IP Logged
doublep
Forum Guru
*****



Badger author

   


Gender: male
Posts: 82
Re: For C++ developers: MCT
« Reply #4 on: Apr 13th, 2010, 6:16am »
Quote Quote Modify Modify

Frankly, I never checked this.  Arimaa is not the same as chess in this regard, though, as captures are much more rare.
IP Logged
rbarreira
Forum Guru
*****



Arimaa player #1621

   


Gender: male
Posts: 605
Re: For C++ developers: MCT
« Reply #5 on: Apr 13th, 2010, 6:35am »
Quote Quote Modify Modify

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.
« Last Edit: Apr 13th, 2010, 6:38am by rbarreira » IP Logged
JimmSlimm
Forum Guru
*****




Arimaa player #6348

   


Gender: male
Posts: 86
Re: For C++ developers: MCT
« Reply #6 on: Jan 11th, 2015, 1:25pm »
Quote Quote Modify Modify

wow this helps the performance of my bot, almost 20% speedup! Thanks so much for sharing!
 
edit: 5 years later ^^
« Last Edit: Jan 11th, 2015, 1:26pm by JimmSlimm » IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Arimaa Forum » Powered by YaBB 1 Gold - SP 1.3.1!
YaBB © 2000-2003. All Rights Reserved.