Beta

Slashdot: News for Nerds

×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Computer Defeats Human At Japanese Chess

CmdrTaco posted more than 3 years ago | from the king-me dept.

Supercomputing 178

Calopteryx writes "A computer has beaten a human at shogi, otherwise known as Japanese chess, for the first time. As New Scientist reports, computers have beaten humans at western chess before, but that game is relatively simple, with only about 10^123 possible games existing that can be played out. Shogi is a *bit* more complex, offering about 10^224 possible games."

cancel ×

178 comments

Best use of the word "only" ever. (2, Funny)

nedlohs (1335013) | more than 3 years ago | (#33871052)

pointless comment text

*yawn*. Call me when we lose at Go. (-1, Offtopic)

DeafDumbBlind (264205) | more than 3 years ago | (#33871056)

nt

Re:*yawn*. Call me when we lose at Go. (1)

Tatarize (682683) | more than 3 years ago | (#33871234)

We can lose at Go. It's just not computers don't typically beat a person who tries and knows how to play. Here we see that this is the first time in human history that a human has managed to lose at this game. It seems like even random moves should be able to happen into defeating some human some time. Human takes dive against random algorithm.

Re:*yawn*. Call me when we lose at Go. (5, Insightful)

Anonymous Coward | more than 3 years ago | (#33871282)

soooo irritating whenever a go player brings this up.

Go only wins through brute force.
go is 19x19
shogi is 9x9
chess is 8x8

If a game like shogi or chess was extended to 19x19 it would be vastly harder for a computer.

Computers playing Go on 9x9 have beaten 9th dan.
And if it was 8x8 it would be even easier.

What makes Go hard isn't anything particularly neat about the game.
Is just a boring brute force exercise.

Re:*yawn*. Call me when we lose at Go. (1, Troll)

arose (644256) | more than 3 years ago | (#33871452)

If a game like shogi or chess was extended to 19x19 it would be vastly harder for a computer.

The difference is that those games just don't scale.

Re:*yawn*. Call me when we lose at Go. (2, Insightful)

Anonymous Coward | more than 3 years ago | (#33871682)

Sure they can.
The rules just need extending.

Is no different than fischer random chess dramatically increasing chess complexity for an AI.

That's the problem for me with go. It is a simplistic game that, yes, takes a lot of skill for a human. No doubt.
But the number of varying interactions is, well, limited by the tiny ruleset.

Re:*yawn*. Call me when we lose at Go. (2, Insightful)

PiSkyHi (1049584) | more than 3 years ago | (#33872362)

Go vs. Chess. RISC vs. CISC all over again.

Re:*yawn*. Call me when we lose at Go. (1)

mcneely.mike (927221) | more than 3 years ago | (#33873264)

3d chess.... "Check mate, Spock."

Re:*yawn*. Call me when we lose at Go. (1)

jgtg32a (1173373) | more than 3 years ago | (#33871786)

I don't claim to know any thing about AI, but brute-forcing doesn't sound like a good way to solve problems, and humans obviously don't user brute force when they play so ...

Re:*yawn*. Call me when we lose at Go. (2, Insightful)

Moridineas (213502) | more than 3 years ago | (#33871874)

Depends on what your definition of "good" is. Efficient? Easy? Fast? etc

If you can map out every possible outcome of a game given every possible move (calculate every ply), you can play optimally. You might need multiple super computers, lots of time, etc (for now!), but if you can do that, you can pretty much guarantee optimal play. Other "smarter" methods are of course faster, more resource efficient, etc, but not as optimal if you know every possible outcome.

Re:*yawn*. Call me when we lose at Go. (1, Interesting)

Raenex (947668) | more than 3 years ago | (#33872086)

If a game like shogi or chess was extended to 19x19 it would be vastly harder for a computer.

The difference is that nobody would want to play a chess game on a board that size. Go grew to 19x19 by player preference, not as some artificial limit to make it hard to beat the computer.

What makes Go hard isn't anything particularly neat about the game.

Concepts and patterns are more important in Go. There isn't a simple piece count that dominates the evaluation.

Re:*yawn*. Call me when we lose at Go. (0, Flamebait)

PiSkyHi (1049584) | more than 3 years ago | (#33872320)

It's precisely because the brute force method can be defeated just by scaling up the board size that go is a better game - humans don't use brute force to play it, which makes it a real game.

Re:*yawn*. Call me when we lose at Go. (1)

Blackbrain (94923) | more than 3 years ago | (#33872762)

What makes Go hard isn't anything particularly neat about the game. Is just a boring brute force exercise.

I'm curious why you think Go is a brute force game. I'm not sure you've actually played the game before, maybe you're thinking of Atari Go [xmp.net] ?

A real game of Go has very subtle strategies. Using brute force tactics against a strong player usually ends in a loss, which is why computers have only been able to win against Dan level players on very small boards or with very large handicaps.

Re:*yawn*. Call me when we lose at Go. (1)

purfledspruce (821548) | more than 3 years ago | (#33873308)

You misunderstand what GP was saying..."brute force" in this case means computationally being able to examine every possible path for the game to take, not the play strategy.

Re:*yawn*. Call me when we lose at Go. (3, Interesting)

Abcd1234 (188840) | more than 3 years ago | (#33872848)

What makes Go hard isn't anything particularly neat about the game.

Incorrect. There are many things that make go difficult for a computer to play: positional evaluation is tough. The branching factor is huge (unlike Chess and similar games, the number of available moves in a given board configuration is very large, as a stone can be played virtually anywhere on the board). Life-and-death is difficult to calculate. There are interactions between local and global play...

Go's board size is certainly a factor, yes, but if it were the only one, computers should excel at 13x13 or 9x9 games, and yet they don't.

Re:*yawn*. Call me when we lose at Go. (2, Interesting)

bluefoxlucid (723572) | more than 3 years ago | (#33871314)

I'm in the process of joining the AGA ... that is, I'm strategically holding off until I get more Go literature under my belt (I can bank life-and-death problems against high level players; but my initial set-up and my capture race performance is weak, so my territory boundaries are not far reaching enough and creating wider ones stretches me thin). Maybe in 2 months.

Re:*yawn*. Call me when we lose at Go. (4, Interesting)

TheCycoONE (913189) | more than 3 years ago | (#33871330)

I spent a summer once working for a professor who has spent his life trying to develop an AI for Go!

In particular I was compressing read-only hash tables of end states. He was basing his approach on the work of someone who had developed AI for checkers but I think it's obvious that Go is a little bit bigger problem.

(To be specific: http://lie.math.brocku.ca/twolf/home/publications.html#3 [brocku.ca] )

Re:*yawn*. Call me when we lose at Go. (1)

Amouth (879122) | more than 3 years ago | (#33871598)

In particular I was compressing read-only hash tables of end states.

*cringe* so basically of all possible states? as in GO the game is over when both players pass twice in succession. their is no end game board layout(s).

i fee sorry for you especially if that guy was trying to go for a full 19x19..

Re:*yawn*. Call me when we lose at Go. (1)

TheCycoONE (913189) | more than 3 years ago | (#33872048)

It was actually Life and Death states of various numbers of pieces. Still huge, but I misrepresented the problem somewhat.

Re:*yawn*. Call me when we lose at Go. (4, Insightful)

sexconker (1179573) | more than 3 years ago | (#33871610)

Go is a simple game.
Mind numbingly simple, in fact.
It's just a LARGE game.

Chess has actual complex rules. It is a hard game.
Mind-numbingly hard, in fact.
It's just a relatively SMALL game.

Re:*yawn*. Call me when we lose at Go. (-1, Troll)

PiSkyHi (1049584) | more than 3 years ago | (#33872436)

Sounds to me like you think remembering the rules for chess is somehow impressive or even vaguely relevant to the quality of a good game.

Re:*yawn*. Call me when we lose at Go. (4, Funny)

interkin3tic (1469267) | more than 3 years ago | (#33872350)

You're bored by the relatively fast advance of computer intelligence? Humans have for the first time in recorded history lost their title of "Best at Shogi" to computers (and orangutangs have presumably been bumped down to 3rd). That may not have any real-world significance, but in the grand scheme of things, it wasn't too long ago that computers couldn't beat us at math.

You're on a forum with a focus on computers, and you say that's boring? Jesus, what WOULD interest you? If it ran linux using a beowulf cluster? Simpsons quotes?

Well fine, I for one welcome our new shogi-playing computer overlords.

That's nothing... (2, Funny)

msauve (701917) | more than 3 years ago | (#33871086)

a computer could have beaten me at shogi a long time ago, but it never asked to play.

Re:That's nothing... (2, Funny)

i-c-electrons (1467179) | more than 3 years ago | (#33871150)

Hell a computer could probably beat me at connect four.

Re:That's nothing... (1, Funny)

Anonymous Coward | more than 3 years ago | (#33871336)

A computer beat me at Connect One once. I never should have granted it's wish to go first...

Re:That's nothing... (1, Funny)

Anonymous Coward | more than 3 years ago | (#33871382)

Computers always beat me at tic-tac-toe...

Re:That's nothing... (1)

wagnerrp (1305589) | more than 3 years ago | (#33871472)

Well that's your own damn fault. Tic-tac-toe is un-winnable.

Re:That's nothing... (4, Funny)

MikeyO (99577) | more than 3 years ago | (#33872568)

its totally winnable. you just have to get three in a row! (do you not even know the rules!?) :)

Re:That's nothing... (2, Informative)

wagnerrp (1305589) | more than 3 years ago | (#33873600)

OK. How about... tic-tac-toe cannot be won against an opponent who has simulated every possible move. There is no way to set up a trap that they cannot block.

Re:That's nothing... (1)

veganboyjosh (896761) | more than 3 years ago | (#33871728)

A strange game. The only winning move is not to play.

Re:That's nothing... (1)

Yaotzin (827566) | more than 3 years ago | (#33871856)

A strange game. The only winning move is not to play.

Unless you cheat.

Re:That's nothing... (2, Funny)

shentino (1139071) | more than 3 years ago | (#33872174)

Kobayashi maru anyone?

Re:That's nothing... (1)

Quato (132194) | more than 3 years ago | (#33872452)

The computer wanted to play nice game of chess, but you kept wanting to play Global Thermonuclear War

Re:That's nothing... (1)

masmullin (1479239) | more than 3 years ago | (#33873090)

Gtw is a lot more fun. It allows me to take out my aggressions in ways previously unfathomable.

Nice headline (3, Insightful)

mrvan (973822) | more than 3 years ago | (#33871114)

First time "a computer" has beaten "a human", eh?

I'm sure they mean: first time a computer has beaten a 1st dan (or whatever shogi ranks are called) grandmaster in an offical tournament setting...

Also, I don't think the theoretical number of games is very relevant. Paper-scissor-rocks has an infinite amount of possible games, ie 1 draw followed by a win, 2 draws ... inf draws. Much more relevant would be branching factor, difficulty of estimating positional strength, horizon problems, long term dependencies etc.

Re:Nice headline (2, Funny)

jwietelmann (1220240) | more than 3 years ago | (#33871140)

Yeah, I'm pretty sure a computer could beat me at shogi all day long, seeing as I have no idea how it's played.

Re:Nice headline (1)

The MAZZTer (911996) | more than 3 years ago | (#33871244)

Chess can also be considered to have an infinite number of games where both players simply move a single piece back and forth forever. But it would seem pointless to track those.

Re:Nice headline (1)

Kjella (173770) | more than 3 years ago | (#33871350)

Actually no you can't, 50 move rule. But yes, there are far more possible games than there are possible positions.

Re:Nice headline (0)

Anonymous Coward | more than 3 years ago | (#33871448)

Both the 50 move rule and the threefold repetition rule require one of the players to declare a draw. If neither player does this, the game can proceed indefinitely.

Re:Nice headline (0)

Anonymous Coward | more than 3 years ago | (#33871374)

That's often defined as a draw after three repetitions of the same board position. Specific guidelines may vary across tournaments and countries.

Re:Nice headline (1)

PiSkyHi (1049584) | more than 3 years ago | (#33872508)

Even more-so than compression algorithms, moving pieces like this adds no complexity to the game outcomes at all.

Re:Nice headline (1)

Chris Mattern (191822) | more than 3 years ago | (#33873848)

Chess can also be considered to have an infinite number of games where both players simply move a single piece back and forth forever. But it would seem pointless to track those.

Wrong, because chess has a rule that if you have the same position three times, the game is a draw.

Re:Nice headline (4, Informative)

Speare (84249) | more than 3 years ago | (#33871254)

"First dan" or shodan is roughly the level of "starting to get serious" or freshman-professional. This goes for karate, shogi, igo (go), language, and pretty much the grading scheme in all other Japanese arts and skills including ikebana and shodo calligraphy. Westerners often think the black belt in karate is the pinnacle, when indeed your first black belt is just the beginning of a lifelong journey. Most schools go to 9-dan (kyuudan) and have an honorary 10-dan or 11-dan ranking for the highest practitioner in the world. Everything below 1-dan is just weeding out the hobbyists and dilettantes.

Re:Nice headline (4, Funny)

srussia (884021) | more than 3 years ago | (#33871494)

11-dan ranking for the highest practitioner in the world.

+11 Funny

Re:Nice headline (0)

Anonymous Coward | more than 3 years ago | (#33873232)

Seeing "First dan" in quotes reminds me of Lieutenant Dan (Gary Sinise). Please tell me where Lt. Dan ranks on the dan scale! :)

"Lieutennnnantttt Daaaaan!" --Forrest Gump

Re:Nice headline (1)

black_lbi (1107229) | more than 3 years ago | (#33871342)

No. The number of possible games for rock-paper-scissors played by two protagonists is combinations of three taken two at a time (with repetitions) - 9.

Re:Nice headline (4, Interesting)

bluefoxlucid (723572) | more than 3 years ago | (#33871348)

Actually, I used to routinely thrash the top level in typical Checkers programs. Shogi is interesting because if you can hold your own enough to start capturing pieces, you can become a huge nuisance. Every piece you capture can be played back on the board on your side on any turn; this makes Shogi a little complicated for a computer, since suddenly you have no checkmate on the board but there's 10 ways I can play a Horse or Rook and trap you in a checkmate.

Re:Nice headline (1)

The_mad_linguist (1019680) | more than 3 years ago | (#33872024)

Of course, since draughts is now solved, a really high level program will never be defeated.

Re:Nice headline (1)

bluefoxlucid (723572) | more than 3 years ago | (#33872674)

Of course; but Shogi isn't, and it suffers the same problem as any unsolved program: determining the absolute best move is hard. Shogi only becomes more complex during play, not simpler.

Re:Nice headline (1)

john83 (923470) | more than 3 years ago | (#33873432)

Draughts has only been solved on the 8x8 board, and the best programmes for the 10x10 version caught up with the top humans a few years back.

It's interesting to speculate about how the advancement of playing software might hint at how tactics and strategy are balanced for the various board games. I mean, a chess computer has no concept of a plan, and even Kasparov or Topalov or whoever can only calculate a handful of positions a second. Of course, the most interesting part of that problem is how to pose the question.

Re:Nice headline (1)

fusiongyro (55524) | more than 3 years ago | (#33872114)

There are exactly 6 different rock-paper-scissors games:

  1. Rock-Rock
  2. Rock-Paper
  3. Rock-Scissors
  4. Paper-Paper
  5. Paper-Scissors
  6. Scissors-Scissors

The other factors you bring up are irrelevant if the number of possible games is small.

Re:Nice headline (1)

SlimXero (1001229) | more than 3 years ago | (#33872410)

Incorrect. There are exactly 9 different rock-paper-scissors games:

Rock-Rock
Rock-Paper
Rock-Scissors
Paper-Rock
Paper-Paper
Paper-Scissors
Scissors-Rock
Scissors-Paper
Scissors-Scissors

You may attempt to argue semantics such as Rock-Paper is the same game as Paper-Rock, but you would be wrong. In a Rock-Paper game, the second player would be the victor, where as in a Paper-Rock game, the first player will claim the spoils. You could argue and say that from a scientific standpoint, that the victor doesn't matter. Wrong again. The very spirit and focal point of competitive scenarios is to win. No one turns on COD and says "How many different ways can I die today?". Sure, the outcome may not matter to one or more of the players, but the likelihood of going into a competitive situation, intentionally attempting to lose, is slim. Whilst none of the parties involved will be upset if they lose, they will still continue to pursue a victory.

Re:Nice headline (1)

fusiongyro (55524) | more than 3 years ago | (#33872856)

I would almost agree with you if we were talking about chess, where players are meaningfully distinguished by the rules of the game, but we're not talking about a game in which that happens. There are exactly six different games in rock-paper-scissors. A computer doesn't have to do anything differently to account for which player is which in analyzing this game.

Even if I agreed with you, you're missing the point. The OP stated that there are an infinite number of rock-paper-scissors games. Either one is substantially less than infinite.

Re:Nice headline (0, Redundant)

SlimXero (1001229) | more than 3 years ago | (#33872902)

Agreed.

Re:Nice headline (0)

Anonymous Coward | more than 3 years ago | (#33872782)

Technically there are 9 different games between 2 people

the outcome is different if Player A chooses Paper and Player B chooses Scissors than if Player A chooses Scissors and Player B chooses Paper

First professional player (4, Informative)

Chris Pimlott (16212) | more than 3 years ago | (#33872418)

The actual accomplishment, not specifically stated until the FOURTH paragraph of the New Scientist article with the same terrible headline, is that it's the first time a computer has beaten a professional human player; in this case, Ichiyo Shimizu, the female shogi champion.

Re:Nice headline (0)

Anonymous Coward | more than 3 years ago | (#33872434)

First time "a computer" has beaten "a human", eh?

I'm sure they mean: first time a computer has beaten a 1st dan (or whatever shogi ranks are called) grandmaster in an offical tournament setting...

Also, I don't think the theoretical number of games is very relevant. Paper-scissor-rocks has an infinite amount of possible games, ie 1 draw followed by a win, 2 draws ... inf draws. Much more relevant would be branching factor, difficulty of estimating positional strength, horizon problems, long term dependencies etc.

paper-scissor-rock with 2 players has 9 possible games. Far less, I'd say.

Re:Nice headline (0)

Anonymous Coward | more than 3 years ago | (#33872970)

Umm...paper rock scissors has 9 possible games. What kind of fuzzy math are you using?

Re:Nice headline (0)

Anonymous Coward | more than 3 years ago | (#33873528)

only if you define a game as not having a tie as a possible win. Otherwise, there's just 9 possible games.

When a computer program can... (2, Interesting)

Viol8 (599362) | more than 3 years ago | (#33871130)

... design and write another computer program to beat a human at chess or shogi - THEN i'll be worried.

Re:When a computer program can... (1)

ampathee (682788) | more than 3 years ago | (#33871226)

Well get worried then, because combining two programs is pretty easy.

Re:When a computer program can... (1)

nedlohs (1335013) | more than 3 years ago | (#33872740)

Try rereading, you missed the actual bit to be worried about...

Re:When a computer program can... (1)

rpresser (610529) | more than 3 years ago | (#33871594)

... design and build another human being which can design and write another computer program which can design and build another human being which can post on Slashdot - THEN I'll be worried.

Re:When a computer program can... (1)

michelcolman (1208008) | more than 3 years ago | (#33872262)

Actually, this already happened. Forget Darwin. Adams got it right.

Nonsense (1)

readin (838620) | more than 3 years ago | (#33871136)

Computer Defeats Human At Japanese Chess

Nonsense! A computer beat me at shogi decades ago.

Re:Nonsense (3, Funny)

2names (531755) | more than 3 years ago | (#33871200)

Computer Defeats Human At Japanese Chess

Human, my friend. Human.

Re:Nonsense (1)

bluefoxlucid (723572) | more than 3 years ago | (#33871546)

Are you implying parent is a furry?

Buddhists are geniuses (1)

digitaldc (879047) | more than 3 years ago | (#33871152)

FTA: "Akara is apparently a Buddhist term meaning 10^224"

I never knew those Buddhists were secretly genius mathematicians with specific words for abstract numbers.

Re:Buddhists are geniuses (2, Informative)

Intron (870560) | more than 3 years ago | (#33871294)

Not sure about large numbers, but they certainly had math geniuses
http://www.cut-the-knot.org/proofs/jap.shtml [cut-the-knot.org]

The first time... (1)

PseudonymousBraveguy (1857734) | more than 3 years ago | (#33871158)

<nitpick>He won the first time *against a skilled opponent*. The prototype has probably won against a lot of humans during the development process. I guess I would lose frequently against any random algorithm, as I don't even know the rules of shogi; winning agains some arbitrary human would not be anthing newsworthy.</nitpick>

Nonsense (-1, Redundant)

readin (838620) | more than 3 years ago | (#33871180)

A computer has beaten a human at shogi, otherwise known as Japanese chess, for the first time.

A computer beat me at shogi decades ago.

First move (2, Interesting)

Intron (870560) | more than 3 years ago | (#33871232)

Chess has a natural limit since the number of pieces monotonically decreases during the game. Shogi lets you drop (add) pieces that you capture, so a game can go on for a long time.

Pawn promotion? (1)

Paul Rose (771894) | more than 3 years ago | (#33871784)

>>monotonically decreases

http://en.wikipedia.org/wiki/Promotion_(chess) [wikipedia.org]

Re:Pawn promotion? (1)

Paul Rose (771894) | more than 3 years ago | (#33871810)

Nevermind -- should have thought about it for 10 seconds before posting...

Re:Pawn promotion? (1)

Xaositecte (897197) | more than 3 years ago | (#33872370)

Which, if the criteria is just "Number of pieces" still qualifies as monotonically decreasing.

Re:First move (1)

toastar (573882) | more than 3 years ago | (#33872772)

Chess has a natural limit since the number of pieces monotonically decreases during the game. Shogi lets you drop (add) pieces that you capture, so a game can go on for a long time.

Um no.... The thing that makes computers so good at chess is that it's a game of perfect information. Shogi the same it just has more permutations, specifically because of the drop rule. But there are still only a finite number of plays, Therefore using a lookup table is possible and I would argue even practical.

http://www.en.wikipedia.com/wiki/game_theory [wikipedia.com]

Shogi (2, Funny)

mark72005 (1233572) | more than 3 years ago | (#33871262)

I saw Shogi's show in Branson, that guy plays a mean fiddle.

Shogi - chess on steroids (1)

zill (1690130) | more than 3 years ago | (#33871360)

1. Kill enemy soldier
2. Turn him into a zombie with a necromancy spell
3. Train said zombie in air-borne assault tactics
4. HALO drop him behind enemy lines
5. ???
6. PROFIT!!!

AFAIK, Shogi is the only game I know that allows you to do this.

Re: chess on steroids (1, Interesting)

Anonymous Coward | more than 3 years ago | (#33871968)

Look up Bughouse.

Re: chess on steroids (1)

Chris Pimlott (16212) | more than 3 years ago | (#33872442)

Just about to say this. It's certainly plausible, though, that Bughouse was inspired by Shogi.

Re:Shogi - chess on steroids (1)

Colin Smith (2679) | more than 3 years ago | (#33872500)

chess is politics, not warfare .

Re:Shogi - chess on steroids (1)

john83 (923470) | more than 3 years ago | (#33873588)

Swap chess, a minor variant of chess, has a similar concept. Two pairs of players face off. On each team is one player with white pieces, and one with black pieces. Any piece they capture, they hand to their team mate, who can place it on the board at any time in lieu of a move.

Same Old Song And Dance (3, Insightful)

mnagy (854980) | more than 3 years ago | (#33871380)

Ugh. What's with perpetuating this nonsense? A computer did not beat the top ranked Western chess player. Rather, a group of people _reprogrammed the computer after each match_ to beat the top ranked Western chess player.

TFA, it is annoyingly vague on an important point: What is the rank of the Japanese player that lost?

And as others have pointed out, let see a computer take down a top ranked (10th Dan) player at Go. The best a machine has done (I think) is winning against a 5th Dan.

Re:Same Old Song And Dance (1)

shadowofwind (1209890) | more than 3 years ago | (#33871618)

And as others have pointed out, let see a computer take down a top ranked (10th Dan) player at Go. The best a machine has done (I think) is winning against a 5th Dan.

I think that would be a 5 dan amateur, not a 5 dan pro, which is a lot stronger. But to me that's still impressive enough that nothing would surprise me now.

Re:Same Old Song And Dance (1, Interesting)

Anonymous Coward | more than 3 years ago | (#33871826)

As long as the algorithm is rather simple and it's achieved just with more bruteforce (=more processing power), it's all rather pointless. Things get interesting, when computers analyze problems themselves, the rules, and come up with their own approach, learn and modify their strategies. This is what I'd call true AI.

Re:Same Old Song And Dance (1)

zacronos (937891) | more than 3 years ago | (#33872382)

As long as the algorithm is rather simple and it's achieved just with more bruteforce (=more processing power), it's all rather pointless. Things get interesting, when computers analyze problems themselves, the rules, and come up with their own approach, learn and modify their strategies. This is what I'd call true AI.

I think things get interesting well before you meet that definition of "true AI". I once wrote an evolutionary algorithm to develop a Reversi/Othello AI as a final project for a graduate class. It didn't analyze problems, and it didn't analyze the rules; following the rules was built into the AI framework I developed. The framework also didn't allow the AI to think more than a fixed number of moves in advance -- I eventually settled on 3, because I didn't want it to rely on brute force computation. With that said, it did develop its own approach, learn, and modify strategies (not within an AI, but evolutionarily within the population of AIs). And when I say it developed its own approach, I mean it surprised me with its technique. Once the best AIs in the population were at the point where they trounce me consistently, I took a look at the AI's program genome to reverse-engineer its strategy. It turns out that early game, it would put a high priority on letting me take pieces. It also prioritized controlling side and corner pieces (not surprising), and ensuring it maintained flexible play options. Then, at a certain point in the game, it would change its strategy, and use its flexible position to take back the ground it gave initially. I'm no expert at Reversi, but this struck me as a very interesting and unexpected (to me) strategy .

Re:Same Old Song And Dance (1)

Kjella (173770) | more than 3 years ago | (#33873690)

And when I say it developed its own approach, I mean it surprised me with its technique. Once the best AIs in the population were at the point where they trounce me consistently, I took a look at the AI's program genome to reverse-engineer its strategy. It turns out that early game, it would put a high priority on letting me take pieces. It also prioritized controlling side and corner pieces (not surprising), and ensuring it maintained flexible play options. Then, at a certain point in the game, it would change its strategy, and use its flexible position to take back the ground it gave initially. I'm no expert at Reversi, but this struck me as a very interesting and unexpected (to me) strategy.

Long story short, Reversi is dominated by the fact that there are 12 horribly bad moves (the three adjacent squares to every corner) and bad moves only tends to lead to an even more screwed position. "Ok I have to give the corner." "Ok he took the corner... now my choices are even worse." It would have been easier to see with a brute-forcing AI, but the general idea is to minimize your edge stones to limit the opponents' moves and force him into a line of play, not so much for your own flexibility. You don't mind grabbing stones if they're on the interior, they are possibilities. If you can force the opponent into such a bad sequence of moves with some air still on the table, you will win. This will absolutely devastate greedy players who grab as many as possible early.

The only reason you see a change in strategy is that it has been playing mirror images of itself, both players do their best to avoid taking edges and yielding corners so eventually as the board fills up you have to try a territory grab and avoid losing too much on the sides. One method to avoid losing too much on the edges is to force the opponent to fill the second to last, then fill the last position on the edge yourself. A short example with only the top two lines:

X-OOOO-X
-XOXXOX-

So you've yielded the corners, but if he takes the left open spot you take the right and so keep 5/8 pieces on the row. Also if you can plant one between the corner and his own side that is good, example:

XOXXXX--
-XOXXOO-

If he takes the corner, you fill the row and get the six in the center. Taking the edge is even worse as you get the line and the corner. All these things means the edge game will be more of a draw between good opponents, so you have to try grabbing the center at some point when there's so many pieces out you won't get forced into anything bad. It doesn't quite sound like your AI would become a champ any time soon but it's still impressive work though.

Re:Same Old Song And Dance (1)

zacronos (937891) | more than 3 years ago | (#33874120)

It doesn't quite sound like your AI would become a champ any time soon

Nor would I expect it to -- that was what evolved after about 4 days of evolution on a PC (at processor speeds from about 6 years ago). And of course it started with total random AIs -- ones that would lose to even a simple greedy algorithm. So some of that 4 days was spent just figuring out how to play well in the most rudimentary sense, much less developing anything resembling a strategy. I still have the code, because I always wanted to go back and tweak the mutation algorithm. As the code is, I feel the mutations are generally too large, and would only infrequently lead to a small change in expressed strategy; an ideal environment for mutation should have mutations which result in a mix of large and small expressed differences (large to avoid local extrema, and small to optimize within a solution region).

but it's still impressive work though.

Thank you. I find this sort of bottom-up AI incredibly fascinating. (It was a project for an Evolutionary Computation class, not an AI class.)

Re:Same Old Song And Dance (0)

Anonymous Coward | more than 3 years ago | (#33872016)

there are a couple of bots who have claimed rankings of around 2-3dan on kgs amongst amateurs on the server's own scale of ranks, but I dont think any real european or asian 5dan amateur would lose to those bots on 19x19 under normal conditions. Or very rarely.

Best do fare quite well in 9x9 now, with tons of computing power behind them. But even then I dont know if they manage to win against pros consistently, my guess would be 1/3rd of the time.

The bots so far have needed to have 9 handicap stones (typically the maximum given) to manage to wrestle a win against a professional human on 19x19.

Re:Same Old Song And Dance (-1, Troll)

Anonymous Coward | more than 3 years ago | (#33872054)

Also in chess, note that programmers are allowed to have an opening database. The opening is by far the most critical element of the game for chess. If the computers had to actually work out their openings instead of using ones already derived by humans over centuries, then computers have almost zero chance of beating even an average human player.

Re:Same Old Song And Dance (1, Insightful)

Anonymous Coward | more than 3 years ago | (#33873036)

Yeah, but human players do the same thing: they memorize specific openings rather than starting with a blank slate each time. Why wouldn't a computer program do that?

Re:Same Old Song And Dance (1)

SoVeryTired (967875) | more than 3 years ago | (#33872398)

Ugh. What's with perpetuating this nonsense? A computer did not beat the top ranked Western chess player. Rather, a group of people _reprogrammed the computer after each match_ to beat the top ranked Western chess player.

TFA, it is annoyingly vague on an important point: What is the rank of the Japanese player that lost?

And as others have pointed out, let see a computer take down a top ranked (10th Dan) player at Go. The best a machine has done (I think) is winning against a 5th Dan.

That's only on a 9x9 board. A competent low Kyu or Dan player could crush any computer on a 19x19 board.

For people who don't play go: the difference between 9x9 and 19x19 is a bit like the difference between ping-pong and tennis.

Re:Same Old Song And Dance (2, Informative)

SoVeryTired (967875) | more than 3 years ago | (#33872566)

Sorry for replying to my own post, but I guess I meant any non-supercomputer. Apparently they've managed to get clusters to play at amateur Dan level over the last couple of years.

For the record, the go ranking system works out as

30 Kyu ... 1 kyu 1 dan amateur ... 5 dan amateur european ... 9 dan amateur european

5 dan amateur european is about equal to 1 dan professional, due to inconsistencies in rankings between countries.

Re:Same Old Song And Dance (1)

Moridineas (213502) | more than 3 years ago | (#33874100)

I think that's exactly the GP's point.

Decades ago many people thought a computer could never beat a human at chess. Many millions of dollars have been spent on specialized hardware, computer-human tournaments, and AI research, we now have computers that can beat the best human players some of the time. Chess is admittedly, in turns of branching and possible moves, much simpler than Go. Far more able to be bruteforced, or to have lookup tables of millions of board positions.

But...

Isn't it obvious that the same thing will happen with Go? I don't know how long it will take, but I would bet a substantial amount of money that within my lifetime Go AIs will become, like Chess AIs, at the very least highly competitive at all levels. If you take current Go AIs and double their computing power, or quadruple, or 1000x, how much better would they be? Perhaps not hugely better, but between more AI research and exponentially increasing computing power and memory, I think the writing is on the wall.

Re:Same Old Song And Dance (4, Informative)

phantomfive (622387) | more than 3 years ago | (#33873120)

Are you referring to Deep Blue? While it is true that Deep Blue was relatively weak, and Kasparov lost because of psychological errors, he later played against Fritz [wikipedia.org] , which is a much more powerful chess engine, in a more fair match. Also we now have Rybka, which was created by a team of programming grandmasters, and has a rating several hundred points above the highest human (although no one has ever shelled out the cash necessary to get it to play against the world champion, it would likely win).

Forget Shogi - The real story is this (4, Interesting)

NYMeatball (1635689) | more than 3 years ago | (#33871926)

If you bother to read the article:

"IBM say they have improved artificial intelligence enough that Watson will be able to challenge Jeopardy champions, and they'll put their boast to the test soon, says The New York Times. "

Do you realize what this means? Ken Jennings versus robots. They could make an entire new show out of this and I'd watch it religiously.

Re:Forget Shogi - The real story is this (1)

ari_j (90255) | more than 3 years ago | (#33872352)

Do you realize what this means? Ken Jennings versus robots. They could make an entire new show out of this and I'd watch it religiously.

I'd watch it, too. Especially if the competition had nothing to do with trivia.

*Yawn* (1)

Stenchwarrior (1335051) | more than 3 years ago | (#33873022)

Wake me when we develop a computer that can give me an orgasm without me having to touch myself.

Not worried (1)

SuperRoboNinjaMonkey (949078) | more than 3 years ago | (#33873466)

According to TFA,

And IBM has now developed Watson, a computer designed to beat humans at the game show Jeopardy. Watson, says IBM, is "designed to rival the human mind's ability to understand the actual meaning behind words, distinguish between relevant and irrelevant content, and ultimately, demonstrate confidence to deliver precise final answers

There's to worry about until it learns to phrase those final answers in the form of a question.

Ein (0)

Anonymous Coward | more than 3 years ago | (#33873982)

Let me know when a computer-enhanced corgi wins.

Load More Comments
Slashdot Account

Need an Account?

Forgot your password?

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>
Create a Slashdot Account

Loading...