What is Digg?45 Comments
- clink0914, on 10/12/2007, -5/+44unfortunately the machine that calculates the algorithm freezes up at times and spits out a weird 216 digit number
- inactive, on 10/12/2007, -0/+20My computer can beat me at Chess - but I can whip it's ass at Kickboxing.
- ideogram, on 10/12/2007, -1/+19This article is content-free.
- rhinopig, on 10/12/2007, -1/+12The movie was Pi, and yeah it was for stocks but the game they played was go, not chess.
- Auerbeck, on 10/12/2007, -5/+16Al Gore rhythm?
- Lnomis, on 10/12/2007, -0/+11Notice that 216 factorises as 6*6*6. Coincidence? I think not.
- TomP, on 10/12/2007, -1/+11Now all we need is an algorithm that helps humans beat computers at Go
- Zique, on 10/12/2007, -0/+9Whoa, whoa... not far from reaching the level of professional players? That would mean this algorithm would improve computer Go by roughly the same amount as last 10-15 years have. Quite a bold claim, especially considering the UCT technique they say they're using isn't that new.
- trigger0219, on 10/12/2007, -0/+8Here is content...
http://senseis.xmp.net/?UCT
Contains pseudo code of algorithm and links to academic papers and more - au071, on 10/12/2007, -1/+7For now maybe, but have you seen terminator?
- TwimA, on 10/12/2007, -0/+6Currently the best computer Go programs on GO servers are rated somewhere between 10kyu to 5kyu.
The ranking goes from 30kyu (weakest beginner rank 30k) to 1kyu, and then from 1dan to 7dan (strongest amateaur rank, 7d). A professional 1dan player (1p) is said to be around 7dan amateaur, and professional dan ranks go to 9dan. (9p)
A talented new player is said to reach amateaur 1 dan (that's better than 1 kyu) in about a year.
So currently the best computer go programs out there are no competition for someone who has played actively for about a year.
So i won't believe in professional grade programs before i see it. - chaosmachine, on 10/12/2007, -0/+6i think digg killed zdnet india..
http://news.zdnet.com/2100-3513_22-6161042.html - Asidic, on 10/12/2007, -0/+5Am I the only one that noticed the title and description contradict each other?
- kaffiene, on 10/12/2007, -0/+3The article made my teeth hurt. Using the term 'marbles' instead of 'stones' is really aggravating. Not to mention that the claims are dubious and the details were scant.
- TwimA, on 10/12/2007, -0/+3This is easily winnable by a amateaur that has played for about 2months.
Copying your opponents moves and mirroring them doesn't work in Go.
Building up a ladder for example quickly destroys such a try. - Dantetheinferno, on 10/12/2007, -0/+3Oh well, Doesn't matter to me... I'm only 19kyu... :(
- alok0, on 10/12/2007, -0/+2I'll second that, the computers wern't all that good to begin with. So unless it was quite a major improvement, like comparing a handheld chess AI to deep blue: it won't be huge news.
- ictoan, on 10/12/2007, -3/+5There's a DS game called Itsu de mo Doko de mo Go that let's you play Go and it's pretty hard for me so far to beat it. Go is fun though; much more interesting than Chess.. XD
- attention, on 10/12/2007, -1/+3(thats a mirror)
- Scarblac, on 10/12/2007, -0/+2That's not the only hard part. Chess has 20 possible moves in its opening position, and perhaps 20-30 possible moves in the average game position. So thinking two moves deep for both player only means looking at about 30^4 = 810,000 positions (ballpark).
Go, on the other hand, has a branching factor of about 150. Thinking two moves deep for both players is 506,250,000 different lines.
That's just not tractable. Taken together with the evaluation function problems, it means that the usual minmax algorithm used for chess like games isn't feasible, something entirely different is needed. - inactive, on 10/12/2007, -0/+2about 100 years well see on digg, title:
new chip helps computers beat humans at everything! - Lnomis, on 10/12/2007, -0/+2Reaching 1 dan in a year would be a massive accomplishment. Realistically, you would need to study every day and have a really good teacher.
- Ascendant, on 10/12/2007, -0/+2agreed- not only can pros easily beat the best computer programs for Go, even reasonably competent amateur players can do the same.
- abhiroop, on 10/12/2007, -1/+3thats "JO-incidence"
- mrbass, on 10/12/2007, -0/+1Daredemo Kantan Chou Chikun no Tsumego is actually a better DS game especially if your beginning. It's more of thousands of problems and you need to solve them. Basically you are try to make eyes and save your pieces so usually you have a move or a few and it'll tell you if your right or wrong. If wrong, you can keep attempting it till you get it right.
I have a screenshot of it here
http://mrbass.org/nintendoDS/games - barktwiggs, on 10/12/2007, -2/+3Agents are...
GO! - Bhima, on 10/12/2007, -1/+2Oh, I would say it's 100% content free just mostly free of content... like say enough to fill the inside of a book of matches.
- Zique, on 10/12/2007, -0/+1Hardly a massive accomplishment, some kids do it in 6 months and it's doing in in one year is not uncommon at all, although it would require daily training.
- foxyfoxykitsune, on 10/12/2007, -0/+1Thanks I knew someone had to try to make a ds Go game I just hadn't found one yet, Ill give this a try, as I'm abysmal at go so So the sad state of AI Go does not hurt me yet and I want some way to practice Go on the go.
- Bisqwit, on 10/12/2007, -1/+1Yeah, it seems like the one who wrote the article knows nothing about the game of Go. "Capture spaces"... shudder.
Buried as inaccurate. - KragTheDigger, on 10/12/2007, -1/+1quoting ACM ICPC problems now ? :)
~K - dextius, on 10/12/2007, -1/+1 [golf clap]... hahahah..
- Karmalary, on 10/12/2007, -2/+1I prefer Pente
http://www.pente.net/ I - sikosmurf, on 10/12/2007, -2/+1No, the title is what the article is about, the description is the background.
- KragTheDigger, on 10/12/2007, -4/+2Sorry for self-promoting, but I think this blog of mine is somehow related: http://foryourreview.blogspot.com/2007/02/true-ai-larry-pages-take.html
The blog was prompted by Larry Page's recent comments on AI. I mention checkers in that post, but the same applies to go and, in general, to any application of AI: I don't like the common approach of making an expert system (as most go AIs are); I'd rather let the program learn on its own, given the proper context and goals.
Go is a very interesting problem. Since the players can place their next stone just about anywhere on the board (barring suicide and ko restrictions), the computational complexity is exponentially larger than that of chess. It took a while for chess programs to become competitive, and that was achieved via libraries and expertise built-in the chess program itself. With the same approach, a pro go AI might never see the light.
~K - jjrohal, on 10/12/2007, -2/+0Computers can beat some of the world's top chess players, but the most powerful machines have failed at the popular Asian board game Go, in which human intuition has so far proven key.
Two Hungarian scientists have come up with an algorithm that helps computers pick the right move in Go, played by millions around the world, in which players must capture spaces by placing black-and-white marbles on a board in turn.
"We are not far from reaching the level of a professional Go player," Levente Kocsis of the Hungarian Academy of Sciences computing lab Sztaki said.
The 19x19 grid board that top players use is still hard for a machine to use, but the new algorithm is promising because it makes better use of the growing power of computers than did earlier Go software.
"Programs using this method immediately improve if you use two processors instead of one, say, which was not typical for earlier programs," Kocsis said.
Whereas a chess program can evaluate a scenario by assigning numerical values to pieces--9 to the queen and 1 to a pawn, for example--and to the tactical worth of their position, that technique is not valid for Go.
In Go, all marbles have an identical value, and scenarios are more complex, so the computer has to think about all potential moves through the end of the game and emulate the outcome of each alternative move.
Even the most powerful computers have failed at that task, but Kocsis and colleague Csaba Szepesvari have found a way to help computers focus on the most promising moves, using an analogy with slot machines in a casino.
Punters will find that certain one-armed bandits in a casino appear to pay more on average than others, but an intelligent player should also try machines that have so far paid less, in case they are hiding a jackpot, Kocsis said.
The key is to find the balance between the two sorts of machine.
Go software using a similar method, called UCT (Upper Confidence bounds applied to Trees), does not have to scan all possible outcomes of a game and can quickly find the best mix of scenarios to check.
"This bandit algorithm has proven advantages," Kocsis said.
The possible outcomes of a game are like branches of a tree, and earlier Go programs, unable to scan all branches, picked some at random and tried to find the best move from that sample.
The UCT method (PDF) helps a computer decide which routes are most worth investigating. Programs based on it have consistently won games against most other machines, according to Kocsis. - mtrip, on 10/12/2007, -5/+2And it's damn near impossible to count up the score at the end unless you're playing on a computer and it can do it for you.
- standrum, on 10/12/2007, -6/+3maybe the computers just get bored cause the game take FOREVER to play
- maximthegreat, on 10/12/2007, -4/+0I came up with an amusing way to cut the complexity of go. Have the program do the exact same, but symmetrically opposite, move as his opponent until the state space gets small enough as the board fills up. It maintains equilibrium perfectly. Not exactly a serious technique, of course.
- StellarlyAstral, on 10/12/2007, -8/+3Clink, that was too good of a comment.
- hiPpymIck, on 10/12/2007, -6/+1good backgammon - its pretty fast
http://www.gnubg.org/ - rujulz, on 10/12/2007, -7/+1test 1-2-3
- agrabob, on 10/12/2007, -11/+3^^ next poster needs to reply with the movie thats from
but, it was for stocks, not chess right? - hessef, on 10/12/2007, -12/+0Yeesh--the commenting can wait until after the store changes (assuming that the change is actually noteworthy). Just because the internet can be used to report something in seconds doesn't mean that you can't wait for the story to actually develop.
- hessef, on 10/12/2007, -12/+0Ach--wrong story and I can figure out how to delete the previous comment. Sorry 'bout that one.
© Digg Inc. 2009
— Content created and posted by Digg users is