Artificial Intelligence Depot
Visiting guest. Why not sign in?
News, knowledge and discussion for the AI enthusiast.
FEATURES COMMUNITY KNOWLEDGE SEARCH  
Flesh and Machines: How Robots Will Change Us
Antitechnologists may shudder at the story line, but readers interested in the astounding possibilities of the digital age will be fascinated by Brooks's vision of what is and what will be.
More information at Amazon US UK

Reply to Message

Not registered yet?

The AI Depot has a focused community of friendly users. Rather than let anyone abuse the site at the brink of promiscuity, we prefer to let only those with an active interest participate... this simply requires registering.

Why not sign up!

Joining the site's community is completely free. You can then post messages freely, and customise your personal profile at will. Specific privileges will also be granted to you, like being able to access printer-friendly articles without restrictions. So, why not register?

Username:
Password:
Subject:
Email me when someone replies.
Body:

Parent Message

Go Artificial Intelligence

Essay - <a href="http://ai-depot.com/LogicGames/Go.html">Go
Artificial Intelligence</a>

Looking beyond the rules of Go, this article explains why Chinese Weiqi is such a fascinating game for AI researchers as well as normal players.

Analysis of human approaches to the game prompts the description of multiple algorithms and techniques that may 'solve' Go in the future.

http://ai-depot.com/LogicGames/Go.html

13 posts.
Monday 18 February, 16:02
Reply
Impressive!

Great essay! It makes me realise that I haven't played as much Go as I would have liked. No doubt I'll get the opportunity soon enough. Then it's just a matter of trying to work out a good way of doing this with AI... Challenge extended ;)

Again, nice work Andy!

935 posts.
Sunday 17 February, 11:26
Reply
My Mistake

Apologies for those who got upset when I referred to the game as Chinese Checkers. Despite Go having many names, it is not known as that. Chinese Checkers is very different.

The mistake has been fixed, sorry for the trouble.

935 posts.
Monday 18 February, 16:04
Reply
Deep analysis !

I'm new to this website and also to the A.I. world so I can't give any technical explanations. But I learn GO back in yr 2000 and I can say that GO's rule is easy to learn but playing the game is largely base on your experience -which is the ability to recognize opponent's formation/tactics in advance and come up with an appropriate 'reply'. Unfortunately, there are too many variations in the game so to get a computer to analyse the game will need a computer hundred times more powerful than a Deep Blue.

Anyway, anyone have any suggestions where I can start learning A.I. (programming in C++). Oh,I'm now still learning C++ basics.

1 posts.
Thursday 21 February, 07:42
Reply
Good essay, although some misinformation

I liked the essay overall, but some of the information is incorrect or misleading: (the dotted lines bracket text cited from the essay)

-----------
Some of the factors responsible for the game tree's enormity are shown below. (A comparison to chess is shown in brackets)
...
- players can pass
-----------

This is misleading, since passes are rarely made during the game itself, but only at the end or close to it, since passing usually confers no advantage to a player during most of the game. Many variations appear in the rules on how to regulate passing.

Theoretically, if you include passing, another node should be added to every single branch of the chess and go minimax trees: a player could resign. This, however, is unnecessary, since it is rarely in a person's advantage to do so (except for psychological/etiquette reasons).

-----------
Go stones bore no relation to each other until the very end of the game. It was almost impossible to see which group an individual stone belonged to, and in fact players mentally placed stones in more than one group.
-----------

Not really. Often, it is quite simple for humans (sufficiently experienced in the game) to tell which stones are connected to which group. Many weaker players, in fact, sometimes make oversimplifications, considering stones to be part of a group (visually) when in fact they could be cut off with a few tactics. I do agree with the last statement: in certain cases, stones can be a part of more than one group, although more often this just connects the two groups into one.

-----------
One of the best Computer Go players is The Many Faces of Go which is rated on the Go handicap system at 6 kyu (the same as an average humn player with about 1 year experience).
-----------

This is a bit misleading. It is rare for a person to attain the rank of 6 kyu in one year (although it does happen enough to make it not extraordinary).

