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 Cracks 5x5 Go

timothy posted more than 9 years ago | from the figure-go dept.

Puzzle Games (Games) 442

gustgr writes "The American Go Association is reporting that Go for the 5x5 board has been solved by the computer program MIGOS, reports the program's creator, Erik Van Der Werk, a professor at the University of Maastricht in Holland. At about a quarter of the full-board version, 5x5 go is miniscule, similar in scale to "solving" 2X2 chess. The fact that a programmer would even consider this a noteworthy challenge is itself a remarkable testament to the game's complexity. Van Der Werk's approach is described in detail in an article at the Netherlands Organization for Scientific Research (NOSR)."

cancel ×

442 comments

October 2002 (5, Funny)

fembots (753724) | more than 9 years ago | (#11740416)

From the friendly article:

Subject: computer-go: 5x5 Go is solved
Date: Sun, 20 Oct 2002 15:27:04 -0100
From: Erik van der Werf
To: COMPUTER GO MAILING LIST

The fact that an editor would even consider this a newsworthy article is itself a remarkable testament to the site's simplicity.

Funny how the stock market crashed [greekshares.com] the day before 5X5 Go is solved.

Oh noes! (-1, Offtopic)

Anonymous Coward | more than 9 years ago | (#11740427)

Date: Sun, 20 Oct 2002

We've travelled back in time!

I've got to warn people about Hitler!

Re:Oh noes! (-1, Offtopic)

Anonymous Coward | more than 9 years ago | (#11740455)

I can see it now -

you: You've got to listen to me - there's this guy called Hitler, he's...
Public: Dead.
You: ...
You: Well, in 2005, he's _still_ dead!
Public: ...
You: what, why is everyone looking at me?

Re:Oh noes! (1)

Abreu (173023) | more than 9 years ago | (#11740611)

Hilarious! Too bad you posted AC

Re:October 2002 (4, Informative)

Anonymous Coward | more than 9 years ago | (#11740434)

The doctoral thesis was defended on 27 January 2005

Maybe the results came out just now.

Re:October 2002 (5, Funny)

Xzzy (111297) | more than 9 years ago | (#11740503)

Sometimes I wonder if there's some secret society of geeks that scour geekly websites for neat stuff, who's only flaw is being several years old.

They make a contest of it.. whoever gets an old geek story posted on slashdot, wins the round.

It's such an obvious sport to invent, considering all the heckling slashdot editors recieve. I'm not quite prepared to accept that so many old stories get submitted out of ignorance.

Someone, somewhere, is toasting themselves to a beer right about now.

Re:October 2002 (1)

torpor (458) | more than 9 years ago | (#11740515)

Funny how the stock market crashed the day [19 oct 1987] before 5X5 Go is solved [20 oct 2002].


"Time Fractally" in a Push [futurismic.com] kind of way ... ?

Re:October 2002 (1, Informative)

Anonymous Coward | more than 9 years ago | (#11740602)

Before trolling read the full fucking article [www.nwo.nl]

And as one had already stated, the thesis was defended just a few days ago...

Re:October 2002 (0)

Anonymous Coward | more than 9 years ago | (#11740726)

Well, the "editor" is Timmy Piquepaille, so we should lower our expectations of quality.

Some slashdot lore. (5, Insightful)

Eunuch (844280) | more than 9 years ago | (#11740418)

Slashdot has a longstanding joke that with every chess article, some wide-eyed enthusiast will blurt out a quick description of Go like he's first to discover it in all the West. Speed is essential! There may be some pasty white guy who does not know the wonder that is Go.

I fully expect someone to breathlessly explain the Great Goodness that is Chess.

Chess is fun. Go is fun. People have generally heard of both. That is all.

Re:Some slashdot lore. (4, Interesting)

Ayaress (662020) | more than 9 years ago | (#11740447)

People on Slashdot probably fall into a different demographic, but I've found that people generally haven't heard of Go. They'll recognize a chess set by site, but they see Go and if you're lucky they assume Reversi or Othello. I was in the student lounge with a friend who was teaching me how to play Go, and somebody asked what game we were playing. When we told him, his reply was, "Go? I thought that was a card game."

Re:Some slashdot lore. (-1, Flamebait)

Anonymous Coward | more than 9 years ago | (#11740483)

Yeah, people are so rude and stupid and uncultured for not knowing what games you play. What idiots.

Re:Some slashdot lore. (2, Informative)

usefool (798755) | more than 9 years ago | (#11740487)

When we told him, his reply was, "Go? I thought that was a card game."

I had a similar experience except that guy said "Go? I thought that was the monkey from outerspace."

Re:Some slashdot lore. (0)

St. Arbirix (218306) | more than 9 years ago | (#11740600)

Obviously I'm not posting enough.

The sig says it all.

Re:Some slashdot lore. (3, Insightful)

Anonymous Coward | more than 9 years ago | (#11740472)

I find it most amusing that they describe a 5x5 Go board as a quarter of the size of a full-sized go board... a full size go board is 20x20, so 5x5 is a sixteenth-sized go board. It's only a quarter sized if you only measure linearally, rather than spacially.

Re:Some slashdot lore. (5, Informative)

PetWolverine (638111) | more than 9 years ago | (#11740553)

A full-size Go board is 19x19, but you're right in your main point.

Re:Some slashdot lore. (1)

IWannaBeAnAC (653701) | more than 9 years ago | (#11740678)

But for practical purposes, its exponentially smaller ...

Re:Some slashdot lore. (5, Funny)

Deadstick (535032) | more than 9 years ago | (#11740737)

It's only a quarter sized if you only measure linearally, rather than spacially.

Arm yourself against spelling flames first, Grasshopper. Only then will your math flames stand up to the foe.

rj

2x2 chess? (0)

Anonymous Coward | more than 9 years ago | (#11740429)

What is that? King/Queen * 2 on a 2x2 board? Double checkmate every time.

Re:2x2 chess? (2, Interesting)

Anonymous Coward | more than 9 years ago | (#11740568)

There is a neat leaning variant called Quic k Chess [chessvariants.org] .

That means (0)

Anonymous Coward | more than 9 years ago | (#11740430)

That chess is much more complex, right?

GREAT SCOTT! (3, Funny)

agildehaus (112245) | more than 9 years ago | (#11740432)

Marty, this story once mattered, back in 2002, when it happened.

What the hell? (0, Redundant)

Anonymous Coward | more than 9 years ago | (#11740444)

If someone bothered to read the linked article you would find that it was solved in October 2002. Just a tad out of date, wouldn't you say?

You would expect 20x20 to be solved by now...

Re:What the hell? (4, Funny)

mikael (484) | more than 9 years ago | (#11740544)

I heard rumours that there was a solution for "Tic-Tac-Toe" very close to being announced. The only hold up is finding a large enough
distributed network to explore all paths in real-time.

And the solution is....... (0)

Anonymous Coward | more than 9 years ago | (#11740661)

here [sciflicks.com] .

How is this surprising? (2, Interesting)

idono (858850) | more than 9 years ago | (#11740446)

If computers can beat chess grandmasters and similar feats, how is this anything special?

Re:How is this surprising? (1)

lcrypt (754134) | more than 9 years ago | (#11740468)

The combinations of possible Go games is much bigger.

Re:How is this surprising? (2, Interesting)

Rakishi (759894) | more than 9 years ago | (#11740517)

Because computers can't beat 10 year olds in Go. It's kinda amusing really.

Re:How is this surprising? (5, Interesting)

Haydn Fenton (752330) | more than 9 years ago | (#11740524)

Because Go is incalcuably more complex to design a computer program for, there are only two pieces, but they can go anywhere at any time (Ok, not *anywhere at any time* but pretty much), and the number of combinations there are to a simple move is much more difficult than the moves are in chess.
Or so I would assume, I've never actually tried to make a program for either, but it would appear so to anyone who has played more than a few games of each.

Re:How is this surprising? (5, Informative)

legLess (127550) | more than 9 years ago | (#11740549)

If computers can beat chess grandmasters and similar feats, how is this anything special?
It's special for two reasons. For one thing, even though computer programs can beat most humans, chess itself has not been solved. That's a very different proposition.

For another thing, go is spectacularly more complex than chess. The very best go programs are competition only for weak amateurs. There's an archived NYT article [ishipress.com] that summarizes the problems reasonably well.

Although the standard go board is 19x19 intersections, the game scales, unlike chess. Things you learn on a small board are sometimes applicable to larger ones. A 5x5 is usually not interesting for human play; most consider 9x9 the minimum size for a worthwhile game. This means that a computer has been programmed to force a guaranteed win at a smaller size, and hopefully paves the way for further development and understanding.

Re:How is this surprising? (3, Informative)

STrinity (723872) | more than 9 years ago | (#11740586)

In chess, there are approximately 71,000 possible board possitions after four moves, compared to over 16.7 billion in full board Go. Even on a simplified 5x5 board, there are more than 300,000 combos after four moves.

Re:How is this surprising? (0)

St. Arbirix (218306) | more than 9 years ago | (#11740705)

Because computers don't have two sides of their brains to use. Chess only uses the left side of your brain, go uses both.

If this were comparable computers would be critiquing art and robots would never run into walls.

2002? (4, Funny)

porcupine8 (816071) | more than 9 years ago | (#11740448)

What is this, Classic Slashdot? Next do we get a story on the impending end of the dot-com bubble?

Re:2002? (1)

Tablizer (95088) | more than 9 years ago | (#11740604)

You mean my petfood.com stock is going to be worthless? I sunk my life savings into that. Go OS/2!

What, are you crazy!? (2, Funny)

ucblockhead (63650) | more than 9 years ago | (#11740635)

It's not going to end! It's the new economy, dude! (I can't wait until Salon.com goes public so I can buy a new house!)

The future called (2, Funny)

Anonymous Coward | more than 9 years ago | (#11740450)

It said 6x6 go is solved.

2X2 Chess? (3, Insightful)

tritone (189506) | more than 9 years ago | (#11740456)

Go scales downwards in a logical way, but 2X2 chess is either absurd or trivial depending on what pieces you decide to place there. The "equivalent" chess problem is probably more along the lines of 4x4 or 5x5.

Re:2X2 Chess? (5, Funny)

nacturation (646836) | more than 9 years ago | (#11740557)

But what if it's 2x2 chess with all knights?

Re:2X2 Chess? (1)

tritone (189506) | more than 9 years ago | (#11740603)

That would be one of the absurd possibilities!

Re:2X2 Chess? (5, Insightful)

_Pablo (126574) | more than 9 years ago | (#11740572)

In my opinion, for it to be chess, it would have to have two kings otherwise no one could win. Therefore 2x2 chess would start with checkmate and is absurd.

Re:2X2 Chess? (0)

Anonymous Coward | more than 9 years ago | (#11740626)

That 2x2 Chess is trivial is the point. If you scale the chess board down by a factor of four on each side you get a trivial game. If you scale the go board down by roughly a factor of four on each side, you get a game that was only just soluble. It just speaks to how difficult go is.

In Other News (4, Funny)

froodiantherapy (858964) | more than 9 years ago | (#11740458)

Sony has released a new devixe, tentatively dubbed the "CD Burner," capable of burning the first second of any of your music CDs! Programmers hope some day to move to the entire first track.

Re:In Other News (0)

Anonymous Coward | more than 9 years ago | (#11740529)

now that one was really nice and funny in contrast to some other comments moderated as funny

thanks

Size? (5, Informative)

Anonymous Coward | more than 9 years ago | (#11740463)

5x5 is 1/4 the size of 19x19??? More like 1/14th.

Re:Size? (0)

Ayaress (662020) | more than 9 years ago | (#11740518)

It's 20x20. 19 squares, but Go is played on the vertecies, not the tiles, so it's 20x20.

Re:Size? (5, Informative)

Doctor Ian (452190) | more than 9 years ago | (#11740555)

No, 18 by 18 squares, the game is played on the vertices which is 19 by 19. There's a centre vertex, see?

Re:Size? (1)

Ayaress (662020) | more than 9 years ago | (#11740629)

Yeah, I checked after the replies, you're right. I just assumed the dozen posts that said 20x20 were right without bothering to look it up. I suck at the game, even worse than I do with chess, so I never pay attention to it anymore.

Re:Size? (2, Informative)

wmshub (25291) | more than 9 years ago | (#11740556)

Uh, no.

It's 19x19. There are 18 squares on a side when you look at the board, but as you point out, the stones are placed on the vertices, so the playable positions form a 19x19 grid.

Re:Size? (1)

cameldrv (53081) | more than 9 years ago | (#11740560)

You've never played go. There are 19x19 intersections.

Re:Size? (1)

PetWolverine (638111) | more than 9 years ago | (#11740584)

No, it's 19x19. If you're counting squares instead of vertices it's 18x18, but that wouldn't make sense, since, as you say, it's played on the vertices.

Re:Size? (0)

teknomage1 (854522) | more than 9 years ago | (#11740646)

I think your math is faulty, in terms of board area 5x5 is 17% of the board, while 1/14 would be closer to 7%, and anyway as it's probably game theory trees 5x5 is likely a drop in bucket.

Re:Size? (1)

smoondog (85133) | more than 9 years ago | (#11740731)

IIRC, traditionally computer approaches to solving Go have used a 10x10 board. Maybe that is what the poster was thinking about.

Wait... what? (-1, Troll)

jimmsta (628925) | more than 9 years ago | (#11740465)

so... does this mean that games will be smarter, or will games be able to beat themselves more often? Does this really help with the future, or what? No, I didn't RTFA, since I'm tired from my computer-repairing job...

Go... (5, Informative)

BicycloHexane (819192) | more than 9 years ago | (#11740470)

The way that chess games work is they check n ammount of moves into the future. With each iteration into the next move it splits off into a massive tree of moves. As an example, the first iteration has 10 potential moves, the next has 100 and the next has 1,000 With Go as an example there may be 100 potential moves on the first iteration and then 10,000 and then 10,000,000 The number of potential moves grows way faster then in chess.

What the fuck? (-1, Troll)

Bloodlent (797259) | more than 9 years ago | (#11740474)

Fuck my karma-What the fuck are they doing? This happened in two thousand-fucking-two. 3 years ago. What the hell? The Slashdot editors are fucking retarded. Why don't we make a retro.slashdot.org for shit that happened years ago?

Re:What the fuck? (0, Redundant)

castrox (630511) | more than 9 years ago | (#11740578)

Although put in a silly language, the parent does have a point. :-\

Re:What the fuck? (1)

dcclark (846336) | more than 9 years ago | (#11740693)

And on the other hand, while it may be old news, it IS interesting. I certainly didn't hear about it when it happened. News like this tends to be less visible than news about chess computers or other projects that are more in the public eye.

yep (4, Informative)

St. Arbirix (218306) | more than 9 years ago | (#11740482)

Check out this [nyud.net] for a decent comparison between chess and go for those of you who have been missing out.

Also, dig my sig biotches.

Oh a fanatic (2, Insightful)

Eunuch (844280) | more than 9 years ago | (#11740499)

You notice there's no chess players proclaiming its superiority to Go. What is this, frustration from the fact that Go doesn't help with getting an Asian girlfriend?

Re:Oh a fanatic (1, Informative)

Anonymous Coward | more than 9 years ago | (#11740664)

What is this, frustration from the fact that Go doesn't help with getting an Asian girlfriend?

Hey, that's every Geek's concern---except you, obviously, since you are Eunuch [slashdot.org] .

Um, who wins? (1)

endersdouble (719120) | more than 9 years ago | (#11740489)

Am I the only one ***OUT OF THE PEOPLE HERE WHO KNOW HOW TO PLAY*** who is slightly confused after a cursory glance at that site as to who exactly *wins* in 5x5 go? Obviously if it's solved, it's either a black win, a tie, or a white win (as I said, I'm not sure, though I'd guess one of the first two.)

Can there be a tie? (1)

Eunuch (844280) | more than 9 years ago | (#11740526)

I don't think so.

Re:Um, who wins? (1)

ricewind (690994) | more than 9 years ago | (#11740534)

From TFA

As was expected it is a win for the first player with 25 points (the whole board belongs to black).

It's Go. Black plays first. Just like in that other board game, which I can't remember the name of, white goes first.

Re:Um, who wins? (1)

jrumney (197329) | more than 9 years ago | (#11740701)

It's Go. Black plays first. Just like in that other board game, which I can't remember the name of, white goes first.

It's called "Nine Men's Morris". I thought everyone knew that. Or are you talking about that other game with the horses and castles and stuff?

Re:Um, who wins? (0)

Anonymous Coward | more than 9 years ago | (#11740612)

There are animated GIFs on the article's page showing the optimal moves in a 5x5 game. Black win in all cases, assuming optimal moves (once you consider the captures).

Re:Um, who wins? (1, Interesting)

PetWolverine (638111) | more than 9 years ago | (#11740625)

It has to be a black win or a tie. If White has an advantage, Black can just pass the first turn, effectively trading places and giving him White's advantage.

Not "one quarter" (-1, Redundant)

Anonymous Coward | more than 9 years ago | (#11740494)

5x5 go is NOT one-quarter of the Go board.
If I remember correctly, a Go board is 20x20,
so 5x5 is ONE-SIXTEENTH of the entire board.

Just as 2x2 is ONE-SIXTEENTH of an entire 8x8
chess board.

Oh Please... (0, Troll)

_Potter_PLNU_ (627430) | more than 9 years ago | (#11740500)

5x5..pfft. I wrote a program that solves 1x1. I win every time.

Re:Oh Please... (1)

flatface (611167) | more than 9 years ago | (#11740596)

No, a move by either player would be considered illegal self-capture.

Re:Oh Please... (0)

Anonymous Coward | more than 9 years ago | (#11740724)

but white get 5.5 points, so white wins ;)

Sheeshkabob (0)

Anonymous Coward | more than 9 years ago | (#11740613)

A marathon.. pfft. I run a centimeter-long track. I finish every time.

Uh... (0)

Anonymous Coward | more than 9 years ago | (#11740506)

(16x16 / 2x2) / (19x19/ 5x5)

8/3.8

Even taking into account that there's only 2 different sorts of pieces in Go, I'm sure that 5x5 Go is WAY more complex than 2x2 Chess. Way.

Hm, 4x4 or 5x5 seem closer for Chess...

"a quarter of a full scale board"? (4, Insightful)

Speare (84249) | more than 9 years ago | (#11740514)

A 5x5 go board is not a quarter of a full scale board. It is only roughly a quarter in each dimension. A full go board, if I recall, at the size most people play, is 19 by 19 intersections. That's 361 positions. A 5x5 only has 25 positions. Each intersection can theoretically contain three states.

In the past couple days, people have been talking about "cracking" an 80 bit hash with a 69 bit effort. It's logarithmic, people. 69 bits is not three-quarters of 80 bits, it's a factor of 0.000488 in terms of the workload to crack it.

SHA-1 is now 0.000488 (4.88*10-4) as strong as it was. And by my calculator, 5x5 go is 4.866*10-161 as hard as a brute-force solution as a 19x19 board would be.

Could I get that in binary or hexadecimal? (0)

Eunuch (844280) | more than 9 years ago | (#11740648)

I don't see why decimal needs to be used here.

2x2 chess is... (2, Funny)

cloudkj (685320) | more than 9 years ago | (#11740522)

...the only game simpler than 2x2 tic-tac-toe :)

How long till they solve chess? (4, Interesting)

jaylee7877 (665673) | more than 9 years ago | (#11740527)

I've always believed within my lifetime, chess would be solved. In other words, a computer would come up with the perfect solution to chess so that no matter what moves you possible make, out of the, i dunno, billions, trillions, or higher number of possible moves, the computer knows how to beat you. The simplest comparison I can think of is tic-tac-toe. If you've played tic-tac-toe enough, you've learned that no matter who goes first, someone can always force a cat (tie game). I wonder, is it possible to always force a draw in chess or might it be that whoever goes first can always win? Sure the computing power to figure this out is beyond anything we have now, but with quantum computing and other advancements, I expect to see chess solved in my lifetime.

Re:How long till they solve chess? (5, Interesting)

cnettel (836611) | more than 9 years ago | (#11740695)

Yeah, you have to rely on quantum computing to do that. Alternatively, you have to prove that lots of "possible" chess positions don't actually appear, no matter how the other player plays, on the way to the optimal win.

The number of chess positions is, very naively and as a significant underestimation, something like C(8, 64) * C(8,56) * C(8, 48) * C(8,40).

Even this severe underestimation gives 1.8E35, or about 2^117.

Let's say that 2^80 problems are crackable today and that we wouldn't have the non-locality problems of chess (a move consists of computing another position and then you have to see if that is already in the database of computed moves, not as parallel as just trying encryption keys 'til it works). The added 2^37 is on the scale of 13 billions. If 2^80 is done in a year now, this would require the age of the universe.

We can guess that we, if lucky, get to trust Moore for our lifetimes. Hoping that it will get better than that is a long shot, in my mind. The development of computing speed for computing machines in the Turing sense will probably rather slow down. Even if the current speed of increasing computation capacity was maintained and chess would be as simple as encryption testing (calculating moves is simpler, coordinating the effort and addressing the memory isn't), it would taket 56 years to get to the point where a run would take a year -- based on extremely optimistic assumptions.

Finally, we haven't even got to the point about how to store all that information. 6E23 hydrogen atoms weigh about a gram (Avogadro and all that). Let's say we store one bit for each atom. We would need one billion kilograms of storage to store one bit for each of the possible chess positions. To reach less than 1 bit/position seems quite hard...

Re:How long till they solve chess? (1)

smallfries (601545) | more than 9 years ago | (#11740723)

Congratulations on a quality troll. Too bad you didn't get any bites. Has the makings of a classic slashdot flamefest.

Chess vs Go (0)

Anonymous Coward | more than 9 years ago | (#11740533)

Go is orders of magnitude more complex than chess (although chess is the more interesting game for us mere mortals, imo).

The reason this is noteworthy is that Go (which is played on a 19x19 board) is notoriously difficult for computers; the best programs cannot defeat a competent amateur. To have a program which has solved Go (unlike the best chess programs, which are merely at the strength of Grandmasters), even at a miniscule 5x5 scale, is a sign of progress.

In the interest of fairness... (2, Funny)

Theatetus (521747) | more than 9 years ago | (#11740540)

It's nice that AI and computer science research is going into popular and well-known games like go, but a lot more complexity and interesting research can be found in a less-known game called chess [chess.net]

Re:In the interest of fairness... (1)

malfunct (120790) | more than 9 years ago | (#11740638)

No, not complexity, that is if you measure the number of possible outcomes given a particular configuration of the board as compexity. For any given configuration of the board there are far more possible outcomes for go so it is MUCH harder to min/max because of the size of the search space.

Re:In the interest of fairness... (0)

Anonymous Coward | more than 9 years ago | (#11740642)

Fairness? You forgot backgammon.

Re:In the interest of fairness... (1)

eobanb (823187) | more than 9 years ago | (#11740644)

You are mistaken, sir. The game of Go is fantastically more complex than Chess can ever hope to be.

Re:In the interest of fairness... (0)

Anonymous Coward | more than 9 years ago | (#11740699)

Only in the number of combinations of different moves that can be played. I've always found it to be a dull game.

Chess, on the other hand, is far more interesting.

Re:In the interest of fairness... (1)

cnettel (836611) | more than 9 years ago | (#11740730)

His humor is fantastically more complex than you can ever hope to be. (Or maybe you just carried it on...)

Re:In the interest of fairness... (2, Insightful)

maino82 (851720) | more than 9 years ago | (#11740712)

Go may have simpler rules than chess, but it by no means a simple game. When I tell my friends about Go they laugh at me, but after explaining the game to them and giving them a 9 stone handicap and thoroughly trouncing them (I'm only around 12kyu... practically a beginner) they begin to see the game is much more complex and subtle than they anticipated. A computer program playing Go would have to be much more adaptive than a program playing chess, or have a much quicker algorithm to process the insane number of possible moves and responses. In either case, research into a computer that can play Go and can beat a human is something that is extremely worthwhile and applicable not just in Go, but in other AI applications as well. Don't get me wrong, research into chess playing programs is just as worthwhile, but any advance in Go will be orders of magnitude more impressive than any advance in playing chess.

Posted AC to avoid karma whoring (2, Informative)

Anonymous Coward | more than 9 years ago | (#11740542)

Seeing as so many karma whores are saying that this was solved 3 years ago, here's a hint: RTFFA (Read The Full Fucking Article). If you do you'll realise that it was just solved recently. [www.nwo.nl]

Re:Posted AC to avoid karma whoring (0)

Anonymous Coward | more than 9 years ago | (#11740627)

Seeing as so many karma whores are saying that this was solved 3 years ago, here's a hint: RTFFA (Read The Full Fucking Article). If you do you'll realise that it was just solved recently.

Speaking as a karma pimp, don't you be talkin' about my ho's.

"Cracks" defined (0)

Anonymous Coward | more than 9 years ago | (#11740547)

/Anon because I'm not in a whoring mood, and Wiki is getting so slow these days the link may not load for you...

But what the headline means is that 5x5 Go has become a Closed Game [wikipedia.org] .

Re:"Cracks" defined (0)

Anonymous Coward | more than 9 years ago | (#11740709)

Anon because I'm not in a whoring mood...

What makes you think you would get points for your "post", such as it is?

The mathematical rules (5, Interesting)

Eunuch (844280) | more than 9 years ago | (#11740583)

Note that a liberty is an empty spot on the board that is either next to your stone or can be reached by moving across your stones horizontally or vertically. This is great for computer scientists who don't know the game yet, http://brooklyngoclub.org/jc/rulesgo.html:

The Alternating Rule:
Two players, called Black and white, keep alternating moves till the end of the game. Black plays first. A move by a player begins by his placing a stone on an empty intersection of the go board. The first player who cannot put down a stone without breaking a rule loses the game.
The Rule of Capture:
After a stone is placed on the board, all enemy stones which have no liberties are removed. A player's move is not finished until this phase has been completed.

The Rule for Suicide:
Suicide is illegal. Precisely, after a stone has been played, and after the rule of capture has been applied to his enemy stones, if the stone has no liberty, then the move was illegal.

The SuperKo Rule:
A player is not allowed to place down a stone if, after the rule of capture has been applied, the resulting Board position has appeared previously in the game.

arthur c clarke story (3, Interesting)

Sark666 (756464) | more than 9 years ago | (#11740622)

Everytime chess gets mentioned on /. (ok I know it's a go story but you know the comparisons will start) I like to post a link to this short story written by Arthur C. Clarke. I originally found the story through someone else's /. post http://www.research.ibm.com/deepblue/learn/html/e. 8.2.shtml [ibm.com]

Checkers (1)

Skraut (545247) | more than 9 years ago | (#11740651)

Isn't this in the realm of possibility for Checkers now. I know checkers has been solved with up to like 9 pieces a side. But with the limited moves, it should be able to create a database of all moves in only a couple terrabytes or so. Yeah I know "only" is relative, but it should be in the realm of possibilities.

The actual details (1, Informative)

Anonymous Coward | more than 9 years ago | (#11740656)

The actual details are available at Erik van der Werf's homepage [unimaas.nl] at the Universiteit Maastricht, and in particular on his publication list. [unimaas.nl]

Just as exciting as... (0)

Anonymous Coward | more than 9 years ago | (#11740671)

This is nearly as exciting as the release of HappyKitchenGames [happykitchengames.com] first game Click-a-Block [happykitchengames.com] . Anyone want to write a program to play that game?

If we solve Go, will it still be fun? (4, Insightful)

Eunuch (844280) | more than 9 years ago | (#11740677)

I think it will. We still have weightlifting competitions even though we have forklifts at our disposal.

GNU Go and future AI research (5, Informative)

keen (86192) | more than 9 years ago | (#11740684)

AFAIK, the current state of the art of Go on computers is Goemate [wulu.com] and Go4++ [infonomics.nl] .

GNU Go [gnu.org] is actively developed, but it still does not match commercial Go software, ranking 1-2 stones weaker. It is rated from 8 to 9 kru, which is a weak amateur.

Computers have thus far not been too great at cracking go via the usual searching algorithms, as it has a high branching factor - starting at 361, much higher than chess! It is only recently that Go programs have even begun to achieve low levels of competence. Besides the limited searching and pattern recognition of current software, future programs may improve by decomposing Go into 'subgames', allowing it to be more readily attacked.

Versus people or computers? (2, Interesting)

Eunuch (844280) | more than 9 years ago | (#11740703)

It would seem that it could be very different. There are a lot of these computer-only competitions and tuning for that will be very different from tuning for humans online.

Re:GNU Go and future AI research (1)

keen (86192) | more than 9 years ago | (#11740714)

Sorry, that should read *peaking* at 361 (which is of course 19^2).

What?? (2, Interesting)

Transcendent (204992) | more than 9 years ago | (#11740686)

5x5 go is miniscule, similar in scale to "solving" 2X2 chess

Sorry, but that's like a full chess board with the pawns removed (if even that much).

5x5 Go is still fairly complex. Although the article is old (2002), I'd still like to see a caltulation time comparison.

2x2 chess can be solved in a manner of seconds/microseconds. 5x5 Go might take a few days to brute force it.
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...