Slashdot Mirror
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)."
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 the day before 5X5 Go is solved.
Rock that crushes, Paper & Scissors that don't matter.
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.
Transcend Humanity. Please.
Marty, this story once mattered, back in 2002, when it happened.
If computers can beat chess grandmasters and similar feats, how is this anything special?
What is this, Classic Slashdot? Next do we get a story on the impending end of the dot-com bubble?
Warning: Apple/Nintendo fangirl. Likes her electronics cute & cuddly. May be rabid.
It said 6x6 go is solved.
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.
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.
"Kaylee, that's the buffet bar." "But how can we be sure unless we question it?"
5x5 is 1/4 the size of 19x19??? More like 1/14th.
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.
Check out this for a decent comparison between chess and go for those of you who have been missing out.
Also, dig my sig biotches.
Direct away from face when opening.
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.)
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?
Transcend Humanity. Please.
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.
[
Comment removed based on user account deletion
I don't think so.
Transcend Humanity. Please.
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.
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
All's true that is mistrusted
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.
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.
Vintage computer adverts: http://www.vintageadbrowser.com/computers-and-software-ads
But what if it's 2x2 chess with all knights?
Want to improve your Karma? Instead of "Post Anonymously", try the "Post Humously" option.
There is a neat leaning variant called Quic k Chess.
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.
$2B OR NOT $2B = $FF
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.
Transcend Humanity. Please.
No, a move by either player would be considered illegal self-capture.
That would be one of the absurd possibilities!
Hilarious! Too bad you posted AC
No sig for the moment.
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
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 cake is a pie
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.
Introducing Microsoft Vacuum 1.0 The first Microsoft product that doesn't suck.
The actual details are available at Erik van der Werf's homepage at the Universiteit Maastricht, and in particular on his publication list.
I think it will. We still have weightlifting competitions even though we have forklifts at our disposal.
Transcend Humanity. Please.
AFAIK, the current state of the art of Go on computers is Goemate and Go4++.
GNU Go 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.
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.
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.
Transcend Humanity. Please.
http://swag.uwaterloo.ca/~jchampaign/goapplet.html
I call white!
~ Crummy
To have a program which has solved Go (unlike the best chess programs, which are merely at the strength of Grandmasters)
It should be noted that even on a 9x9 board (let alone 19x19), competent amateurs can beat any computer program.
19x19, 13x13, and 9x9 (the "standard" sizes, though 7x7 is fun sometimes), require totally different strategies. 9x9 is pure life and death, 13x13 is mostly fighting, and 19x19 requires a good understanding of balancing influence for defined territory (don't spread your stones too thin while not letting them get bunched up).
For all who don't play go or are new to go, the biggest problem with the 19x19 and even 9x9 computer programs is that the computer can't see the dual threat someone might play with a sequence of moves. For example, you can start to attack a specific section of the board, and use what you played to grab hold of an even larger section of territory, or even kill a large portion of their stones. It's easy to fool the computer in Go.
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.
EvilCON - Made Famous by
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).
A 5x5 go board has only 847,288,609,443 possible game states, even including impossible boards. Assuming the relatively tame pace of scoring 100,000 boards per second towards completion, which on a board of that size is trivial, this solution takes a simple brute-force time of 98 days. That solution space can be cut down by almost two orders of magnitude with simple reflection and rotation tricks, implying a realtime tree search space of about a day and a half.
Given that my full board scorer moves faster than that, and given that the university probably has more than one PC to work with, I wonder how it is that anyone can justify this as something larger than a publicity stunt, especially given that none of go's emergent structures even fit onto a 5x5 board.
This is horseshit, in short. Mod story down.
StoneCypher is Full of BS
2 kings wouldn't work, it would be a constant stalemate.
Anthropic principle: We see the universe the way it is because if it were different we would not be here to see it.
exp-time-complete: the time to solve one particular problem for an input of size N is no less than O(2^N) time units.
exp-space-complete: you can solve one particular problem in less then O(2^N) if you calculate all the solutions and try to keep all the O(2^N) results around, wasting an enormous amount of storage.
It's better to be the foot on the boot than the face on the pavement. ~~ tkx Kadin2048
Look at the mathematical rules I wrote. If you have equal amounts, whoever goes first will lose because that person will have no move left.
Transcend Humanity. Please.
Since computers have started to beat strong chess players, it *is* taken for granted by many that computers can beat reasonably strong people with today's processing power.
Presently, if a typical geek started playing Go, they would get their ass kicked by the weakest computer for a week or two.
After a month, they would be winning the odd game, if the computer gave them a 3-stone headstart. (Like 3 free moves to start in chess).
After three months, they would win some games in an even match against the weaker programs (Turbo-go)
After six months, they would be winning against a 3-stone or higher handicap for the computer.
Then they find a stronger Go program.
They start to lose every match again.
After another month or so, they start to win on the weaker levels.
Take it six months ahead, and they are smashing the computer in an even match with no handicap, playing white (white moves second) or at lower levels against a 3 or 4 stone handicap.
The only thing that makes the game playable against a computer is that Go has an incredible handicapping system that lets uneven players play against each other.
So what makes this story interesting? Aside from the brute strength issue?
The first moves of the game, often in the corners in roughly a five-by-five area (Joseki) are only recently being evaluated for best move potential...
That can affect the outcome of professional matches played for big $$$$.
But more importantly for people like me, I can't play humans much... Kids, wife and home environment mean I can't spend 30 minutes undisturbed, so playing against human opponents is out for me.
Any technology that makes computer programs stronger, improves algorythms or makes me play harder will keep my morning bus trips interesting.
Because Go programs have got a long way to go if they are easily defeated against a human opponent with just 1 year experience.... Who would be easily classed as a novice let alone just a weak player.
GrpA
Enjoy science fiction? "Turing Evolved" - AI, Mecha, Androids and rail-gun battles. What more could you want?
Shouldn't the sig be 0x2b OR NOT 0x2b??
In anything I've used $2b would be a variable with that name.
0x2B | ~0x2B == 0xFF
$2B OR NOT $2B = $FF
Would return true or false depending on the value of $FF.
$2B = $FF should return as true (the assignment, the NOT makes it false, so the $2B would equal $FF and return as true for non-zero values (as a condition to an if).
I am not criticizing to be an asshole, I really liked the sig and it made me think, you were just a sensless victum who is forced to listen (after my girlfriend rolled her eyes and left the room).
Who wins 2x2 chess Black or White?
It starts with a checkmate, but in Chess you cannot take the king, so what happens?
Wow, sent an e-mail as suggested when clicking on "use classic" banner, and got a fast response that addressed my msg
I don't mean in terms of computation power, I mean in a theoretical way. As in, it can be shown that Go can be solved, even if we cant='t solve it.
I don't know much about these sorts of things... practically nothing in fact. Now, we all learned as kids that tic-tac-toe (or Naughts and Crosses if you prefer) is closed or solved or whatever the right term is... whoever goes first always wins, so long as they go right in the middle.
It seems pretty clear to me that if the solution in the 5x5 case is to put the first stone right in the middle of the board, then my money's on the same move on a full-size board. Because of the way Go works, the center square has the highest "potential" for liberty in that it's equally capable of finding that liberty in any direction. (Conversely, the worst first move is the corner.) I have a hunch that going anywhere else is more of a dead-end move... just like in Tic-Tac-Toe, only we don't learn this, brute force, from the older kids on the schoolyard.
(Wait... Did I miss something? I thought the solution presented in the 5x5 game had black's first move at the center. If that's not the case, consider this an exercize in rationalization, facts notwithstanding)
Passing need not be mentioned. The page mentions that.
Transcend Humanity. Please.
You don't, it's 19x19.
but yes, 1/16th is reasonably close.
As can be read here some languages actually do use $ as prefix for hexadecimal.
:)
Then there are languages who use single = for comparison too. So if you are friendly enough it might make sense.
I don't know where that 2x2 chess comparison came from, but heck..I can solve that: take the guy's king with your king. Done.
(insert witty/esoteric/dumb quote here)
If you had bothered to read the first comment you would have found this was posted as the first comment
I definitely heard about this a long time ago, i think the same guy is working on a 9X9 version working up to the 13X13 and eventually to the 19x19? version.
its a goodo accomplishment, but only if they could crack ARIMAI (spelling mistake.) it is much harder to beat, even on the most difficult setting i can still beat the computer easily with funky tactics.
Check journal for info on Anti-TextBook, an idea by me.
2x2 chess... the new reform chess variant?
quidquid latine dictum sit altum videtur.
My fascination with solutions to these games is not really what they are, but how they developed. Of course the verification is boring since its simply brute force, but I do like strategies that have some clever evolution or a clever implementation.
A multi-user network client to "solve" Chess or Go might produce some fascinating results or verifications. Is there a way we can contribute our space CPU cycles to the end of these game as we know it?
Eventually we may have the horsepower to brute-force win every game at 19x19 but I wonder if it might be more economical to program computers to play the same way that people do. (The father of one of my friends seemed to have all of Alekhein's games memorized. We couldn't do anything that he hadn't seen before.) By using pattern recognition we might be able to get a more capable game sooner. You wouldn't have to store all possible games; only the good ones. If someone blunders while playing the computer and produces a game it hasn't seen before then it could probably win by brute-force calculation. If someone does something different and wins then the computer has another game for the database. The game is symmetrical in a way that chess isn't and that would reduce the number of games stored by a factor of at least four.
Seems kinda obvious so there must be something wrong with it but I'm not sure what it is.
isn't it a stalemate if it's a player's turn and he can't move?
Hi
:)
Sorry to hear you can't really play undisturbed as much as you like. I'm in a similar position at times and hence I've started playing go at http://www.dragongoserver.net wich is a sort of korespondance go. You play long lasting games at perhpas as little as one move per day or less (logging on and off in between).
I tend to play a few moves at breaks or inbetween idleing on the net.
Hope to see you there...
http://gobase.org/studying/rules/?id=2&ln=uk
Karma: Positive (mostly due to rash moderations)
I hear they are working on a "hypertext" transfer protocol -- it's kindof like Apple's hypercard 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.
HIV Crosses Species Barrier... into Muppets
I don't know whats worse: a dupe or a story thats almost 3 years old... I certainly hope the editors aren't paid to do what they do. You subscription holders should really rethink your purchase.
It does need to be mentioned. I've never seen the rule that if you can't put a piece down eithout breaking the rules, you lose. You can always pass.
Actually no, it would be a mutual checkmate. The king can never place itself in check though so the game would start in an illegal state.
Looking for an Information Security student project suggestion?
Try http://dotcrimeManifesto.com/
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.
The last news was probably "go invented" dated 2500BC or whenever.
Engineering is the art of compromise.
Maybe he plays as White.
I found the meaning of life the other day, but I had write-only access.
Therefore 2x2 chess would start with checkmate and is absurd.
YOU'VE SOLVED IT!
Irritable, left-wing and possibly humorous bumper stickers and t-shirts
And you need brackets somewhere or something, as something takes priority over something else; enough people've pointed out tweaks to my version that I can't even remember any more (and it's 4am, which is never a good time for thought...)
I mod down anyone who says "I will be modded down for this", regardless of the rest of their comment
I have been interested in computerized Go for a while now, but have never actually gotten my feet wet in the subject.
One approach I have always wanted to try is this:
set up a massive neural net that takes the state of the entire board as input, goes through way too many intermediate layers, and spits out a preference for spots to play. The state of the neural net could be exhaustively described with a few tens of thousands of [0,1] doubles.
Then set up "breeding" algorithm, make a few hundred instances of the program, each with its own neural net, and then have them pretend to be users on an internet Go site. Don't try to understand how they play, just let them figure it out. You could even, on occasion, let them play eachother...
I don't know if this would produce a good genome ever, but I'd be interested to see where it went regardless.
Does anybody know if this sort of thing has been tried before?
First, I'm glad to see at least a few people got the joke.
Secondly, I definitely agree with you. I think both go and chess programs are taking the less interesting route by doing dictionary / exhaustion algorithms, since that's not how humans play either game (in most circumstances -- openings and endgames are another matter).
Sticking with chess (since I know it better, and I think the lesson carries over), I think Kasparov really exposed this flaw in his second game against Fritz. If you completely seize the initiative from an algorithm based on exhaustive move analysis, it is helpless until you make a mistake. Even the most amateur human player would have said "he's making me look stupid; I have to do something". People play games like go and chess by setting out objectives and performing a basic analysis on the moves that further those objectives, calculating risks based on that analysis, and choosing the next move. I would love to see a go- or chess-playing program based on that model.
All's true that is mistrusted
solving a board a quarter of the size only solves one sixteenth of the problem. thats what i read.
The king can never be placed in check, but if through legal means he finds himself in check, there's no reason he can't take the other king and end the game.
This post written under Gentoo-linux with an SCO IP license.
I think I saw that in a movie...isn't that where the horse runs up to the edge of the cliff (or board in this case), stops just short of falling off, and the rider is unceremoniously thrown forward over mighty steed's head, over the edge of no return.
On a more serious note, that might be interesting if the chessboard had a "wraparound" feature, so if you move beyond the edge, you actually start back at the other side.
But can You take the King?
There is no rule saying you can't, in chess it is impossinle to be able to take the king.
Wow, sent an e-mail as suggested when clicking on "use classic" banner, and got a fast response that addressed my msg
I didn't expect to be taken seriously there,
I truly think it reads better the way you had it, I was just board and as I said, I liked it and thought too much.
Wow, sent an e-mail as suggested when clicking on "use classic" banner, and got a fast response that addressed my msg
Actually, there was a cut down 6x6 variant of chess designed so that it would run on MANIAC.
English is easier said than done.
Computationally, Go is far more complex. A good Go player can consistently beat the best Go computers. At the moment, the very best human players are only breaking even against the best Chess computers.
English is easier said than done.
Honinbo Warrior was coded in UCSD Pascal and really did not play that well, but my boss and a few friends talked me into running ads in some Apple II magazines and marketing it. Working on that program was a fun obsession that lasted about 1 1/2 years.
Go is such a great game. In the 1970s, I got to play exhibition games with Miss Kobyoshi (women's world champion) and Mr. Lee (national champion of South Korea). The high level of their play really blew me away - getting slaughtered was a surprisingly great experience.
The Gnu Go program plays a good game, BTW. It is best to play against human opponents, but give Gnu Go a try also. Just like studying chess, if you get into playing Go, make sure you study complete master games: studying opening, middle game, and end games in isolation just does not cut it.
Seriously though, I wonder. I suspect that it might be rather easy to solve, but I'm to lazy to find out.
English is easier said than done.
The king can't approach the other king ever because that would place him in check. A king can never take a king.
English is easier said than done.
To put this into even more perspective
..., 9 dan.
In go, players can be given a rank on how strong they are compared to others. It's a fairly simple method.
Everyone starts out at about 30 kyu. As they get stronger, their kyu number decreases till it gets to 1 kyu. At which point starts a new number system that goes upward, starting at 1 dan and goes to 9 dan.
So..
30 Kyu, is weaker then a 29 kyu,... 2 kyu, 1 kyu, 1 dan, 2 dan,
Now that is for amateur rankings. There is a professional ranking system that starts at 1 dan pro and goes to 9 dan pro. I have heard that a 1 dan pro is roughly the same strength as a 7 dan amateur.
There is a handicap system where if you take the rankings of two players and subtract them, it determines the number of handicap stones given to the weaker player. Thus a 10 kyu playing against an 8 kyu, the 10 kyu player gets to play first by placing 2 stones on the board (one set of rules allows black to place the stones anywhere on the board, another set of rules, the stones must be played at specific spots). The rule of thumb is that each handicap stone is worth about 10 points. Another rule of thumb is that each handicap stone "erases" one mistake by the weaker player.
Normally one doesn't play with more then a 9 stone handicap. Mainly because beyond 9 stones, black really isn't "learning" much
To prevent ties, a half point is awarded to white in handicap games, in an even game (where both players are of equal strength), white is given 6.5 points (this has been changing around some -- depending on the rules you are playing with).
Usually after the 1st game or so a 30 kyu player learns enough to drop to around 28 kyu or there abouts.
I have heard that the amount of time and study to go from a 10 kyu to a 1 kyu rank is about the same as going from a 1 dan to a 2 dan.
A game between two weaker players can result in scores of anywhere from just a few points to 100's of points going to the winner. As one gets stronger, the wins are usually only a few points, or someone resigns.
I have seen strong dan and pro players when playing weaker players their goal is to try to get the score within a half point (always in their favor).
In Go, the game really doesn't start to get interesting till about 30 to 50 moves into the game (in chess, the game is usually over at that point).
Currently on one of the online go playing servers, GNU Go (among the top go playing programs -- though not the strongest) is roughly around 11 kyu in strength, A weak dan player can give gnugo a 9 stone handicap and the dan player will still win.
Several years ago, Janice Kim gave the top go playing program a 28 stone handicap and she still won the game (I believe it was a 28 stone game).
To get to a professional level player, it is best to start playing when you are very young. Expect to dedicate your life to the game. To get to a strong amateur dan level, also expect to dedicate a good chunk of your life to the game.
I'll admit that I'm a wide eyed enthusiast, but I'll also delimit that with acknowledgement of the fact that I'm one of the last pasty white guys in the West to have discovered it.
l
I wish I had been introduced to Go as a child. I've only been learning for a month now, and I'm obsessed already. I've completely given up traditional computer games, unintentionally... its friggin' GO. I like chess, and play when I've free time... but Go is making me make time for it!
That being said, I'll let someone else descirbe the virtues of go with a comparison to chess:
http://users.eniinternet.com/bradleym/Compare.htm
There is no computer program that is able to beat a high-ranked amatuer, let alone a professional go player.
Aside, you meant 19x19, I hope...
Shouldn't the sig be 0x2b OR NOT 0x2b??
In anything I've used $2b would be a variable with that name.
some assemblers use $ as the prefix for a hexadecimal literal. # or something is used for decimal literals. still others use $ to denote a particular register.
-mkb
It's stalemate if the player is currently not in check, but any move will put him into check. In the 2x2 chess setup, white starts in check, and any move he makes results in him still being in check, and is thus illegal. My diagrams broke last time because I had it on HTML, so here it is in plain text:
Start:
QK
QK
White at the bottom, first move, he can do four things: He can use either his king or queen to capture one of the other two pieces. However, both the black king and queen check the white king currently.
Whichever one he captures, his king is still in check, and thus the move is illegal in standard rules, and the game ends in checkmate. White can't finish their turn, so black wins:
Queen takes queen:
QK
K
Black king still checks white king, so this move is illegal.
King takes queen:
KK
Q
Same as above, black king checks white king, this move is also illegal.
Queen takes king:
QQ
K
Black queen checks white, so you can't do this.
King takes king:
QK
Q
White is still in check by the black queen here.
Any way you play it, white is in checkmate. So is black, but by the rules, since white can't get out of check before ending his turn, he looses.
If you're going by blitz rules, then you have the same four options, but they're all legal, since you don't call check in blitz anyway. I've had situations where I've had somebody in check for several turns in a blitz game and not realized it until afterwards, and even more where I've been in check and not been able to immediately counter it and spent a couple turns in sheer agony hoping they don't notice it.. If you capture the black king, you win. If you make a serious mistake and capture the queen for some stupid reason, black king takes black king next turn and white looses.
Then we come to the unbelievably unlikly reason that, having just seen such a stupid mistake made, black then proceeds to capture the white queen, thus putting the ball back into white's court to pave the way for even more stupid mistakes. I suppose it could take nine turns to win a 2x2 chess game, but you'd have to be very drunk to accomplish that.
Maybe go scales differently than chess, but i'm pretty sure the possibilities go up a lot faster than that.
...it's really a sad day for America when we require a goddamn ACT OF CONGRESS to make our DVD players work properly. ~
Old news
There was a documentary released twenty-two years ago about the trying to find a solution for Tic-Tac-Toe. Information can be found here: http://www.imdb.com/title/tt0086567/
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?
"Your superior intellect is no match for our puny weapons!"
Roshita Go is similar to Go, but done in the Roshita Style:
Both players have a supply of "stones" which are actually compressed sugar. One of them is posioned.
Each player takes turn placing pieces on the intersections on the board.
Any player may "capture" an opponents piece by eating it.
There is no draw. Each player must place pieces on the board, anwhere on the board, when it's thier turn, even if all the spaces are filled up.
The first player to die loses.
Death does not have to be by posioning.
"Your superior intellect is no match for our puny weapons!"
I can't help thinking that if you spend 18 months learning to beat a computer at Go you're still gonna get your ass handed to you the first time you play an actual human being. Even if the computer players are strong, don't they lack "personality"?
I suppose I have a hard time understanding why someone would devote that much time to learning to play against humans, much less a computer. Not that I'm claiming I spend my time any better (which would be absurd, seeing as I'm posting on Slashdot!), but what is it that you get from playing Go?
fish and pipes
I started to play from scratch 5 months ago dedicating around 1 hour per day for go.
Now I beat gnugo with no handicap more then 50% of the time.
On KGS (http://kgs.kiseido.com/) I'm 14 kyus only.
Gnogo is around 12-11kyus on the same scale but I think the last stones are compensated by the fact I subconsciouly know which patterns gnugo are unable to handle.
Actually the amateur rankings only goes to 7 dan - however since the pro's goes up to 9 dan some systems use that for amateur rating too. Anyway a toplevel amateur is regarded as a little below a shodan (1 dan) pro player.
some assemblers use $ as the prefix for a hexadecimal literal.
Pascal does, too.
Pulling together is the aim of despotism and tyranny. Free men pull in all kinds of directions. It's the only way to mak
...or am I mistaken?
http://senseis.xmp.net/?SmallBoardGo
Also, 19x19's complexity is in the order of 10^500 and chess about 10^54.
But chess has more rigour as the unnecessary (debatable) obfuscation build into the game through the arbitrary complexity of the moving pieces, thus making it more difficult to get past the tactics to the strategy. Go, on the other hand, has a very simple rule-set similar to finite automata which lends itself easily to the human thought process, making it easy even for a beginner to be able to see dozens of moves ahead and get caught in it's rich strategy.
I am not debating 'which is better' here. If your into rigour and tactics, chess is your game.
Chess is the battle, go is the war.
His name is Eric van der Werf.
a professor at the University of Maastricht
He is not a professor. He was a Ph.D. student. He received his Ph.D. title January 27 of this year.
in Holland.
That should be "The Netherlands". Holland is part of The Netherlands, but Maastricht is not located in Holland.
At about a quarter of the full-board version, 5x5 go
That's about 1/14th of a full board (25 points as opposed to 361 points).
is miniscule, similar in scale to "solving" 2X2 chess.
It is similar to solving 5x5 or 6x6 chess.
The fact that a programmer
Calling Van der Werf a "professor" is a bit too much, but calling him a "programmer" is not enough.
would even consider this a noteworthy challenge is itself a remarkable testament to the game's complexity.
Basically, it was not done before, and could be done with a couple of weeks computation time. That's not to belittle Eric's work; it is only a small part of his work. Read his thesis to see what he has done for the field of Go research.
Van Der Werk's
Again, it is "Van der Werf".
approach is described in detail in an article at the Netherlands Organization for Scientific Research (NOSR).
That should be NWO, not NOSR, and the approach is not described in detail in the article. For details, visit Eric's website.
Real players don't play with the super-ko rule.
I guess today is a passable day to die.
Your post is to insightful what this story is to news.
I guess today is a passable day to die.
Some time ago I tried to pick up go, basing on the faq of a dedicated usenet group (sorry, I don't remember which one right now).
I found it all rather confusing, since it went immediately through the different sets of rules (some rather complex), while I had made the opinion that the power of Go is that it can be played with a very small rule set but still offering a lot of possibilities during play (which imho is what make great games, well, great). Am I wrong?
So, how (I mean basing on which document, tool or else), oh sage
Thank you.
i wrote some elisp to play GNU Go in an Emacs buffer. check it out! (fishing for bug reports; patches welcome.)
see also: GoMode (emacswiki)
there's no reason he can't take the other king and end the game
What makes you think that would end the game? No such rule! The only rules are the ones defining stalemate and the ones dealing with check/checkmate. If you *do* capture his king (and remove it from the board) then he's obviously not in check, much less in checkmate. Chuckle.
I depends on what peices you start with, but I figure the most likely outcome is that white captures black's second peice on turn 2. This leaves black not in check and with no legal moves - and there *is* a specific rule declaring that a stalemate. Another option would be white starting in checkmate and the game ending with no move at all. That would be true if for example if each player starts with a rook covering their king - you are in check and can't capture his king because that would be an illegal move into check.
It is impossible for white to win unless the starting configuration has a black king and no white king. Just a weeee bit unfair, chuckle.
-
- - You can't take something off the Internet! That's like trying to take pee out of a swimming pool.
A variation on Go for players with vastly different skills is to play Go by all the regular rules except the following: The weaker player instead of placing enough stones on the board to make it an even game places enough stones on the board to prevent the better player from creating any viable territory whatsoever. So the strong player's first 20 moves or so are all around the board using his better sense of strategy, while the weaker player responds tacticly to each move and doesn't have a feeling of being overwhelmed. I played this "Go Blip" thousands of times, and it's unsymmetrical play helps the weaker player from being embarrassed at losing since he's trying to beat his own best score of how few initial handicap stones are needed to stop the other from ending up with any viable territory.
Authorization Required... Thank you google cache! -> fractal tic-tac-toe
Thanks for pointing that out--I guess I really borked the site.
English is easier said than done.
http://users.eniinternet.com/bradleym/Compare.html
Scroll down to see a point by point comparation.
How can this happen? On a 2x2 board with two kings, each king can move to any square they're not on, and as such will always be in checkmate by your definintion.
This post written under Gentoo-linux with an SCO IP license.
# but what is it that you get from playing Go?
Beside keeping your brain active (after all you need to continous learn), another property is worth spending the time. In Asia the "balance-of-things", which is tought by Go also highly tributes to the recognition of the game worth to be known by most of Japan's executive business men.
To give an example, and to comment on the real achievement of solving 5x5 Go, the smaller the Go board the more importance has your tactical skills. Like in chess the "reading moves ahead". I might say although the program used learning it might well be to have "just" found a good way of storing positions - never mind to do real strategy. Because on bigger boards (starting 13x13) strategy is another key issue. Finding the balance is the real key to mastering Go. Like in real life you can't get everything in one go, but sometimes allowing the other to win a tactical/local battle, will bring you forward in the big strategy. Hence Solving 5x5 Go misses out a most of the finer skills a real 1 Dan player needs to master.
You asked what it is worth, well, gaining real life experience will teach you that sometimes achieving a goal means holding the balance between different things. But it will so at costs, I like to put forward, that if you master Go, you will be able to skip some of the less pleasurable real life failures.
BTW these points are also made in The Way of Go (Senseis library review) Amazon page
Right so they've solved go for a 5x5 board wonderful, nice to know it has a solution.
However it does make me wonder how good your maths is as if a 'standard' board is 19x19 then this small board is approximately 1/15 of the size (a 5x5 has 25 possible places where as a 19x19 has 361 possibilities which is clearly about 15 times bigger.
so if you are going to say its 4 times bigger be more specific as the area is not just 4 times...
enjoy
2x2 chess is impossible. There is no legal starting position possible since opposing kings cannot be adjacent to each other -- they must be at least one space apart, which would require at least a 2x3 board.
Getzen
Why is this noteworthy? It's pretty straightforward, and known to be impossible for large games ( it has been calculated by 'some physics PhD in a popular book' that to 'solve' chess using a (hypothetical) maximally energy efficient cpu it would require one to convert the mass of Jupiter to pure energy just to power the cpu during the computation - Go is even worse. People do not play games by 'solving' them except maybe very simple ones like Tic Tac Toe. I'd be more impressed with a machine that could actually reason about games, forming powerful theorems and even unproved hypotheses which are improved upon when they don't pan out. For instance, you could state a theorem about chess that it is impossible for white to lose a piece in the first move, or a general unproven hypothesis like: it's good to control the board early in the game to restrict your opponent's movements and create opportunities for your self without knowing exactly what those oppertunities will be.
It's generally accepted among chess-heads that controlling the board early is a Good Thing, but maybe, in the space of chess games, more winning strategies are actually to be found where control of the board is not gained early. That has never actually been proven, it's only a hypothesis ( or maybe a theory since it seems pretty well accepted and seems to be borne out by actual chess games ) but if say, the actual 'solution to chess' were known and it happened to be a strategy that did not cease control of the board early for most sequences of opposing moves, and that player with the 'cheat sheet' for chess played some games, then that theory of chess would quickly fall out of favor to be replaced by the new stategem.
If life is a game, then maybe reasoning itself is rooted in the need for the ability to reason about games. Deception may not play much of a role in the lives of lions and tigers and bears, but for monkeys, the current battle is many times not the war. A male chimp may kowtow to the Bluto of the troop when he's around but then do the nasty with the lady chimps behind his back.
Among humans, goals are even more veiled. The road to X is rarely the direct route. You want a candy bar, you go to the store and buy it - seems direct, but it isn't. To get the 85 cents, you go to a job and earn your money. But to get that job you may have had to obtain college degrees, or certifications, and to do that you had to compete. To get hired you had to compete, and to get promoted you had to compete. The games you participated in probably had less to do with being valuable so as to make your paycheck a good deal for your employer than with gaming so as to appear that way - especially if you have been successful in getting anywhere - nobody ever got to be boss by being a good laborer, the games you have to play to be boss take too much time for someone who spends all their effort working to compete in. Some may find this amoral, but be assured that those who are successful most likely do not even know they are useless fucks who reap all the reward.
They probably assume everyone games as much as they do and when they are rewarded they are certain it is because they really *are* more valuable and they actually think they *deserve* it. To think otherwise would offend their own egos. In fact, if your desire to masturbate your own ego does not make you stupid enough to accept the top seat with a straight face, then you either accept being 'evil' to some extent and wear a poker face, or you put your nose to the grindstone to be an even more valuable resource to exploit ( a lot of currently technical people who didn't spend all their time 'gaming' for popularity in high school because they didn't enjoy it have taken this route. Then they find that labor is labor and that they can not charge more than the third world shmoe who will charge the leas
Beside keeping your brain active
:)
Actually, this by itself is a great reason to play Go. After starting to play, I've found my visualization skills have improved significantly. Moreover, it's a great way to improve your overall focus and mental stamina. Plus, it's just damn fun.
wow...you all don't see a sarcastic joke when it stares you in the face...sheesh. 1x1, c'mon, you think I was serious?
"Hard work never killed anyone." -- Some Dead Guy
as such will always be in checkmate by your definintion.
...well... there's still no rule against it and it's no longer unreachable.
No, on the first trun white was presumable in check. It is perfectly normal to escape check by simply capturing the peice causing the check. (So long as that move does not itself place you into check from some other peice.) So turn 1 white captures the black kinkg that was causing check. On turn two he captures the second black peice (if any). One of the stalemates rules then activates - black is not in chack and black has no legal moves. Game over, draw.
Chess actually has no rule against capturing a king. It is simply an move that is normally unreachable from the standard starting postion. If we change the starting position and leave all other rules intact
There is also no rule stating that capturing the king wins the game. The game only ends by (1) loss by being in check with no legal move, (2) stalemate by triple board repetition, or (3) stalemate by non-check with no legal moves.
In fact someone who somehow has no king on the board could no longer be checkmated, and thus could never lose. We would either win by checkmating the other king, or at worst draw.
If you're going to make up a new reasonable game where someone can somehow capture a king then you'd probably want to add a rule that doing so wins the game. But the assuption was that no rules (other than starting setup) were changed or added.
-
- - You can't take something off the Internet! That's like trying to take pee out of a swimming pool.
The ko rule means that you can't just solve for all possible board positions, you also have to consider previous states of the game.
This makes things quite a lot more complicated....
The counting phase is just accomplished by filling in your own territory. The first won who has to pass loses.
Transcend Humanity. Please.
I failed to understand, before posting my comment, that the rules described are not how people play Go but rather a mathematics curiosity.
Food for thought.
fish and pipes
The fact that a programmer would even consider this a noteworthy challenge is itself a remarkable testament to the game's complexity.
Brilliant. We've discovered a new scaling effect. When you reduce a game where all the pieces begin on the board, it loses complexity more rapidly than a game which begins with an empty board where pieces can be added at will.
I get a stream of far more remarkable testaments in my spambox every day.
If two experts are playing, every sub-game will become a draw, leading to the main grid becoming a draw.
Space Lines is much more fun.
Vintage computer adverts: http://www.vintageadbrowser.com/computers-and-software-ads
Oops - fixed. Thanks for pointing that out. You almost exposed us, and then you would have been stuck searching for 3-year-old unreported geek stories too, according to the curse under which we live.
--
make install -not war
The superko rule would cover single-stone suicides. An advantage from group suicide seems very rare to me. It would seem that this rule doesn't need to be in the mathematical rules. However, it would be an easy way to cut down on brute force checking.
Transcend Humanity. Please.
Whoever moves has to. The opponent then captures and wins.
Transcend Humanity. Please.
I just happen to like Farscape. (Aeryn and Crichton are making out aboard Talyn when the ship is attacked). Aeryn: "Frell!" Crichton: "Yes" Aeryn: "No, bad frell."