Also, there are many different ranking systems across the world. A rating of 6 kyu on IGS (the International Go Server, a rated, online playing network), for example, is equivalent to about 3 kyu in the American and Japanese Systems, and about 6 kyu on the Korean system, and about 4 or 5 kyu on the Chinese system. The lower the kyu number, the stronger the player is considered to be.

A rank beginner who has just learned the rules can be anywhere between 30 and 50 kyu, and after about 6 months of study, the person can usually attain 15-20 kyu, although results do vary widely.

Even though many programs ostentatiously brandish that they have achieved the ratings of 3 kyu or 6 kyu and such, in actual practice they have a much lower ranking. One test put Many Faces of Go to be at a bout 17 kyu on IGS, which translates to about 13 kyu in the Japanese and American systems. Players did not know they were playing a computer program (which does make a difference).

Once players realize they are playing a computer program, and once players have tried a few games with the program, often the players are able to quickly figure out the program's weaknesses and exploit them endlessly, resulting in very bad scores for the programs. This is not "cheating" on the part of the human players, however, and these types of games shouldn't be dismissed as skewed results. Playing strength is not determined by first time games but rather in a long term test of gameplay.

-----------
There is a database available to all known as the
Joseki database. This contains thousands of endgame
positions and optimal plays for each. Many human Go masters know most of them so to that end it doesnt seem like cheating to store them in a Computer player (except a computer has perfect recall).
-----------

Firstly, Joseki is a set of corner **opening** patterns, not endgame patterns, and it contains only what professional players consider as the best plays they can think of in and of themselves (without considering other parts of the board).

Secondly, I doubt that there are many people who know **most** of the variations. There are a few, to be sure, but only the most dedicated can know most. One can easily become a very strong player without knowing even a small fraction of the possible variations and patterns of Joseki. Most players know only a small handful.

Thirdly, what is "cheating"? AI is AI. No human is expected to work out the entire game of Go based on first principles, nor should a computer. It would a miraculous feat for any human to be able to compose all of the Joseki by theory alone; Joseki (which vaguely means "established stones") is just the collection of the experience of thousands of years of high level Go playing and studying. No chess player is expected to work out an entire opening book by theory, nor is any chess program.

-----------
Perhaps there will eventually be enough computing power to brute-force search the game tree of Go, but will there be a good enough evaluation function? I hope not because Go is providing an excellent domain for AI researchers and i believe it will continue to bring out new ideas and approaches to game AI.
-----------

How is the Minimax tree not part of AI? AI can mean many things. Minimax is, of course, a very crude AI structure, and it emulates the rough outline of the human player's thought process (consider possible moves, look ahead through, assume other player plays well, choose best result, play corresponding move). Still, it is within the realms of AI, since it does create a program that seems to be showing intelligence. Yes, this point can be disputed on and on, but nonetheless, the Minimax tree is a valid AI construct, if not a very elegant or expandable one.

Overall, I enjoyed the essay, but I think that people should be aware of the (albeit minor) mistakes/ambiguities in the essay.

1 posts.
Monday 13 May, 21:21
Reply
Go Issues!

I'm sure Andy is better placed to reply, but I'll make my points briefly.

1) The tree size in theory is as Andy describes it. If you add some expert knowledge to your AI by removing that factor, then you've optimised your search slightly. You could do that in many other cases too (not put a stone where it will be instantly removed for example). I think the point is for a learning algorithm, you may want to make the AI aware of that option in the first place.

2) Groups of stones in the start of the game are generally physically isolated though. Then it all clicks together, and you have a bigger problem to deal with!

5) As Rodney Brooks once said, when something is solved by an algorithm, AI researchers claim it's no longer part of their field. AI thereby never gets any successes! Minimax is by this definition just a search algorithm.

Though the rough outline of minimax is indeed similar to the human deliberative process, many specific details of current "standard" implementations make it very unhuman-like (problems with depth cut off, considering all options, not learning opponents reactions, static evaluation functions and assumptions).

In any case, I do not believe in the ability of Minimax to "solve" go any time soon...

Anyway, my 2p ;)

935 posts.
Sunday 19 May, 13:37
Reply

Back to the Artificial Intelligence Depot.