Computer Defeats Human At Japanese Chess

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

Comments

Best use of the word "only" ever.

[nedlohs]

pointless comment text

Re:Best use of the word "only" ever.

[severoon]

It is only a "bit" more complex than western chess; exactly one bit more complex. The exponent 123 can be stored in 7 bits. The exponent 224 requires 8, a full byte.

See what I did there? -puffs chest out proudly-

*yawn*. Call me when we lose at Go.

[DeafDumbBlind]

nt

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

[Tatarize]

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.

[Anonymous Coward]

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.

[bluefoxlucid]

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.

[TheCycoONE]

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)

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

[arose]

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.

[Amouth]

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.

[sexconker]

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.

[Anonymous Coward]

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.

[jgtg32a]

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.

[Moridineas]

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.

[TheCycoONE]

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.

[Raenex]

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.

[PiSkyHi]

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.

[interkin3tic]

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.

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

[PiSkyHi]

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

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

[PiSkyHi]

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.

[Blackbrain]

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?

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.

[Abcd1234]

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.

[mcneely.mike]

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

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

[purfledspruce]

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.

[jsac]

Computer programs have already beaten Go professionals at 7-stone handicap games. Mogo and Many Faces of Go have both done it for sure, and Zen is very competitive with both of them. If you go to http://gokgs.com/ and sign into the Computer Go room you'll see that Zen is ranked 3 dan and ManyFaces is ranked 2 dan, and they routinely win games off strong amateur humans. Both Zen and ManyFaces are single-box SMP programs, and the algorithm they use is a Monte Carlo algorithm so it should scale to hundreds of machines, while Mogo already runs on 600 processors...

So Go programs are getting there. Not as fast as chess, but they're still getting there.

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

[CarpetShark]

Spoken like someone who doesn't get Go at all.

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

[JohnBailey]

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.

Don't be so sure.. The most common Shogi is played on a 9x9 board with 40 pieces. True enough.. Just as the most common western chess is played with an 8x8 board and 32 pieces. That is far from the only Shogi though.

Maka-Dai-Dai Shogi has a 19x19 board, with 192 pieces.

There are plenty of variant rules that make for an even more interesting game, one of which has the piece take on the move of the piece in front of it. Others have specific rules about drops, others don't have drops..

There is a Shogi variant, Tai Shogi which has a 25X25 board, and 354 pieces. Something I've wanted to make for years, even if only as a display piece. And there may be bigger I haven't heard of.

Or at the other end of the scale, a 4X5 Micro Shogi board with 10 pieces.

http://trout.customer.netspace.net.au/ Old VB program that works great on Linux under WINE too. So you can try lots of different variants

Chess is a complex game, but there are a huge number of variants. Most are unknown outside the few who play them.

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

[Tetsujin]

Chess has actual complex rules.

It really doesn't.

I mean, think about it. Six different types of pieces, most of which only have one particular type of movement they execute. Pawns and kings are the only exception - with pawns having the two-rank initial advancement, en passant, and promotion, and kings being able to castle... The rules really aren't complex. It's just the depth of possible game combinations, and the strategies that can emerge as a result, that make it a complex game..

I haven't played Go a whole lot, just enough to know I'm really not very good at it. :)

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

[Anonymous Coward]

Why is this modded troll? That's exactly what the grandparent post says.

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

[Laxori666]

We don't know how our minds work well enough to say that we don't use brute force. Obviously, consciously, we're not thinking about it that way, but who knows what kind of processing the brain does to produce those conscious thoughts? When you get a knack of intuition like "ah that move would win" - is that just a brute force algorithm in the subconscious signalling termination with a result?

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

[Vintermann]

Yes. 3 dan on KGS is above what most of us can ever hope to reach at go - certainly, if someone doesn't know any go today, they wouldn't reach it until the programs have moved on.

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

[buswolley]

I played Shogi against a computer and lost in 1996. Sure I didn't know the rules. Still it happened.

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

[koreaman]

We are still much better at math than computers. Maybe you're confusing arithmetic with math.

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

[Guppy]

Go is a simple game.
Mind numbingly simple, in fact.

The rules that create and define the game are starkly simple. The "rules" that emerge and operate during the game are mind-boggling difficult. For instance, simply knowing when a game is functionally over can be very difficult for a beginner.

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

