Pente AI using Monte Carlo and UCT?
Posted:
Jul 23, 2014, 4:02 AM
It seems like as successful as Monte Carlo methods with UCT search have been in the last few years for Go programs ( http://en.wikipedia.org/wiki/Computer_Go#Monte-Carlo_methods )some graduate student might have come up with a decent improvement on Mark Mammel's pente AI using similar methods by now. After 7 plus hours of waiting (still waiting as I type this) for Mark's program to identify what it thinks is the best move in a position, I wouldn't mind hearing of something a bit quicker. Anyone aware of newer Pente AI developments?
Retired from TB Pente, but still playing live games & exploring variants like D, poof and boat
Re: Pente AI using Monte Carlo and UCT?
Posted:
Jul 23, 2014, 4:25 AM
A patent (originally assigned to Microsoft, published in 2008) for "an apparatus for learning to predict moves in games such as chess, Go and the like, from historical game records." http://www.google.com/patents/US20080004096
Retired from TB Pente, but still playing live games & exploring variants like D, poof and boat
Re: Pente AI using Monte Carlo and UCT?
Posted:
Jul 23, 2014, 1:14 PM
Hi Watsu
I have been writing an app to play Pente for a while now (for fun). It doesn't use Monte Carlo methods, just a fairly standard Alpha-Beta search. I think Mark's program still plays better than mine, though I'm working on it 7 hours seems like a LONG time for a single move. How many depth levels is it searching??? I presume this is a downloaded version not MM8 on the site.
Send me a message here if you would like more information about my AI, or would like to play against it (unrated).
Re: Pente AI using Monte Carlo and UCT?
Posted:
Jul 24, 2014, 1:20 AM
Hi Bruce, Thanks for letting me know about your app. I'll pass for now on the offer to play against it, since I barely have time to play against human opponents any more right now. I think I recall a position or two where it took around 30 hours to analyse them (probably on a faster computer than mine) but hopefully since this is a midgame position the computer will have made its move by the time I get home to check on it. Maximum depth (12) and VCT are the settings I use when I'm curious about a position enough to want to know what AI thinks is the best option.
Retired from TB Pente, but still playing live games & exploring variants like D, poof and boat
Posts:
2,233
Registered:
Mar 4, 2007
From:
San Francisco
Age:
45 Home page
Re: Pente AI using Monte Carlo and UCT?
Posted:
Jul 24, 2014, 2:41 AM
in this game it took AI_12 with VCT 2-3 days to discover the sure win move of P2's move#5. i ran it on a laptop that is quad duo. so 8 possessors. the search i think went into the billions. Richard played it first, but i knew about it a few weeks before he played it. I was trying to save it for tourney but he let the cat out of the bag prematurely. oh well.
~z
Scire hostis animum - Intelligere ludum - Nosce te ipsum - Prima moventur conciliat - Nolite errare
Re: Pente AI using Monte Carlo and UCT?
Posted:
Jul 24, 2014, 8:23 AM
Hi Watsu No problem Please excuse my ignorance, but what does VCT stand for? I'm guessing it means something like "try every move", because that is a LOT of processing.
Re: Pente AI using Monte Carlo and UCT?
Posted:
Jul 24, 2014, 8:24 AM
Hi Zoeyk
Just curious - does MM's AI actually use more than one processor? It would probably need to be explicitly programmed for it. My AI doesn't use multiple processors yet, and may never do so - it adds another whole dimension of pain for the programmer
Re: Pente AI using Monte Carlo and UCT?
Posted:
Jul 26, 2014, 4:23 AM
VCT -> Thanks.
On the processors topic, I'm not a windows user (much) but I think you can use the "Resource Monitor" built-in app. Watch a graph of the CPU performance while you've got the Pente search running. I suspect that you will find that it peaks at a level below 100%. E.g. if you've got 4 physical processors in your machine, it will hover around 25%.
You can probably list the processes that are running on your machine and sort them from highest to lowest usage. (on OS X I use the "Activity Monitor" app.) Note that processEs run on processORs - the operating system schedules their time on the CPUs. If there is a single, single-threaded processes for the pente app, you might see it running at close to 100%. If there are multiple entries for the pente app, it is probably multi-threaded or multi-processes. But I'd be surprised
Posts:
28
Registered:
Mar 22, 2008
From:
Cambridge, England
Age:
27
Re: Pente AI using Monte Carlo and UCT?
Posted:
Aug 3, 2014, 12:39 PM
I did some research on MCTS (Monte Carlo Tree Search) algorithms and achieved significant improvement of performance over UCT (Upper Confidence Bounds for Trees). My work can be found at github.
In a nutshell, MCTS performs well in games like go, and quite poorly in chess. The reason being, notion of threat. In chess (but it's also applicable to other games, like pente, c6, etc.) there are situations where only handful of moves can be classified as reasonable candidates, whereas all others lead to lost positions (usually very quick).
Why this is a problem? During the process of building a tree, when a node is visited an algorithm faces multi-armed bandit problem (also called exploration v exploitation trade-off). The algorithm needs to decide whether to improve statistics of already created child-nodes (exploitation) or go with an unseen option (exploration). UCT approaches this purely as a statistical dilemma. Moreover, random games played from a leaf don't resemble credible game whatsoever (although that's not really a problem when you run 100k simulations per move).
In my research I proved that you can apply heuristics to boost the performance of MCTS. To cut long story short, in the most successful configuration instead of using UCT formula I applied combination of:
Beam search - limited # of candidate plays for each node based on heuristic evaluation.
The Gibbs distribution - which determines the probability of selecting certain moves (child-node) given their heuristic evaluation (in other words based on heuristic evaluation how likely it is that certain move is going to be played). This concept was borrowed from quantum physics, and it was also explored in reinforcement learning. The formula is very simple, for more info please see my dissertation at github.
Enhanced simulations - instead of playing purely random games, each time random selection is made among n best candidate moves according to the heuristics.
At the end I outperformed pure UCT 100-0, so it kind of works. I should have probably published this in some journal...
I used the game PahTum as my test bed, however, I believe with some tweaks (and new heuristics) it can be successfully applied to Pente.
Nowadays I'm mainly interested in NLP and applying machine learning to big data, however, if you'd need some help I'm more than happy to offer my advice.
Re: Pente AI using Monte Carlo and UCT?
Posted:
Aug 4, 2014, 12:59 AM
Wow, thanks for sharing that information kolia! I hope we can find someone who is both interested in taking up Pente and/or C6 AI methods using your research findings and also has the programming skills which I lack. Ever since former Pente tournament winner Virag's work on solving renju http://www.sze.hu/~gtakacs/download/wagnervirag_2001.pdf I've been expecting someone to come up with a top level fast AI Pente program, but I guess there's not enough interest or money involved to make it worth someone's time currently. Giving Mark's program a top notch opening book would likely make it fairly unbeatable, but it would still be really slow.
Retired from TB Pente, but still playing live games & exploring variants like D, poof and boat
Re: Pente AI using Monte Carlo and UCT?
Posted:
Aug 4, 2014, 3:45 AM
Kolia, It doesn't affect the results of your research, but you may want to establish for sure the ancientness of the game Pah-Tum before you try to publish your dissertation somewhere, since the entry for it on wikipedia currently says the ancientness of the game is a hoax. It may be ideally suited for computer programming refinements precisely because its rules may have been first formulated @ http://dinsights.com/POTM/PAHTUM/details.php I don't know for sure either way, but it's something to check on before publishing, I think.
Retired from TB Pente, but still playing live games & exploring variants like D, poof and boat
Posts:
28
Registered:
Mar 22, 2008
From:
Cambridge, England
Age:
27
Re: Pente AI using Monte Carlo and UCT?
Posted:
Aug 9, 2014, 12:01 AM
Thanks for browsing through the paper and checking things up.
The article on Wiki is marked as a potential hoax due to lack of references (which is understandable). At the time of writing I also checked in Britanica (encyclopaedia), however, the game wasn't mentioned there.
In case of dispute or doubt I'd certainly remove any adjectives. Unfortunately, I don't have time to find the true origins of the game.
Once again, thanks a lot for having a look, and a diligent check.
