Computer Cracks 5x5 Go

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

October 2002

[fembots]

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.

GREAT SCOTT!

[agildehaus]

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

2002?

[porcupine8]

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

The future called

[Anonymous Coward]

It said 6x6 go is solved.

In Other News

[froodiantherapy]

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:October 2002

[Xzzy]

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.

Comment removed

[account_deleted]

Comment removed based on user account deletion

In the interest of fairness...

[Theatetus]

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:What the hell?

[mikael]

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.

Re:2X2 Chess?

[nacturation]

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

What, are you crazy!?

[ucblockhead]

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

Re:Some slashdot lore.

[Deadstick]

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

Connect 4 Solvable As Well

[Comatose51]

My friends and I once made a connect 4 game but the AI wasn't very good against other AIs. It occured to me that perhaps Connect 4 is solvable. Each hole has 3 possible states and there are 42 holes. So it's 3^42 possible board states. However, there is a very large number of board states that cannot happen, such as having a piece in row 2 but not row 1, etc. Someone with better math skills can calculate what the actual number of possible board states. My intuition is that it should greatly reduces the number of states enough that we can solve the entire game. The rules are simple and the AI for it is simple as well. We used a tree to represent moves and applied alpha-beta pruning to it.

Re:Uh...

[Ayaress]

Actually, the fact that Go only has two pieces is why it's so much more complex. Chess pieces individual behavior is what usually limits the number of moves in Chess. Also, since Chess doesn't easily scale down, 2x2 chess doesn't work: QK QK Neither side can move, since any move they make still leaves their king in check. I guess that means that White looses by default, since White goes first and can't make a legal move. Unless you play by rules like with blitz and don't count check, only actually capturing the king, in which case White always wins (unless he's REALLY dumb).

hypertext

[morcheeba]

I hear they are working on a "hypertext" transfer protocol [w3.org] -- it's kindof like Apple's hypercard [ihug.org] where you can "link" to various media in a free-form manner. A "mouse" is used to select which links to follow, and the transport protocol sends the appropriate network packets to retrieve the data.

Re:What the hell?

[prockcore]

I heard rumours that there was a solution for "Tic-Tac-Toe" very close to being announced.

Duh, the only solution is not to play.

2x2 Chess

[gnovos]

Not QUITE that scale...

Two by two chess:

White: Checkmate in 0, would you like to play agin?
White: Checkmate in 0, would you like to play agin?
White: Checkmate in 0, would you like to play agin?
White: Checkmate in 0, would you like to play agin?

Re:October 2002

[hdparm]

Can you imagine the level of hilarity (this is the correct word?) produced tomorrow after dupe of this story appears on Slashdot front page?

Re:hypertext

[TLSPRWR]

Using this technology, I've created the "one-click shopping" technique to create webstores!
I should probably patent it before someone else does...Nah, I'll wait and see if it takes off.