Author |
Topic: For C++ developers: MCT (Read 3321 times) |
|
doublep
Forum Guru
Badger author
Gender: 
Posts: 82
|
 |
For C++ developers: MCT
« on: Mar 21st, 2010, 2:31pm » |
 Quote  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
Gender:
Posts: 108
|
|
Re: For C++ developers: MCT
« Reply #1 on: Mar 22nd, 2010, 9:45am » |
Quote 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:
Posts: 1003
|
|
Re: For C++ developers: MCT
« Reply #2 on: Mar 27th, 2010, 7:16am » |
Quote 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 
|
| « Last Edit: Mar 27th, 2010, 7:16am by omar » |
IP Logged |
|
|
|
rbarreira
Forum Guru
Arimaa player #1621
Gender:
Posts: 605
|
|
Re: For C++ developers: MCT
« Reply #3 on: Apr 13th, 2010, 5:55am » |
Quote 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:
Posts: 82
|
|
Re: For C++ developers: MCT
« Reply #4 on: Apr 13th, 2010, 6:16am » |
Quote 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:
Posts: 605
|
|
Re: For C++ developers: MCT
« Reply #5 on: Apr 13th, 2010, 6:35am » |
Quote 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:
Posts: 86
|
|
Re: For C++ developers: MCT
« Reply #6 on: Jan 11th, 2015, 1:25pm » |
Quote 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 |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print