Ask HN: How does Weiqi AI work? | Hacker News Reader

Ask HN: How does Weiqi AI work?

16 pointsCaiGengYang27 comments

Anybody plays Weiqi around here and understands how Go AI works?

I have been playing Weiqi for many years and even represented Singapore several times when I was much younger and won 3rd place at the World Youth Amateur Tournament and 12th place at the World Amateur Weiqi Tournament.(though I play much less in recent years)

When I first started out, Go AI was weak, really really weak like 30 kyu or something and a 5 year old kid who had learned Go for 2 weeks could defeat it easily.

Now I see Go AI reaching strong 5-6 dan level like ZenBS and the program seems pretty strong to me. (I could probably win 50-60% of my games against ZenBS if I play seriously). And ZenBS even won a game against Takemiya Masaki even though it was given 4 stones handicap.

How do Go programs like ZenBS work ? Does it perform brute search or does the AI play "intuitive" moves that resemble human intuition ?

Cai GengYang

View on HN

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

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.

Not to be pedantic, but it's "Monte Carlo", not "Money Carlo". In case OP wanted to search the phrase.

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_fil...

http://arxiv.org/pdf/1206.3382.pdf

I highly recommend the computer-go mailing list (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/

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 ..

Yup, Ive heard of him ... the professor who created Crazy Stone

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/... 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.

> 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 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.

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 ...

Sorry, yes, you are correct - my memory was playing tricks.

Playing tricks about what ?

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.

Do you know who are these people who work on Go AI daily and how to get in touch with them ?

[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.)

The English name is a transliteration of the Japanese.

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.

"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.

I bet "Go" beat out "Goo" and "Ogle" in internal naming discussions.

I think so too. Maybe another reason is we can use 'go func' in this programming language to start a concurrent function.

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.

Its actually surprising to me that I have played this game for such a long time and still don't know the origin of the word "Go".

I have always called it Weiqi as I was taught in mandarin. From what I understand, Weiqi originated in China, and for most of history was the dominant player in this game, until Japan took over around World War 2 (the rise of Japanese military power , technology, and standards of living probably all contributed to this).

The Japanese took up the game, called it Go and helped spread the game to the west and the name has stuck ever since.

Japan has since been eclipsed by both Chinese and Korean players though.

International Go Tournaments are now mainly dominated by Chinese and Korean national team players it seems to me.

Go terminology used in the West is all from Japanese. The reason can be traced back to the first organized Western interest in Go, from a German engineer who visited Japan in the 1880s: https://en.wikipedia.org/wiki/History_of_Go#Development_in_t...

A bit more trivia for you: the Japanese pronunciation is "go" for the same kanji. That sounds weird to you as a Mandarin speaker, but that is because kanji pronunciation is taken from the old Wu dialect. They call it "go-on" in Japanese, or "wu-yin" in Mandarin, meaning "sound of Wu". Apparently the W's often become G's in Wu (like the pronunciation for the number 5).

There you go. As a Chinese, you can feel comfortable that the weird Westerners are still calling Go by its Chinese name.

Hmm .. Go should be for everybody, not just Chinese

https://en.wikipedia.org/wiki/Computer_Go

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.

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.

Reply on news.ycombinator.com