5 ms·

Ask HN: How does Weiqi AI work?

• k8tte 11y ago
  https://en.wikipedia.org/wiki/Computer_Go https://en.wikipedia.org/wiki/Computer_Go
• Wildgoose 11y ago
  Hi, I'm a Go player (only around 9 kyu though). The programs don't make "intuitive" moves, but nor do they exactly perform brute search - the search tree is far too wide. They actually use a mixture of techniques. For example, in the beginning they may select moves from fuseki databases of accepted good play, and have some knowledge of joseki for plays in the corner. During the very end game they may be able to brute force search and make sensible decisions about the order of play - however there is also a book about using simulated annealing with neural networks to decide the order moves should be played. <a href="http://www.amazon.co.uk/Mathematical-Go-Chilling-Gets-Point/dp/1568810326">Mathematical http://www.amazon.co.uk/Mathematical-Go-Chilling-Gets-Point/... Go: Chilling Gets the Last Point</a>. There have been attempts to code "rules of thumb" into the Go algorithms, such as knowledge of bamboo joints, table shapes, etc., but the recent improvements have largely been down to techniques such as evaluating the position after allowing two consecutive moves and even simply trying various random plays rather than an exhaustive breadth-first search. There certainly used to be a mailing list for people interested in the development of Go-playing programs. I can't remember the address but if you broaden your search terms to include "Go, wei-chi, weiqi, baduk" you should be able to find it.
  • gjm11 11y ago
    > using simulated annealing with neural networks Are you sure about that, or are you basing it on the word "chilling" in the title? My understanding is that Berlekamp's book is all about applying combinatorial game theory to go, and the "chilling" in question has very little to do with the "temperature-decrease" schedule in simulated annealing. "Chilling" in combinatorial game theory means, in effect, making players pay a penalty for each move they make. The simplest games to analyse are ones in which it's always a disadvantage to have to move; these are equivalent in a certain sense to numbers; the "chilling" operation tends to turn games into simpler games. See e.g. http://senseis.xmp.net/?Chilling http://senseis.xmp.net/?Chilling for a little more information. The only connection between this and what happens in simulated annealing is that temperature happens to be a good metaphor for both. In combinatorial games, that's because the "value" of a position changes less wildly with each move in a cooled/chilled game. In simulated annealing, it's because the configuration you're looking at changes less wildly on each successful update as the temperature decreases.
    • CaiGengYang 11y ago
      Sounds very interesting ! God knows how Go AI will evolve in the future ! Perhaps the field of Go AI will produce a fully conscious machine in the future , one that can think and strategise like a human being , contributing to the technological singularity predicted by Ray Kurzweil ...
    • Wildgoose 11y ago
      Sorry, yes, you are correct - my memory was playing tricks.
      • CaiGengYang 11y ago
        Playing tricks about what ?
• slashcom 11y ago
  I can't speak as to how to individual particular programs work, but at least as of a year ago, most of the good AIs used something called Monte Carlo Upper Confidence Trees. They're, unfortunately, not based on intuition. Just statistics. Basically, the machine plays many, many random games. The more winning games which play a particular stone, the more valuable that particular position is. Then the position with the highest value is chosen. This alleviates the need of brute force search (which is just too large for Go). As far as I understand, most of the more successful AIs use UCT for the general game, but then fall back to heuristics and brute search for small, local conflicts (like if forced some stones to be played until death) and counting stones. Sensei's library has some nice high level information written about the topic: http://senseis.xmp.net/?UCT http://senseis.xmp.net/?UCT More recently, DeepMind (and someone else independently at Edinburgh, I believe) has published a couple papers about training a neural network to play by teaching it to predict the next move of pros given the board state. These use modern computer vision techniques and data. Last paper I saw, this did much better than GNU Go (which doesn't use UCT, and is very weak), but still not as good as monte carlo based methods. There has yet to be a combination of the Neural Network and Monte Carlo methods, but they're quite complimentary. I believe we'll see that combination in the next year or so, and this will nearly close the AI-human gap. Edit: Monte Carlo. :P Hooray for autocorrect.
  • apetresc 11y ago
    Not to be pedantic, but it's "Monte Carlo", not "Money Carlo". In case OP wanted to search the phrase.
  • eutectic 11y ago
    The idea that top-level programs use UCT is just folklore at this point. I know that at least MoGo uses a greedy version of Monte-Carlo Tree Search enhanced with RAVE (Rapid Action Value Estimation), a way to share information between branches of the search tree, a pattern database which runs an evaluation function on small patches of the board, and a set of simple heuristics. The consensus is that UCT is bad because it tries to minimize cumulative regret (the average performance over all simulations) at each node, rather than the strength of the chosen move, and that the various heuristic strategies used by strong engines introduce enough noise to make greedy playouts the better option. If you want to learn more, you might want to check out these two papers: http://www0.cs.ucl.ac.uk/staff/D.Silver/web/Applications_files/mcrave.pdf http://www0.cs.ucl.ac.uk/staff/D.Silver/web/Applications_fil... http://arxiv.org/pdf/1206.3382.pdf http://arxiv.org/pdf/1206.3382.pdf
