Support NeoGAF

[jedimike]

http://www.research.microsoft.com/mlp/trueskill/Details.aspx

This is the new ranking system that MS uses in every game on XBL. I mean every ranked game from PDZ to Hearts. It's a whole lot of mathematical mumbo jumbo, but it takes into account the number of games you have played, which no other ranking system has done. Your 100th game will not have the same value as your first.

The systems was created by 5 people in Microsoft's R&D Division. They weren't solicited to do the project... they were just avid Halo gamers who wanted to make a better system. There current project is to build an AI for some Chinese game called .. Go (I think that's what it is called). I guess it takes a lifetime to master and for some reason computers can't handle the game... even though computers can do Chess very well.

Might be interesting for some of GAF's more intellectual types.

 

[Speevy]

Yeah, it pretty quickly finds your match. Of course, some games are unavailable when you try to join.

 

[krypt0nian]

Major Nelson interviews two of the dev's behind this on the current episode as well. Very interesting listen.

http://www.majornelson.com/2006/01/02/show-156-the-first-one-of-the-new-year/

 

[Mr Jared]

There current project is to build an AI for some Chinese game called .. Go

Damn. They must be freakin' brilliant.

<-- Big Go Fan

 

[KingV]

A bit Off Topic, typical AI for Go is very similar to typical AI for chess, which is to say, Chess programs will normally just calculate every possible move, and then every possible move you can make in response, and then every possible move that the computer can then make in response, and so on until the developers collectively decide "ok that's enough iterations" or it hits some kind of physical memory limit or whatever. It then picks the move which provides the best probability of winning down the line. Since chess programs are looking like 5, 10, 15, 20 moves down the line that is why freaking GBA Battle Chess can whup the everloving shit out of you day in and day out unless you're Bobby Fischer. They're just doing a really complex statistical problem. I'm sure there's some algorithms that do it a bit smarter, like removing obvious bad move threads, and so forth, but that's the overall gist. This is known as a min-max algorithm, IIRC.

Go, which I've never personally played and is apparently popular in Asian countries, is a game that is considered to be Chess like in complexity, in that the people who are really good at it, are so much better than you that they are practically freaks of nature and are thus quite frequently accused of using the standby glitch. Anyway, Go, by it's nature, is also an order of magnitude more complex in the number of potential iterations available on a particular move. Therefore, Go AI in general tends not to be able to see as far in the future, and is thus "stupider" to people who clearly don't play their strategy in the same brute force way that computer programs do. So, anyway, designing a new Go AI is obviously some kind of AI challenge.... at least until computers become fast enough that Go min-max algorithms can basically beat everybody down too.

 

[Grug]

A bit Off Topic, typical AI for Go is very similar to typical AI for chess, which is to say, Chess programs will normally just calculate every possible move, and then every possible move you can make in response, and then every possible move that the computer can then make in response, and so on until the developers collectively decide "ok that's enough iterations" or it hits some kind of physical memory limit or whatever. It then picks the move which provides the best probability of winning down the line. Since chess programs are looking like 5, 10, 15, 20 moves down the line that is why freaking GBA Battle Chess can whup the everloving shit out of you day in and day out unless you're Bobby Fischer. They're just doing a really complex statistical problem. I'm sure there's some algorithms that do it a bit smarter, like removing obvious bad move threads, and so forth, but that's the overall gist. This is known as a min-max algorithm, IIRC.

Go, which I've never personally played and is apparently popular in Asian countries, is a game that is considered to be Chess like in complexity, in that the people who are really good at it, are so much better than you that they are practically freaks of nature and are thus quite frequently accused of using the standby glitch. Anyway, Go, by it's nature, is also an order of magnitude more complex in the number of potential iterations available on a particular move. Therefore, Go AI in general tends not to be able to see as far in the future, and is thus "stupider" to people who clearly don't play their strategy in the same brute force way that computer programs do. So, anyway, designing a new Go AI is obviously some kind of AI challenge.... at least until computers become fast enough that Go min-max algorithms can basically beat everybody down too.

My head just exploded.

Only thing I know about Go is what I read ina book about Nintendo's history. Yamauchi used to take people to school at that game.

 

[sangreal]

These guys also designed the self-learning AI in Forza: www.drivatar.com

(not just the drivatar feature)

 

[crisdecuba]

Hrmm... what if the final name of the RVN was "Nintendo TrueSkill (NTS)" ? It's what came to mind when I saw the name of the thread.

~Cris

 

[Prospero]

There current project is to build an AI for some Chinese game called .. Go (I think that's what it is called).

Good luck with that.

I guess it takes a lifetime to master and for some reason computers can't handle the game... even though computers can do Chess very well.

This link is a good place to begin reading about the difficulties in programming Go AI. KingV's post is generally correct but understates the case. Part of the reason that chess AI is so strong is that it's building on decades of shared research. Go AI has had a similar amount of research time put into it (more so in the East than in the West), but the results have been much less fruitful:

It is the intuitive nature of [Go] that makes it so hard to program. Currently the best programs on the fastest computers play little better than beginners, though the financial rewards for improving on this are huge. For twenty odd years (until the recent death of the donor) there was prize of $1 million for a program which could beat a professional player. This goal is still unlikely in our lifetimes.

The basis for computers playing games is the Minimax algorithm invented by Claude Shannon, which examines the tree of possible moves and counter-moves up to the limits of allowed time and computer resources. It evaluates all the positions reachable at the outer edge of the tree, and then uses the algorithm to prune the tree back down to the best first move.

The problems with computer go start with the size of the tree, due to the large number of potential moves. Chess has an average 30 or so legal moves per turn, generating of the order of a million possible positions within 5 moves. But go has an average of about 250 legal moves per turn, generating of the order of a thousand billion positions. The real problems begin, though, with the evaluation function. Computers have great difficulty deciding which is the better of two go positions, and cannot even reliably say who is the winner when the game is over.

That's the hell of the thing. Scoring go for humans is a pretty simple task of pattern recognition, but the only way to really learn how to do it is to have someone explain it to you--at least in my case, reading about it in a book was useless. I've yet to see a go program that had the capability to mark dead stones, though I haven't downloaded any Go programs in a year or so.