[Anonymous Coward]

how about 36x36 Shogi? Already exists:
http://en.wikipedia.org/wiki/Taikyoku_shogi

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

[jonelf]

You can be pretty sure we don't brute force in our brain the same way computers does. We tick way too slow.

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

[Anonymous Coward]

The complexity of Go is affected by the board size FAR MORE than chess-like games. If complexity (C) could be represented purely as a function of board size (B), then for Go it would be something like C = B^2 as opposed to chess, which would be more along the lines of C = log(B).

This is because chess-like games are limited by the moves that the various pieces can make, much more so than the actual board size. Think of it this way: how much complexity is added by increasing the board size to 100 x 100 when all you can move is a pawn?

On the other hand the complexity of Go scales up astronomically even with just a 1 x 1 increase in board size because at any given point in time, a stone can be placed anywhere. (And of course the game would become very simple when the board size is reduced)

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

[Anubis IV]

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

Than their regular 8x8 or 9x9 counterpart? Yes. Than Go? Not even close.

The fact that you can place a piece anywhere, as opposed to along rigidly-defined paths has quite a bit to do with the greater complexity of Go. Even if you bumped Chess or Shogi up to a 19x19 and made them somehow work in that space, Go would still be much more complex to solve due to the fact that there would be vastly more possible moves from any given state.

And they are ALL brute force exercises. That's all they are, really. What makes Go interesting is that it's a much much harder brute force exercise than the others, and not just because of the larger board size (though that is certainly a major contributing factor). That you find it boring is just evidence of the fact that you haven't considered it enough.

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

[matt007]

Your comment is misleading. While Go rules are quite simple, mastering the game is not easier than mastering chess at all.

its absolutely not "just a large game"

Try to play good players at www.gokgs.com

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

[AK Marc]

The argument is that the computer didn't beat you, you beat yourself while playing a computer.

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

[Anonymous Coward]

Don't wait - find a tournament near you soon and sign up so you can go to it. It's fun, and you get serious games under your belt with people whose styles you don't know (if your only face-to-face games so far have been among friends, this is a neat change.)

You can play online, but nothing beats the cold stones in your hand sitting across the board from a well-matched opponent!

If you're in the D.C. area (or driving distance) the next NOVA tournament (the Pumpkin Classic) is at George Mason University in Arlington on the 30th. They like people to pre-register on their website (it's linked to from the tournament list on http://usgo.org )

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

[sadboyzz]

What a load of rubbish. How the hell did this get modded insightful?

Go only wins through brute force.

Go doesn't "win" anything. You play Go to win against someone else. In case you didn't know, Go is a game, with extremely simple rules, played between two players. As it happens, Go also pre-dates Chess by about 1000 years.

Sarcasm aside, to somehow suggest there is a "competition" between Go and Chess to the more "complex" is just absurd. I'm pretty sure our ancestors did not have this in mind when they invented Go and Chess.

go is 19x19 shogi is 9x9 chess is 8x8

Simply comparing board sizes between different games is pretty meaningless. The branching factor is governed as much by the board size as the actual rules of the game.

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

And it would be vastly harder for the human as well. Assuming you could somehow meaningfully extend the complexed rules of Chess (as compared to rules of Go) to a 19x19 board, it could well be that the resulting mess would be so complex that no humans would be interested in playing. If it's not interesting to humans, than there's no point in writing computer programs to solve it.

Computers playing Go on 9x9 have beaten 9th dan.

In July of 2010, and the human isn't even near top 10 in the world. Also, 9x9 Go isn't Go, it's just that, 9x9 Go. These are two vastly different games. As an analogy, 9x9 Go is like fighting a single battle, where most of decisions are tactical. The normal Go is like fighting a war, with many battles going on at the same time. There are both strategical and tactical decisions to make.

And if it was 8x8 it would be even easier.

And if it was 7x7 Chess with no rooks Deep Blue would have crushed Kasparov.

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

What an arrogant statement coming from someone who apparently knows nothing about the game at all.

