>"BLUE" was reprogrammed DURING the games. Humans >were adjusting the program based on how the >match was going. >"BLUE" was not MAN vs MACHINE, but MAN vs A >PUPPET.
I wonder why it's so essential for the thing to have been 'reprogrammed' (in reality most likely simple adjustments to the evaluation weights) to have been a 'puppet'.
It was man-made, with algorithms and strategies that were taught to it by humans. And it was a computer. Me flipping a switch in the options of my chessprogram doesn't suddenly make the program more human.
Unfortunately, it will work only once. Any recent computer has book learning and will avoid the opening next time. Also, take into account Nemeth _takes back_ moves until he gets a winning position. That is, by all means, cheating.
The trojan horse attack he mentions is useless nowadays; the programs are either programmed to understand or avoid it.
I think you got the right idea, but some parts of your post are worded rather, eh, problematic:
>Let's get back to your decision tree: at any >given moment, the trees branching off from each >possible move probably contain *both* winning >*and* losing outcomes.
The game state you are in at any given moment is either win, loss or draw.
If it's win, you will have at least one move that guarantees a win. The others can be a mixture of losses, draws.
If it's drawn, you will have at least one move that forces a draw. You cannot have moves that force a win for you, but you can have moves that lose.
If it's a loss, all moves you have are losses.
>You can't "eliminate every move which doesn't >lead to my victory", because there is no >immediate next move which *always* leads to >victory.
True if the game state is a draw or loss, not if it's a win. (we don't know what the starting position is)
>Ok, so you minimize the risk. Say, you count how >many of the possible outcomes are losses and how >many are wins for any particular move,
This doesn't make sense. If you have outcomes that are wins, the position is won, and you can always pick a winning move.
>Even if you know every possible combination, >theres no way to control where the other person >will move.
If you have solved the game and are playing the side that wins or draws by the solution, you can always play a move that leads to a position where even his best most draws at most.
>If you honestly believe Krammik stands a chance, >you must not have seen the games with deep blue.
The Kasparov match was close, and there's no real evidence that Fritz is stronger than Deep Blue, despite what is claimed (I believe exactly the opposite myself).
The programmer of Fritz, Frans Morsch, commented in a computerchess-magazine that he did not believe Fritz would win a single game.
>The number of possible chess games isn't known >excatly [wolfram.com], but since even the lower >estimates approach the number of atoms in the >known universe we will be waiting a long time >for enough processing power and memory to >enumerate every possible game!
I intentionally avoided using the word impossible because there is no way to tell what someone comes up with next.
For example, 4-in-a-row was partly solved by brute forcing all possibilities, but they avoided searching a great deal of positions by devising certain rules which allowed them to quickly identify whether or not a position was winnable.
Something just as simple is not applicable to chess, but maybe something else we don't know yet is.
Perhaps someone will invent a method to store information in quarks:)
>What I'd like to see is Kramnik, Deep Blue, and >Fritz vs. Kasparov, Deep Blue, and Fritz. >Basically, the grandmaster can use the computer >to explore possibilities and make calculations, >but ultimately the move decision is his.
This is commonly called 'Advanced Chess'. Do a search on Google and you'll find some interesting matches.
>That was very informative- thank you. Do you >have links to the programs you wrote, or are >they in commercial software?
You can get them from the link in the header of my post, or look around on the site that slashdot linked to (chessbase.com), in the downloads-uci engines section.
>Kramnik says that the Fritz 7 program on a >laptop is producing some better moves than Deep >Blue did against Kasparov.
Unfortunately, that's a completely invalid way of judging a computers playing strength.
You can have a program that does very well on a few isolated positions, but sucks in real games, because it may have a weakness that didn't figure in those positions, but that can easily be exploited.
If you would test a program in positions where the theme is attacking the king, the newest ones would do very well. Put them in a position where the goal is to maneouver strategically, and they will look like patzers.
Don't forget there are PR reasons for Kramnik to claim that too...
>From someone who has played them, how does Chess >compare to Go or Shogi in terms of depth and >style of play?
I've played all three and written strong programs to play two of them, but this still is a hard question.
Go is by far the deepest. The current top programs play at the level of a (rather weak) club player. It's got a huge branching factor (number of possible moves) which makes any brute or semi-brute force appraoch (what is used for chess) impossible. Most programs around right now are based on pattern recognition.
Funny thing is, the game is by far the simplest. John Tromp (the guy that wrote the 'shorter turing machine' that was posted to/. a few weeks ago) designed a complete ruleset that's only a few lines long. In practise, there are many rulesets, most of them because of tradition. This is somewhat problematic when making a program, because some rulesets are simply not complete.
Playing go is a very nice mixture of tactics and strategy. One other thing that's very nice about it is that there is a very good handicap system. The games can always be close, even against much stronger players.
Chess, well, it's mostly about tactics. Of course positional understanding matters a lot, but it's actually rather insignificant compared to the tactical part. Mostly due to continious small advances in technique and hardware, we've now got programs that are able to search about 16 half-moves (move by one side) deep. That'll nearly always take care of the tactical part. Programming strategical understanding is much harder, but a lot of progress is being made in the latter. Especially the latest generation of programs took a big step forward. We've got computers that can successfully compete with the very best humans.
Shogi I've only played once, but I've been working a lot on a chess variant that behaves like Shogi in the past. (captured pieces can be dropped) It's got almost double the branching factor of chess, and hence is somewhere halfway between go and chess. The big issue with it is that it is also very tactical, unlike go. Even though the brute force depth of current programs isn't great, they can extend mating lines very well. And mates are important in shogi/dropchess:) I would have to check for the current state of the art, but I believe the top programs are quite competitive here.
>If you remember - for a long time no professional chess player would play a computer.
This is just false...there have always been human-computer matches.
The lack of matches with world champions can be simply explained by the fact that those world champions charge much more for such a match than most chessprogrammers can afford.
Depends. If his title is 'world chess champion', then it is correct, isn't it? Considering there are several world champions in chess (each one claiming he's the real one), it makes sense to make the distinction.
Kasparov sent out a reaction shortly afterwards claiming that Kramnik's statement that Fritz is better than Deep Blue is nonsense.
There's some PR involved here. If Kramnik wins, he wants to look good, so saying Fritz is better than Deep Blue makes him look better. For Kasparov, it's just the opposite.
Whether or not Fritz is actually better than Deep Blue is a matter of endless discussion even among computerchess experts. And we'll never know the answer, because Deep Blue no longer exists.
>Given an infinite amount of processing power and memory, could someone "solve" the game of chess?
Yes. You can even argue it's solvable by an O(1) algorithm, similar to what you describe.
>If so, could someone use techniques such as genetic programming or neural networks to learn the lookup table in a finite amount of time/space?
There's only a limited number of positions. You can enumerate them and then 'solve' the game in the same way we generate endgame tablebases. But we lack storage and processing power for many many many years to come.
>Is the problem that some people are too stupid to figure out how to copy and paste in X?
Well, after 5 years of Unix usage, I must admit I don't understand it. Sometimes it works, sometimes it doesn't. Mozilla/Netscape and Emacs are particularly nasty offenders. I often have trouble pasting to/from them.
>Nobody is going to fit an expensive and battery draining processor into their product just to support an extreme minority codec.
>By using floating point for the algorithms, libvorbis is ruled out from nearly all embedded >devices. At the moment it pretty much only runs (in real time) on PC/Mac systems.
The way you state this sounds like as if Vorbis can't be done with integer-only artihmetic, which is false.
The reference implementation uses floats, because it makes the code easier to understand (that's what the article indirectly is about!), but there's no reason why you can't have integer decoders (and they already exist...)
>Instead of making everyone pay for NASA, those >who care most about it also fund it the most.
Hmm, this is a dangerous way of reasoning. I suppose your country has at least some kind of system that helps homeless people, unemployed, orphans, etc...
Most/many people with homes and jobs won't really care about them. So they shouldn't pay, according to your reasoning. Let the homeless and unemployed pay, eh, for themselves.
You can argue that NASA is luxury, that we don't need their research. Perhaps. There's no way to know what we are going to find up there. Moreover, NASA developed a lot of stuff that is in common use today.
Yes, but a huge difference from a per-copy fee. It's a small one-time cost. As an example, one of Epic Games's developers bought copies of VS.NET for some Vorbis developers. It was a one-time cost for them. Much cheaper than to license MP3.
Same thing for portable players. A small one-time cost vs. paying Fraunhofer for *every player sold*.
>Very wrong indeed, you appear to be confusing what >you hope will happen in the future with what is the >case now, this doesn't benefit anyone.
Sorry, the libs *and* players are available *right now*.
Unlikely they use Vorbis for this; it isn't very fast for compressing (or rather, the standard encoder isn't yet), and there are better algo's out there for pure voice.
>People still use MP3 because there are >pocket-sized MP3 players, and there are >pocket-sized MP3 players because efficient MP3 >decoder software that uses fixed-point (integer) >arithmetic is widely available. The reference >Vorbis decoder still uses floating-point >arithmetic, which common ARM microprocessors cannot >do in real time.
Portable players are available, as well as an official integer-based decoding lib (it needs to be licensed, but it's a small *one-time* fee. There's a totally free one being developed on sourceforge too I believe).
Slashdot Mirror
>"BLUE" was reprogrammed DURING the games. Humans
>were adjusting the program based on how the
>match was going.
>"BLUE" was not MAN vs MACHINE, but MAN vs A
>PUPPET.
I wonder why it's so essential for the thing to have been 'reprogrammed' (in reality most likely simple adjustments to the evaluation weights) to have been a 'puppet'.
It was man-made, with algorithms and strategies that were taught to it by humans. And it was a computer. Me flipping a switch in the options of my chessprogram doesn't suddenly make the program more human.
--
GCP
Unfortunately, it will work only once. Any recent computer has book learning and will avoid the opening next time. Also, take into account Nemeth _takes back_ moves until he gets a winning position. That is, by all means, cheating.
The trojan horse attack he mentions is useless nowadays; the programs are either programmed to understand or avoid it.
--
GCP
I think you got the right idea, but some parts of your post are worded rather, eh, problematic:
>Let's get back to your decision tree: at any
>given moment, the trees branching off from each
>possible move probably contain *both* winning
>*and* losing outcomes.
The game state you are in at any given moment is either win, loss or draw.
If it's win, you will have at least one move that guarantees a win. The others can be a mixture of losses, draws.
If it's drawn, you will have at least one move that forces a draw. You cannot have moves that force a win for you, but you can have moves that lose.
If it's a loss, all moves you have are losses.
>You can't "eliminate every move which doesn't
>lead to my victory", because there is no
>immediate next move which *always* leads to
>victory.
True if the game state is a draw or loss, not if it's a win. (we don't know what the starting position is)
>Ok, so you minimize the risk. Say, you count how
>many of the possible outcomes are losses and how
>many are wins for any particular move,
This doesn't make sense. If you have outcomes that are wins, the position is won, and you can always pick a winning move.
--
GCP
>Even if you know every possible combination,
>theres no way to control where the other person
>will move.
If you have solved the game and are playing the side that wins or draws by the solution, you can always play a move that leads to a position where even his best most draws at most.
--
GCP
>If you solve the game of chess the best you
>could do is make every chess game a draw.
This assumes chess is a draw. We don't know if that's true (but it's likely).
>just follow the classic e4-d4 openings and 90
>percent of the time, your games will be a draw
>if you play with someone of equal skill.
The true number is much smaller. Equal strength does not guarantee a draw, just an equal score over an infinite number of games.
--
GCP
>If you honestly believe Krammik stands a chance,
>you must not have seen the games with deep blue.
The Kasparov match was close, and there's no real evidence that Fritz is stronger than Deep Blue, despite what is claimed (I believe exactly the opposite myself).
The programmer of Fritz, Frans Morsch, commented in a computerchess-magazine that he did not believe Fritz would win a single game.
--
GCP
>Would you call "Go" a game of tactics?
Try getting a *solid* definition of 'tactics' vs. 'strategy' and see if there's sense to the question.
--
GCP
>The number of possible chess games isn't known
:)
>excatly [wolfram.com], but since even the lower
>estimates approach the number of atoms in the
>known universe we will be waiting a long time
>for enough processing power and memory to
>enumerate every possible game!
I intentionally avoided using the word impossible because there is no way to tell what someone comes up with next.
For example, 4-in-a-row was partly solved by brute forcing all possibilities, but they avoided searching a great deal of positions by devising certain rules which allowed them to quickly identify whether or not a position was winnable.
Something just as simple is not applicable to chess, but maybe something else we don't know yet is.
Perhaps someone will invent a method to store information in quarks
--
GCP
>What I'd like to see is Kramnik, Deep Blue, and
>Fritz vs. Kasparov, Deep Blue, and Fritz.
>Basically, the grandmaster can use the computer
>to explore possibilities and make calculations,
>but ultimately the move decision is his.
This is commonly called 'Advanced Chess'. Do a search on Google and you'll find some interesting matches.
--
GCP
>That was very informative- thank you. Do you
:)
>have links to the programs you wrote, or are
>they in commercial software?
You can get them from the link in the header of my post, or look around on the site that slashdot linked to (chessbase.com), in the downloads-uci engines section.
There are free and Free versions
--
GCP
>Kramnik says that the Fritz 7 program on a
>laptop is producing some better moves than Deep
>Blue did against Kasparov.
Unfortunately, that's a completely invalid way of judging a computers playing strength.
You can have a program that does very well on a few isolated positions, but sucks in real games, because it may have a weakness that didn't figure in those positions, but that can easily be exploited.
If you would test a program in positions where the theme is attacking the king, the newest ones would do very well. Put them in a position where the goal is to maneouver strategically, and they will look like patzers.
Don't forget there are PR reasons for Kramnik to claim that too...
--
GCP
>From someone who has played them, how does Chess
/. a few weeks ago) designed a complete ruleset that's only a few lines long. In practise, there are many rulesets, most of them because of tradition. This is somewhat problematic when making a program, because some rulesets are simply not complete.
:) I would have to check for the current state of the art, but I believe the top programs are quite competitive here.
>compare to Go or Shogi in terms of depth and
>style of play?
I've played all three and written strong programs to play two of them, but this still is a hard question.
Go is by far the deepest. The current top programs play at the level of a (rather weak) club player. It's got a huge branching factor (number of possible moves) which makes any brute or semi-brute force appraoch (what is used for chess) impossible. Most programs around right now are based on pattern recognition.
Funny thing is, the game is by far the simplest. John Tromp (the guy that wrote the 'shorter turing machine' that was posted to
Playing go is a very nice mixture of tactics and strategy. One other thing that's very nice about it is that there is a very good handicap system. The games can always be close, even against much stronger players.
Chess, well, it's mostly about tactics. Of course positional understanding matters a lot, but it's actually rather insignificant compared to the tactical part. Mostly due to continious small advances in technique and hardware, we've now got programs that are able to search about 16 half-moves (move by one side) deep. That'll nearly always take care of the tactical part. Programming strategical understanding is much harder, but a lot of progress is being made in the latter. Especially the latest generation of programs took a big step forward. We've got computers that can successfully compete with the very best humans.
Shogi I've only played once, but I've been working a lot on a chess variant that behaves like Shogi in the past. (captured pieces can be dropped) It's got almost double the branching factor of chess, and hence is somewhere halfway between go and chess. The big issue with it is that it is also very tactical, unlike go. Even though the brute force depth of current programs isn't great, they can extend mating lines very well. And mates are important in shogi/dropchess
--
GCP
>If you remember - for a long time no professional chess player would play a computer.
This is just false...there have always been human-computer matches.
The lack of matches with world champions can be simply explained by the fact that those world champions charge much more for such a match than most chessprogrammers can afford.
--
GCP
Depends. If his title is 'world chess champion', then it is correct, isn't it? Considering there are several world champions in chess (each one claiming he's the real one), it makes sense to make the distinction.
--
GCP
Kasparov sent out a reaction shortly afterwards claiming that Kramnik's statement that Fritz is better than Deep Blue is nonsense.
There's some PR involved here. If Kramnik wins, he wants to look good, so saying Fritz is better than Deep Blue makes him look better. For Kasparov, it's just the opposite.
Whether or not Fritz is actually better than Deep Blue is a matter of endless discussion even among computerchess experts. And we'll never know the answer, because Deep Blue no longer exists.
--
GCP
>Given an infinite amount of processing power and
memory, could someone "solve" the game of chess?
Yes. You can even argue it's solvable by an O(1) algorithm, similar to what you describe.
>If so, could someone use techniques such as
genetic programming or neural networks to learn the lookup table in a finite amount of time/space?
There's only a limited number of positions. You can enumerate them and then 'solve' the game in the same way we generate endgame tablebases. But we lack storage and processing power for many many many years to come.
--
GCP
>Is the problem that some people are too stupid to figure out how to copy and paste in X?
Well, after 5 years of Unix usage, I must admit I don't understand it. Sometimes it works, sometimes it doesn't. Mozilla/Netscape and Emacs are particularly nasty offenders. I often have trouble pasting to/from them.
--
GCP
>clearly defined standard before they finish writing it? In my opinion, that is why it has not
>yet been implemented in portably audio players.
False. The 1.0 decoder is finalized since RC1, so you could write the specs needed for a decoder right now.
--
GCP
This is somewhat besides the point, but in case noone had noticed, the latest Winamp 2.80 ships with Vorbis support by default.
:)
This is very nice because:
a) no more explaining how to install plugins to less-literate users
b) it seems that the legal team of AOL considers Vorbis to be patent-safe (they looked into the matter, which is why this lasted so long)
c) some of the WinAmp developers have become Vorbis freaks
--
GCP
>I mean, mp3 is short, catchy, easy to remember, and doesn't sound dumb to people that aren't techie.
Admit it, you don't know any people that aren't techie, do you?
--
GCP
>Nobody is going to fit an expensive and battery draining processor into their product just to support an extreme minority codec.
>By using floating point for the algorithms, libvorbis is ruled out from nearly all embedded
>devices. At the moment it pretty much only runs (in real time) on PC/Mac systems.
The way you state this sounds like as if Vorbis can't be done with integer-only artihmetic, which is false.
The reference implementation uses floats, because it makes the code easier to understand (that's what the article indirectly is about!), but there's no reason why you can't have integer decoders (and they already exist...)
--
GCP
>Instead of making everyone pay for NASA, those
>who care most about it also fund it the most.
Hmm, this is a dangerous way of reasoning. I suppose your country has at least some kind of system that helps homeless people, unemployed, orphans, etc...
Most/many people with homes and jobs won't really care about them. So they shouldn't pay, according to your reasoning. Let the homeless and unemployed pay, eh, for themselves.
You can argue that NASA is luxury, that we don't need their research. Perhaps. There's no way to know what we are going to find up there. Moreover, NASA developed a lot of stuff that is in common use today.
--
GCP
>As in not free then.
Yes, but a huge difference from a per-copy fee. It's a small one-time cost. As an example, one of Epic Games's developers bought copies of VS.NET for some Vorbis developers. It was a one-time cost for them. Much cheaper than to license MP3.
Same thing for portable players. A small one-time cost vs. paying Fraunhofer for *every player sold*.
>Very wrong indeed, you appear to be confusing what
>you hope will happen in the future with what is the
>case now, this doesn't benefit anyone.
Sorry, the libs *and* players are available *right now*.
--
GCP
Unlikely they use Vorbis for this; it isn't very fast for compressing (or rather, the standard encoder isn't yet), and there are better algo's out there for pure voice.
--
GCP
>People still use MP3 because there are
>pocket-sized MP3 players, and there are
>pocket-sized MP3 players because efficient MP3
>decoder software that uses fixed-point (integer)
>arithmetic is widely available. The reference
>Vorbis decoder still uses floating-point
>arithmetic, which common ARM microprocessors cannot
>do in real time.
Portable players are available, as well as an official integer-based decoding lib (it needs to be licensed, but it's a small *one-time* fee. There's a totally free one being developed on sourceforge too I believe).
Your arguments no longer hold nowadays.
--
GCP