• apetresc 11y ago
  I highly recommend the computer-go mailing list (http://computer-go.org/mailman/listinfo/computer-go http://computer-go.org/mailman/listinfo/computer-go), where most of the top-tier engine authors collaborate (including the authors of Zen, Pachi, etc). If you can read research papers, look into the bibliographies of Remi Coulom, who's work in ~2005 revitalized the field of computer go and is pretty much responsible for the quantum leap in engine strength over the last few years: http://www.remi-coulom.fr/ http://www.remi-coulom.fr/
  • CaiGengYang 11y ago
    This is great, didn't know there was a computer Go mailing list ! I am at the moment planning on paying some money to attend programming courses in basic languages like Python, Ruby and C++ in Singapore and start hacking a GO AI prototype. My idea is to build one that thinks more strategically rather than just relying on brute-force search. Since Go is such a large game, there are some areas especially mid game areas where computer programs in their current form simply cannot compete with the human brain at the moment. Professional Go players use strategic thought and positional awareness in huge chunks of the game , especially mid game when they are vying for territory. My intention is to try to capture some of these professional Go player's strategic awareness and sense of positioning through software and translate this into a machine that is more "intuitive" and able to think creatively and come up with new moves and variations by itself ..
  • CaiGengYang 11y ago
    Yup, Ive heard of him ... the professor who created Crazy Stone
• vinceyuan 11y ago
  [off-topic] As a Chinese, I do know what Weiqi (围棋,圍棋) is. I was surprised to see the English name of Weiqi is Go. (When I saw Go in this post, I thought it's Golang.)
  • eutectic 11y ago
    The English name is a transliteration of the Japanese.
  • erikb 11y ago
    A few Weiqi players like me were really angry when they used the name "Go" for the language where nearly all software engineers know that there is already a game with that (english+japanese) game. Btw, the Korean name "baduk"/"badook" is also used quite often. Sadly Chinese version is the least well known, which I think is because China and USA are the least connected of the three big Weiqi countries.
    • vinceyuan 11y ago
      "they used the name "Go" for the language" just because Google named that programming language 'Go'. Personally I don't like the name 'Go'. It's a verb. It should not be used as a name of a programming language or a board game.
      • nicholas73 11y ago
        I bet "Go" beat out "Goo" and "Ogle" in internal naming discussions.
        • vinceyuan 11y ago
          I think so too. Maybe another reason is we can use 'go func' in this programming language to start a concurrent function.
      • erikb 11y ago
        The name for the game is actually reasonable though, because it's the Japanese word. And in Japanese it doesn't mean "walk" but "chess-like game". The complete word is actually "Igo", using characters not too different (maybe traditional?) from the characters for Weiqi. Together Igo/Weiqi means "surround + chess-like". The last character Qi/Go refers to the corresponding more famous chess-like game, so in China it's Xiangqi, but in Japan it's Igo/Weiqi.
• simonhughes22 11y ago
  If you are wondering about intuition, google's deep mind and a number of other companies have applied deep convolutional neural networks for playing go. That is probably the closest to human intuition. Although I am not sure how you play a game on pure intuition, but I'm not a good Go player so I shouldn't comment.
  • deleted 11y ago
    [deleted]
  • CaiGengYang 11y ago
    Human beings (us) currently use a combination of pure calculation and intuition to play Go. Pure calculation is useful in small battles and corners where you can actually calculate the outcome of battles to pretty much 100% accuracy. However , there are still large chunks of the game where it is difficult for the human brain (even seasoned professional go players) to process huge sequences with similar levels of precision, for example early to mid game areas when both opponents are vying for influence and positional advantage. That's when the experience and intuition comes in. Professional go players are much much better at this due to years of experience playing top-notch games against other professional go players. The interesting question for the software developer and Go AI researcher is to attempt to use technology to capture a top-notch professional Go player's "intuition " in such situations.
• erikb 11y ago
  Computer Go is actually a huge topic. There are many different solutions, and they compete and still discover new things every year. If you want to get seriously into it you should get in touch with the people who work on it daily. There are people who write doctor theses about parts of a Go AI nowadays and what they create might not even be top notch. When I last checked, it was basically a set of very complex brute force algorithms. What they (need to) do is limit the search space a lot because there are just so many options. And that's where the smartness comes into play, removing subtrees from search space without visiting them. And as far as I know they tried pattern recognition (which is what we humans do) but it didn't work well for AIs. They work more often with density maps for some factors they calculate depending on the position, imho. But all that I know is really only very flat knowledge, and might be wrong.
  • CaiGengYang 11y ago
    Do you know who are these people who work on Go AI daily and how to get in touch with them ?