There has been considerably more research into Chess AI than Go AI, which may be one important contributing factor to the current relative weak status of Go AI. This may change in the coming years as more and more attention are being directed towards tackling Go. However, what we do know at this point is that writing competent AI for Go is very different from that of Chess, both in terms of the search strategy and the evaluation function, and very little of the advancements in Chess AI can be applied directly to Go. To me at least, the fact that Go is such a challenging game made out of such simple rules, is quite fascinating, and certainly qualifies as "neat".

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

[Anonymous Coward]

Would you insist on using brute force to solve x=1? Yeah, you could check every possible integer for equality with 1, just to make sure, but a deeper understanding of the problem dramatically reduces the necessary time, while providing as correct answer as the "lazy way".

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

[Anonymous Coward]

That's true, the brain's clock works in like, Hz's. However, it's *massively* parallel, and has a feature of gradually reprogramming its hardware to better fit the task - these features give it an overwhelming edge over any existing computer (in a selection of tasks, naturally).

Still I doubt that something as smart as our brain would be using something as dumb as BF.

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

[Cow Jones]

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

To illustrate your point...
Sufficiently motivated players could still win in such a setting. Or so I hear.

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

[loufoque]

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

Way to waste one's life.

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

[FiloEleven]

Exactly. Go has more in common with Conway's Game of Life than it does with chess.

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

[Anonymous Coward]

Another comment that shows no understanding in current AI and Go.

In games like Chess and Shogi piece evaluation is relatively easy as each piece has its specific movement (hence power).
In Go you do not have such thing. Position evaluation is extremely tough. This turn a position may be useless, but next turn it may immediately become critical.

This has nothing to do with board size. It has to do with the nature of the game. 9x9 Go is easy to excel for computer because there is typically no position evaluation (right away in the game you are in combat).
13 x 13 Go, computer still sucks.

I have no doubt that one day we have super computer that can brute force the Go game, but it won't happen any time soon. If we can use heuristics in computer so we don't completely bruce force for computer to be decent at Go, we have a major break through in AI.

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

[arose]

Sure they can.

Oh, ok then let's just make a bigger board and...

The rules just need extending.

Oh. So yeah, they don't scale but similar games can be formulated. I wasn't disputing this.

That's nothing...

[msauve]

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

Re:That's nothing...

[i-c-electrons]

Hell a computer could probably beat me at connect four.

Re:That's nothing...

[Anonymous Coward]

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

Re:That's nothing...

[Anonymous Coward]

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

Re:That's nothing...

[wagnerrp]

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

Re:That's nothing...

[veganboyjosh]

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

Re:That's nothing...

[Yaotzin]

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

Unless you cheat.

Re:That's nothing...

[shentino]

Kobayashi maru anyone?

Re:That's nothing...

[Quato]

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

Re:That's nothing...

[MikeyO]

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

Re:That's nothing...

[masmullin]

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

Re:That's nothing...

[wagnerrp]

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

[Tetsujin]

No thank you, I already ate.

Nice headline

[mrvan]

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

[jwietelmann]

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

[The MAZZTer]

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

[Speare]

"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

[black_lbi]

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

[bluefoxlucid]

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

[Kjella]

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

Re:Nice headline

[Anonymous Coward]

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

[Anonymous Coward]

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

[srussia]

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

+11 Funny

Re:Nice headline

[The_mad_linguist]

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

Re:Nice headline

[fusiongyro]

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

[SlimXero]

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

[Anonymous Coward]

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

[PiSkyHi]

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

Re:Nice headline

[bluefoxlucid]

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

[Anonymous Coward]

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

Re:Nice headline

[fusiongyro]

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

[SlimXero]

Agreed.

Re:Nice headline

[Anonymous Coward]

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

Re:Nice headline

[Anonymous Coward]

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

[john83]

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

[Anonymous Coward]

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

Re:Nice headline

[Chris Mattern]

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

[Anonymous Coward]

"The Mainichi Daily News reports that TOP WOMEN'S shogi player Ichiyo Shimizu took part in a match staged at the University of Tokyo..." Let's see it beat a man!

Re:Nice headline

[Tetsujin]

"The Mainichi Daily News reports that TOP WOMEN'S shogi player Ichiyo Shimizu took part in a match staged at the University of Tokyo..." Let's see it beat a man!

Yes, that'll be a different challenge entirely. There's a whole set of valid moves in Shogi that involve shifting game pieces around with one's penis - in informal matches women will sometimes use their boobs instead, but no such equivalent has yet been accepted as part of a professional tournament.

Re:Nice headline

[Anonymous Coward]

This is no big deal. My Atari 2600 could easily beat me at chess, which is more of an indictment of my chess skills than a reflection of the computing power of my Atari.

Sadly, I can still here the "plunk" sound that game made when it finally (after several hours of thinking) made it's move.

Re:Nice headline

[Vintermann]

Black belt in calligraphy, that would be something to have.

Re:Nice headline

[Anonymous Coward]

Hard to read, though, being black on black.

Re:Nice headline

[Vintermann]

Checkers, aka Anglo-American Draughts, is solved. The Draughts played in continental Europe is not solved.

Re:Nice headline

[ultranova]

I mean, a chess computer has no concept of a plan,

That really depends on the program, now doesn't it? I'd be very surprised if the programs didn't cache some of their computations to immediately generate the countermove if the opponent moves as expected, and use the reminder of their turn to further simulate future moves. After all, it's an obvious optimization, and that's what plans are - now I do this, then he does that, then I respond with this move, and so on.

and even Kasparov or Topalov or whoever can only calculate a handful of positions a second.

I wouldn't be too sure of that. A brain is basically a massively parallel computer, simulating the likely events in your immediate vicinity all the time - and in the case of humans, using abstract thought to simulate far away places as well. It's likely that there are hundreds, if not thousands, of plans that are considered subconsciously but rejected because of some obvious flaw, freeing the conscious mind to only examine the most promising ones in detail.

Re:Nice headline

[Anonymous Coward]

You can just be +5 Funny!

Re:Nice headline

[john83]

I mean, a chess computer has no concept of a plan,

That really depends on the program, now doesn't it? I'd be very surprised if the programs didn't cache some of their computations to immediately generate the countermove if the opponent moves as expected, and use the reminder of their turn to further simulate future moves. After all, it's an obvious optimization, and that's what plans are - now I do this, then he does that, then I respond with this move, and so on.

That's not what I'm talking about. I am a club player of moderate ability - I would have no hope against a modern chess programme like Fritz on a basic PC (even on that hardware, it's at least comparable to a top-50 player). However, I can look at a position and decide that to win, I need to, say, get my knight to a particular outpost, and drive home a passed pawn and promote it. A computer doesn't think like this.

and even Kasparov or Topalov or whoever can only calculate a handful of positions a second.

I wouldn't be too sure of that. A brain is basically a massively parallel computer, simulating the likely events in your immediate vicinity all the time - and in the case of humans, using abstract thought to simulate far away places as well. It's likely that there are hundreds, if not thousands, of plans that are considered subconsciously but rejected because of some obvious flaw, freeing the conscious mind to only examine the most promising ones in detail.

I was talking about brute force computation, which has been measured. I forget the precise result, but I think you're talking something like 3 or 5 positions a second. Those players, and even I derive most of our ability from pattern recognition, while the computer is powerful because it performs an (optimised) search on a tree of possible continuations. There's a fundamental difference in how humans and computers play chess.

Re:Nice headline

[Anonymous Coward]

if the same exact board layout shows up 3 times, its a stalemate.

Re:Nice headline

[Anonymous Coward]

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.

Rock paper scissors is NOT an infinite game. If the game ends in a tie, then you play another game.

As for chess, it actually CAN be infinite within a single game (for example we can each move a rook forward one square and then return it the next turn, voila a never-ending game). There is actually a rule in official tournaments (the 50-move rule) to prevent people from abusing it.
When we speak of the theoretical number of games, that is calculated (in a nutshell) by considering all possible combinations of piece positions, and for each combination how many moves are possible to make from that position.

Re:Nice headline

[binkzz]

Paper-scissor-rocks has an infinite amount of possible games, ie 1 draw followed by a win, 2 draws ... inf draws.

With that logic, any game has an infinite amount of possible outcomes. What OP meant is the number of possible ways an individual game can go, not the possible outcome of infinite games.

The number of possible ways a single RPS game can go is 9 (or 10^0,954): RR - RP - RS - PR - PP - PS - SR - SP - SS.

Re:Nice headline

[Dabido]

I must agree. My computer can not only beat me at Shogi, but also Chinese Chess and Western Chess and has been doing so for a long time.

Re:Nice headline

[Anonymous Coward]

Most schools go to 9-dan (kyuudan) and have an honorary 10-dan or 11-dan

I can picture it: "yeah, well MY school goes to eleven!"

Re:Nice headline

[RivenAleem]

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.

Another example of how Spinal Tap had the right of it. Very insightful for a Western Band.

Re:Nice headline

[FiloEleven]

A brain is basically a massively parallel computer

No, it isn't.

When a computer program can...

[Viol8]

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

[ampathee]

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

Re:When a computer program can...

[rpresser]

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

[michelcolman]

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

Re:When a computer program can...

[nedlohs]

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

Re:When a computer program can...

[Tetsujin]

... write a critical part of its message somewhere other than the message body, so that people misread the message - THEN I'll be... rather unsurprised, really. It's easy to do. The question is, why would you do it?

Nonsense

[readin]

Computer Defeats Human At Japanese Chess

Nonsense! A computer beat me at shogi decades ago.

Re:Nonsense

[2names]

Computer Defeats Human At Japanese Chess

Human, my friend. Human.

Re:Nonsense

[bluefoxlucid]

Are you implying parent is a furry?

Re:Nonsense

[Anonymous Coward]

No, he's got green blood.

Buddhists are geniuses

[digitaldc]

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

[Intron]

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

Re:Buddhists are geniuses

[CarpetShark]

Since they once represented the intellectual elite of the world's first great civilisations, that alone should tell you that they might have. If you had studied buddhist teachings at all, you might have discovered that, far from being fanciful accounts of Noahs and arks, much of their teachings are cold hard logic (including a lot of math), which is easily comparable to "modern" western science.

Re:Buddhists are geniuses

[ELitwin]

I thought that was odd when I read it too. When I googled "Akara and Buddhist", I don't see any references to support that piece of information (other than a link to TFA).

Re:Buddhists are geniuses

[pookemon]

Yeah - I tried the same thing. Apparently Akara is a "Black Eyed Pea" dish.

Of course I did so while thinking to myself that Buddhists probably don't spend a great deal of time on the Internet (referring to buddhist Monks rather than your average run-of-the-mill buddhist). But even so you'd think that someone would have documented the mathematical knowledge of Buddhist math geniuses...

The first time...

[PseudonymousBraveguy]

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.

Nonsense

[readin]

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

[Intron]

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.

Re:First move

[toastar]

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

Re:First move

[Vintermann]

Nope, your lookup table would probably have to be bigger than the universe. Computers may win at Shogi, but not that way.

Shogi

[mark72005]

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

Shogi - chess on steroids

[zill]

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:Shogi - chess on steroids

[Colin Smith]

chess is politics, not warfare .

Re:Shogi - chess on steroids

[john83]

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.

Re:Shogi - chess on steroids

[Anonymous Coward]

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

So, essentially, it's possible that you aren't aware of the other games you know that allow you to do this as well.

Re:Shogi - chess on steroids

[Vintermann]

That's Bughouse. It's a very chaotic game because of timing issues.

Same Old Song And Dance

[__aaasvk1266]

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

[shadowofwind]

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

[Anonymous Coward]

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

[Anonymous Coward]

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

[Anonymous Coward]

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

[zacronos]

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

[SoVeryTired]

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

[SoVeryTired]

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

[Anonymous Coward]

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

[phantomfive]

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

Re:Same Old Song And Dance

[Kjella]

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

[Moridineas]

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

[zacronos]

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

[Vintermann]

Yes, a computer did beat the top ranked Western Chess player. At worst, deep blue did not beat the top ranked chess player.

Programs running on a regular notebook computer can these days beat grandmasters even giving pawn odds.

Re:Same Old Song And Dance

[Vintermann]

It turns out that early game, it would put a high priority on letting me take pieces.

You sound surprised, but this is very basic Othello strategy. You don't seek "material advantage" except when you're confident you can get a wipeout win.

Re:Same Old Song And Dance

[Vintermann]

You're still underestimating computers. Look up Zen19 on KGS - it runs on an ordinary SMP system, hardly a supercomputer. It's stable at 3 dan.

Re:Same Old Song And Dance

[__aaasvk1266]

Yes, I was talking about Deep Blue, and every other rigged Chip vs. Human outing.

I have no problems if we are talking about a one-on-one match: Human sits at board, Chip "sits" at board, they go at it, and a couple of days later, again, etc.

That means Chip does not get worked over, tweaked, re-coded, etc. over the days off between games. If Chip can't handle the play on his own, then Chip isn't good enough.

Re:Same Old Song And Dance

[Anonymous Coward]

It's true, but it's also deeply depressing that none of it indicates almost any advance in AI whatsoever. I guess a few small things have been learned, but certainly no breakthroughs remotely on a par with the headlines generated from "Computer beats grandmaster at *insert difficult game here*". Rather it's almost entirely a tribute to electronic engineering.

Re:Same Old Song And Dance

[Anonymous Coward]

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

Uh, no.

6 dan amateur European CAN BE equivalent to 1 dan pro, but as 6d is the highest European amateur rank there's a wide variance there, and not all 6d amateurs are pro strength. Nor (I daresay) many.

I'm a 3 dan American, but I've played a few European amateurs who came to the U.S. Go Congress, and the amount of pushdown you would get in the European ranks if all 6 dan players were equivalent to pro 1d would mean that the very nice German 4d I played in 2005 (for instance) should have been able to give me 3 handicap stones. No way.

For what it's worth, the highest American amateur rank is 7 dan, and most of our 7d players are not professional strength either. Jie Li is a notable exception, as well as possibly Andy Liu.

Other strong players are very close, but lacking that certain something... perhaps 1/2 stone difference. But it's enough. There is a very palpable difference between the strength of a pro and the strength of (the vast majority of) amateurs. Half of a stone is certainly enough to be felt at that level of play.

Re:Same Old Song And Dance

[Moridineas]

I don't know much about AI, I took one course and that was it. The professor had a good pedigree and spotless credentials. The impression I got from him was exactly yours--AI IS depressing, and little progress of the type imagined in the 60s/70s has really occurred. Not to say there's been no advancement, just perhaps that a lot of the early optimism has proven to be unfounded and burned off.

Re:Same Old Song And Dance

[sadboyzz]

The best a machine has done (I think) is winning against a 5th Dan.

... with a 7 stone handicap.(http://en.wikipedia.org/wiki/Computer_Go#Recent_results) In chess terms, that's like winning an opponent who has no Knights.

Re:Same Old Song And Dance

[Anonymous Coward]

There is also "Stockfish" now which is free software and stronger than Rybka3 (but weaker than Rybka4).

http://www.stockfishchess.com/ for the engine
http://www.husvankempen.de/nunn/40_40%20Rating%20List/40_40%20BestVersion/rangliste.html for the rating

Re:Same Old Song And Dance

[Anonymous Coward]

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

Deep Blue wasn't just weak, it was somewhat of a con operation. It was presented as a computer AI which could play chess- instead it was a fairly simplistic routine which took a specially crafted dataset and applied it statistically. This dataset was hand built by the programmers around Kasparov's play style; they changed the weighting of various moves, values of pieces, and adjusted probabilities based on Kasparov's history and then fed that custom data to the routine. I would have been impressed if it was a learning AI which had to build and weight the dataset on its own (even if it was fed Kasparov's past history it still should have had to make its own analysis), but still would not have considered it to be better than any human until it could be enrolled in the starting tier of a world tourney and worked its way through multiple opponents and still won (without ANY alteration of its programming or datasets by the programmers between matches).
Kasparov could have easily beat the IBM system, but he made the mistake of trying to play against the computer routine as if it was a real opponent. In all reality he was in effect playing against himself (or rather, against his own strategy).

Re:Same Old Song And Dance

[eulernet]

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

Hum no, Rybka is written by only one programmer (Vasik Rajlich) and he's only an International Master.
His program is heavily based upon the open-source chess engine Fruit.
It's true that the GM Larry Kaufman suggested some ideas, but he's not programming Rybka.

Also, their ELO is absolutely useless, since these ratings were measured with games between programs, and not by confronting them to human players.
It reminds me the case of the prisoner who played against his mates and got a massive ELO rating from the US chess federation, but he was just abusing the system.

BTW, you can also easily find an excellent open-source chess program stronger than Rybka: Ippolit.
There are several variants, named Ivanhoe, Robbolito and Houdini.

Check these free programs, their strength is very impressive, and they are used by chess players for game analysis.
And no, it has been confirmed that they are not decompiled versions of Rybka, which is the argument used by Vasik to block these programs from the official chess programs ratings.

Pawn promotion?

[Paul Rose]

>>monotonically decreases

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

Re:Pawn promotion?

[Paul Rose]

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

Re:Pawn promotion?

[Xaositecte]

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

Re:Pawn promotion?

[Anonymous Coward]

You ain't no chess nerd. Pawns aren't pieces, they tell us -- pieces are only the higher-ranking, uhm, pieces. Since they thus applied the word pieces, they use "men" to refer to what any sane person would call a piece, thereby invoking gratuitous gender drama (because they said men) and lulz (because they say the queen is a man).

So promoting a pawn to anything increases the "piece" (chess nerd definition) count by 1.

Forget Shogi - The real story is this

[NYMeatball]

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

[ari_j]

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.

Re: chess on steroids

[Anonymous Coward]

Look up Bughouse.

First professional player

[Chris Pimlott]

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:First professional player

[Anonymous Coward]

female

Re: chess on steroids

[Chris Pimlott]

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

*Yawn*

[Stenchwarrior]

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

Re:*Yawn*

[Anonymous Coward]

Fleshlight + Lego MindStorms.

Re:*Yawn*

[roc97007]

I think I saw that on The Big Bang Theory. As I recall, it didn't end well.

Not worried

[SuperRoboNinjaMonkey]

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.

Re:Not worried

[Tetsujin]

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.

s = "What is " + s + "?";

Ein

[Anonymous Coward]

Let me know when a computer-enhanced corgi wins.

Arimaa : the next 8x8 programing challenge

[advid.net]

See Arimaa , a new game with a board and set similar to Chess *but* with specific rules made to be difficult for a computer to play, and easy for a child.

How many options do you have when it's your turn to play with chess ? The average branching factor in a game of Chess is about 35, whereas in Arimaa it is about 17281 !
This is why a computer which can search to a depth of eight turns for each player in chess, can only search about three turns deep for each player in Arimaa...

This game is the new challenge for IA, easy for a child, difficult for a computer. A average human player wins against best programs.

Re:Arimaa : the next 8x8 programing challenge

[Raenex]

This game is the new challenge for IA, easy for a child, difficult for a computer.

I looked at Arimaa a long time ago and keep tabs on it's progress occasionally. It's still very much a niche game after all these years. The two biggest problems with it:

• I don't find it much fun. I can't be in the minority considering the number of people who try out Arimaa and don't stick with it.
• There was never a need for a new, artificial challenge. Go was already the next challenge, recognized by the AI community for decades. It's a mainstream game that's already hard for computers.

A average human player wins against best programs.

Actually, the top programs these days are already at expert level, but still far behind the master level players.

Most interesting phrase

[Anonymous Coward]

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

Buddhists have a term for 10^224?

Re:Most interesting phrase

[Tetsujin]

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

Buddhists have a term for 10^224?

"apparently". :)

Search tree reductions

[Tetsujin]

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

But to avoid needless computational overhead, we can consider games where player A chooses X and player B chooses Y to be equivalent to games where player A chooses Y and player B chooses X - it's the same combination of states... So if I choose paper and you choose scissors, we can just go ahead and call that a win for me.

Is this canon?

[Anonymous Coward]

Jane plays Shogi with pequeninos, now?

Western Chess?

[metlin]

Really! I'd thought that chess originated in India and spread to Persia and the Middle East, where it evolved. But hey... whatever.

Terrible - This heading has to be inaccurate

[Anonymous Coward]

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

I would insert the word "expert" before human. Because I am pretty sure that just about any computer program could beat me at shogi, since I have no idea how to play. Just printing "I won. You loose." would convince me to forfeit thereby losing the game.

Need a good tori shogi program

[Anonymous Coward]

Dude's about to lose a rook in that picture.

I wish someone would write a good algorithm for tori shogi, which is played on a 7x7 board. I routinely beat my computer at tori, but it's well known that the program is weak.

"Friendly competition"???

[toby]

She obviously doesn't realise how cold, calculating and ruthless humans can be...

Why don't you do it?

[toby]

Nice programming exercise.