[babsa]

I had a conversation with a co-worker the other day while i was playing some game i had on my phone. He suggested i play chess instead whatever i had up on my phone, but i countered that i did not see the point in playing against a program because a victory would mean absolutely nothing. I understand that a phone would probably not have the computing power to beat a world league chess player, but it summoned a debate that eventually landed on the match where a human beat a supercomputer at chess. If the computer is able to process all of the possibilities, the only explanation that the human one was that the computer encountered a glitch. Is there any satisfaction that you won because a computer glitched? Or worse yet, that the computer was programmed to be limited to a few steps ahead at most?

[ummon]

Originally Posted by babsa To view links or images in this forum your post count must be 2 or greater. You currently have 0 posts.

I had a conversation with a co-worker the other day while i was playing some game i had on my phone. He suggested i play chess instead whatever i had up on my phone, but i countered that i did not see the point in playing against a program because a victory would mean absolutely nothing. I understand that a phone would probably not have the computing power to beat a world league chess player, but it summoned a debate that eventually landed on the match where a human beat a supercomputer at chess. If the computer is able to process all of the possibilities, the only explanation that the human one was that the computer encountered a glitch. Is there any satisfaction that you won because a computer glitched? Or worse yet, that the computer was programmed to be limited to a few steps ahead at most?

The computer didn't glitch. The human was just smarter than the supercomputer and played better. Though that's becoming increasingly rarer and computers are winning almost all games against humans these days.

Computers cannot process all of the possibilities in a Chess game, and thus have to rely on some estimation work just like a human player. That's how a complex game like Chess works.

Interestingly, computers are struggling to be competitive against humans when playing Go.

[thod]

Suppose the computer could see every board position 10 moves out. The question then is one of evaluating the board. This is easy to do in terms of material but much harder to do in terms of position. Thus the computer is making a subjective decision that one position is better than another. It is not able to say for certain that it is the best only that according to its algorithms it seems to be the best.

[SilentRequiem]

Originally Posted by babsa To view links or images in this forum your post count must be 2 or greater. You currently have 0 posts.

He suggested i play chess instead whatever i had up on my phone, but i countered that i did not see the point in playing against a program because a victory would mean absolutely nothing. I understand that a phone would probably not have the computing power to beat a world league chess player, but it summoned a debate that eventually landed on the match where a human beat a supercomputer at chess.

Well first point is, although the point of chess is winning you do not have to really win to progress in chess. I would argue that playing against the computer you will be faced with interesting positions that when you assess them (mid/end game) you would get a better understanding of chess. A good game is one that makes you work up a sweat, not one that ends with you winning. But that is my opinion. At the very least though, you are benefiting from the game, much more than say Angry Birds
To view links or images in this forum your post count must be 2 or greater. You currently have 0 posts.

	Originally Posted by babsa To view links or images in this forum your post count must be 2 or greater. You currently have 0 posts.
	If the computer is able to process all of the possibilities, the only explanation that the human one was that the computer encountered a glitch. Is there any satisfaction that you won because a computer glitched?

The computer cannot process all the possibilities, that is a matter of memory and computation required to do so, full state-space expansions is not fully possible for modern computers. (Do the combinatorials work, see how much possibilities you get
To view links or images in this forum your post count must be 2 or greater. You currently have 0 posts.
)

	Originally Posted by babsa To view links or images in this forum your post count must be 2 or greater. You currently have 0 posts.
	Or worse yet, that the computer was programmed to be limited to a few steps ahead at most?

There is even a worse possibility, you will see it as I progress. The computer is limited a few steps ahead, that is the way Chess AI works, but it doesn't mean that it cannot make a calculated guess. In fact the easiest way to understand Chess AI is that, the AI expands moves ahead, and then has an internal memory of the "board picture" if you want, these memories are ranked for the AI with say a weight, mostly about pieces points, positions and assessment of great chess players, stored in a database. So in short when you are playing against an AI you are playing against ALOT of the chess grandmasters, becuase they kind of tell the AI whats a better board position, once the rankings of the "board pictures" is defined. This kind of heuristics has a problem though. And you will see it soon.

	Originally Posted by ummon To view links or images in this forum your post count must be 2 or greater. You currently have 0 posts.
	The computer didn't glitch. The human was just smarter than the supercomputer and played better. Though that's becoming increasingly rarer and computers are winning almost all games against humans these days.

And here we reach the "worse" condition, its not that computer glitched, or that the human was smarter, it is more more likely that the computer let the human win, depending on difficulity an AI might not always choose the best move ahead, the AI would know of the best move ahead, but does not choose it. But despair not, there is a small chance that the human outsmarted the AI but thats a low low chance. And it is due to what we call the "Horizon Effect" (see
To view links or images in this forum your post count must be 2 or greater. You currently have 0 posts.
) but as you can see, the only way to defeat the PC is that for the human being to see ahead more than the AI is expanding, which given the growth of PCs will become much harder.

	Originally Posted by ummon To view links or images in this forum your post count must be 2 or greater. You currently have 0 posts.
	Interestingly, computers are struggling to be competitive against humans when playing Go.

Simply because Go's state space is exponentially bigger than Chess.

	Originally Posted by thod To view links or images in this forum your post count must be 2 or greater. You currently have 0 posts.
	Thus the computer is making a subjective decision that one position is better than another.

Would be pedantic and say it is not subjective as it is fully deterministic (or could be probabilstic, but still not fully subjective) to my knowledge (see Min-max).


The human mind is not designed for highly specialized processing, it is more of a broad and general, thats where the PC comes in, it is a highly specialized processing unit. Or at least it can be designed to be.
So if you want game where you might have the upper hand, try Go, or any game that uses language/context, deriving context from a sentence or something.

[froyo]

A computer cannot feasibly process all the possibilities in a chess match. You start with 16 pieces on one side. Lets assume that each piece has two move options. That's 32 possible options that the computer has to consider for the first turn. But, if it wants to look ahead at the next turn, there are another 32 possibilities. That's 32^2 total possibilities that the computer has to consider. Extend this to 10 turns, you get 32^10 possibilities! This is exponential growth. Even the most powerful computers cannot consider all this. Of course, most chess programs use various heuristics that make this number smaller, but, in a game where the possibilities can extend to hundreds of turns, it is still not feasible for a computer to have every possibility considered.

Also, humans have a very powerful intuition that a computer does not have.

[Atamagahen]

I find AIs of varying degrees to be simple.
Not sure if it's just me, but they lack human creativity and intuition. Computers and even super computers lack as much diversity that the human mind possesses. All they do is calculate what your next move may be and move only according to how you move, it's too rigid and pre-determined. This isn't a bad thing per se, but I find it much better to retain some flexibility.

[Necrosis]

Chess solutions are essentially a dynamic programming algorithm. The only problem is the state space is enormous. If your not familiar with dynamic programming, it's a way of backtracking and recursing through EVERY SINGLE possible solution.

The issue with chess is that, move 1 has 20 choices, move 2 has 360,000, move 3 has.... etc etc. The total number of possible chess games is 10^(10^50). Big number there. That being said, it's deterministic and there is nothing random or unknown about any game. It's just a matter of being able to store and use all that information. Maybe some day we will have enough computing power to do this.

On the other hand, we've done it with checkers, which of course is no where close to the size of chess
To view links or images in this forum your post count must be 2 or greater. You currently have 0 posts.


To view links or images in this forum your post count must be 2 or greater. You currently have 0 posts.

[ummon]

Originally Posted by SilentRequiem To view links or images in this forum your post count must be 2 or greater. You currently have 0 posts.

And here we reach the "worse" condition, its not that computer glitched, or that the human was smarter, it is more more likely that the computer let the human win, depending on difficulity an AI might not always choose the best move ahead, the AI would know of the best move ahead, but does not choose it. But despair not, there is a small chance that the human outsmarted the AI but thats a low low chance. And it is due to what we call the "Horizon Effect" (see To view links or images in this forum your post count must be 2 or greater. You currently have 0 posts. ) but as you can see, the only way to defeat the PC is that for the human being to see ahead more than the AI is expanding, which given the growth of PCs will become much harder.

There're reasons other than the Horizon Effect that can make a computer lose. For one, its evaluation of positions might not be as good as that of a human. Second, if the computer aggressively prunes branches of the search tree, it might neglect some promising line of play that the human notices. You see a lot of this in computer-computer matches for example, with Houdini finding all sorts of brilliancies that other programs overlook.

[Polymath20]

There are specific strategies designed to play against chess computers. While chess is a relatively small set of rules with very deterministic results, it's impossible to calculate every possibility, especially every long term possibility.

Try playing against Fritz. When you beat that, then we can talk.

[eagleseven]

Even if a computer is able to calculate every possibility, it must use a heuristic to rank the different possibilities, and any heuristic can be duped.

For instance, should the computer prefer a move that creates a more positive outcome in the short-term, or the move that has the greatest numbering of winning end-game possibilities?

If the AI goes for the short-term move, you can force it into a bad long-term decision tree with an appropriate short-term sacrifice. If the AI goes for the best long-term outcome, you can force it to expose short-term vulnerabilities.

Most human players don't have the skill to consistently pull this off against the best computers...I certainly don't. But it's still a basic limitation of AI. Games more complex than chess increasingly give the edge to human cognitive ingenuity, as the AI is forced to rely upon more heuristics.

I'd like to see a chess supercomputer used with, say, Civilization V.

[Necrosis]

Originally Posted by eagleseven To view links or images in this forum your post count must be 2 or greater. You currently have 0 posts.

Even if a computer is able to calculate every possibility, it must use a heuristic to rank the different possibilities, and any heuristic can be duped. For instance, should the computer prefer a move that creates a more positive outcome in the short-term, or the move that has the greatest numbering of winning end-game possibilities? If the AI goes for the short-term move, you can force it into a bad long-term decision tree with an appropriate short-term sacrifice. If the AI goes for the best long-term outcome, you can force it to expose short-term vulnerabilities. Most human players don't have the skill to consistently pull this off against the best computers...I certainly don't. But it's still a basic limitation of AI. Games more complex than chess increasingly give the edge to human cognitive ingenuity, as the AI is forced to rely upon more heuristics. I'd like to see a chess supercomputer used with, say, Civilization V.

Except if for every game there exists for every move some possible winning or stalemate solution, in which case, it is ALWAYS possible to win or stalemate. It won't really matter what the computer plays then. Hell he could toy with you because he knows he can win no matter what you play. *Shakes Fist*

[eagleseven]

	Originally Posted by Necrosis To view links or images in this forum your post count must be 2 or greater. You currently have 0 posts.
	Except if for every game there exists for every move some possible winning or stalemate solution, in which case, it is ALWAYS possible to win or stalemate. It won't really matter what the computer plays then. Hell he could toy with you because he knows he can win no matter what you play. *Shakes Fist*

As I said above, an AI that bases moves on the greatest long-term win/stalemate probability (greatest number of winning outcomes) will handily fall into human traps.

How so? Compare two moves, A and B. Move A gives a 65% chance of winning, while Move B gives an 80% chance of winning. Due to position strength, however, if the player makes very good moves after Move A, chance of winning fall to 60% (you can't mess up this strong position easily). In contrast, if a human detects and counters Move B, B's weak position will drop chance of winning from 80% to 40%, IE it's a high-risk position.

An AI that chooses moves based upon win/stalemate probabilities will go for the high-risk Move B every time, thus leaving it vulnerable to a creative human player. Just because it goes for the safest bet, doesn't mean you can't box it into a shitty decision branch, systematically reducing its chance calculations for win/stalemate.

[ummon]

	Originally Posted by Necrosis To view links or images in this forum your post count must be 2 or greater. You currently have 0 posts.
	Except if for every game there exists for every move some possible winning or stalemate solution, in which case, it is ALWAYS possible to win or stalemate. It won't really matter what the computer plays then. Hell he could toy with you because he knows he can win no matter what you play. *Shakes Fist*

But the computer has to know that winning or stalemate solution. Which it doesn't. Because Chess, and most other games, are too complex to search exhaustively.

[froyo]

	Originally Posted by eagleseven To view links or images in this forum your post count must be 2 or greater. You currently have 0 posts.
	Even if a computer is able to calculate every possibility, it must use a heuristic to rank the different possibilities, and any heuristic can be duped.

If a chess program has calculated every possibility, then it already knows how to win... (which I think is the point Necrosis is trying to make)

	As I said above, an AI that bases moves on the greatest long-term win/stalemate probability (greatest number of winning outcomes) will handily fall into human traps.

Except chess AIs don't really work like this. To give a simple model: A chess bot will look X moves into the future considering every possibility. From that information, it will choose its best move.

[eagleseven]

	Originally Posted by froyo To view links or images in this forum your post count must be 2 or greater. You currently have 0 posts.
	If a chess program has calculated every possibility, then it already knows how to win...

Knowing how to win at a given point, and executing that plan against a dynamic opponent, are two different things. This is true if we're talking about computers or INTJs.

	Originally Posted by froyo To view links or images in this forum your post count must be 2 or greater. You currently have 0 posts.
	Except chess AIs don't really work like this. To give a simple model: A chess bot will look X moves into the future considering every possibility. From that information, it will choose its next best move.

That's the short-term AI I described in my first post, seeking a local maximum probability of winning. I wrote a simple program that used a similar system to generate phylogenetic trees, yet it often failed to generate accurate trees because it ignored long-term maxima in favor of the low-hanging fruit, no matter how poisonous to the overall tree.

Such AI are relatively easy to dupe with sacrifices, giving it low-hanging-fruit it cannot ignore. Easier to deal with them, than the end-game-probability AI in my second example.

[Necrosis]

Originally Posted by eagleseven To view links or images in this forum your post count must be 2 or greater. You currently have 0 posts.

As I said above, an AI that bases moves on the greatest long-term win/stalemate probability (greatest number of winning outcomes) will handily fall into human traps. How so? Compare two moves, A and B. Move A gives a 65% chance of winning, while Move B gives an 80% chance of winning. Due to position strength, however, if the player makes very good moves after Move A, chance of winning fall to 60% (you can't mess up this strong position easily). In contrast, if a human detects and counters Move B, B's weak position will drop chance of winning from 80% to 40%, IE it's a high-risk position. An AI that chooses moves based upon win/stalemate probabilities will go for the high-risk Move B every time, thus leaving it vulnerable to a creative human player. Just because it goes for the safest bet, doesn't mean you can't box it into a shitty decision branch, systematically reducing its chance calculations for win/stalemate.

But you don't need a heuristic is what I'm stating. This is how they created the checkers computer that always wins. It knows everything and every solution. Imagine you played Move A and I knew a solution that guarantees I win no matter what you do.

	An average of 50 computers—with more than 200 running at peak times—were used everyday to compute the knowledge necessary to complete Chinook. Now that it is complete, the program no longer needs heuristics—it has become a database of information that "knows" the best move to play in every situation of a game. If Chinook's opponent also plays perfectly the game would end in a draw.

To view links or images in this forum your post count must be 2 or greater. You currently have 0 posts.


I have no idea if this is possible with chess. But it would be pretty crazy if it was.

---------- Post added 04-19-2012 at 09:41 AM ----------

	Originally Posted by ummon To view links or images in this forum your post count must be 2 or greater. You currently have 0 posts.
	But the computer has to know that winning or stalemate solution. Which it doesn't. Because Chess, and most other games, are too complex to search exhaustively.

I agree and I stated that. But I'm simply stating it is not theoretically impossible.

[eagleseven]

	Originally Posted by Necrosis To view links or images in this forum your post count must be 2 or greater. You currently have 0 posts.
	But you don't need a heuristic is what I'm stating. This is how they created the checkers computer that always wins. It knows everything and every solution. Imagine you played Move A and I knew a solution that guarantees I win no matter what you do.

In sufficiently complex games, there is no ideal counter to every situation. Take the starting chess board, first move. No move guarantees a win at that stage, for either player. Initial moves must be made on a heuristic or an end-game probability (your checkers AI).

Those end-game probabilities determining early moves don't take into consideration the opponent. Hence they are inaccurate and vulnerable to exploit.

	Originally Posted by Necrosis To view links or images in this forum your post count must be 2 or greater. You currently have 0 posts.
	To view links or images in this forum your post count must be 2 or greater. You currently have 0 posts. I have no idea if this is possible with chess. But it would be pretty crazy if it was.

Checkers is a comparatively simple game, and it's not particularly tricky for a kid to force you to draw every time. One of the reasons I grew bored with it, tbh.

[ummon]

	Originally Posted by Necrosis To view links or images in this forum your post count must be 2 or greater. You currently have 0 posts.
	To view links or images in this forum your post count must be 2 or greater. You currently have 0 posts. I have no idea if this is possible with chess. But it would be pretty crazy if it was.

Not even close to possible. Chess is way more complex than checkers.

	I agree and I stated that. But I'm simply stating it is not theoretically impossible.

Yes, as chess is a finite game (50 moves without a capture results in a draw iirc). However, there are some games which are open-ended, and thus it may be theoretically impossible to prove if the game can be won or not. This is because of the halting problem.

[Necrosis]

Originally Posted by eagleseven To view links or images in this forum your post count must be 2 or greater. You currently have 0 posts.

In sufficiently complex games, there is no ideal counter to every situation. Take the starting chess board, first move. No move guarantees a win at that stage, for either player. Initial moves must be made on a heuristic or an end-game probability (your checkers AI). Those end-game probabilities determining early moves don't take into consideration the opponent. Hence they are inaccurate and vulnerable to exploit.

If you have all the information available to you about every piece, every move, and every situation, you do not need any probabilities, counters or any heuristics to know whether or not you will always win. It is either possible, or it isn't. It's deterministic.

	Originally Posted by ummon To view links or images in this forum your post count must be 2 or greater. You currently have 0 posts.
	Not even close to possible. Chess is way more complex than checkers.

Theoretically it is possible. Chess is completely deterministic. It's just not feasible with the processing power we have today. Maybe 100000 years from now or maybe never
To view links or images in this forum your post count must be 2 or greater. You currently have 0 posts.


Simply put, 10^(10^50) is virtually impossible, but in theory doable. You can enumerate all possible strategies. IF AND ONLY IF, in those enumerations, there ALWAYS exists a strategy in which YOU ALWAYS WIN, then it is doable. To say it is not possible, without this knowledge just isn't true.

While we may never find out, it certainly is interesting to discuss.

[Firebrand]

It doesn't have to mean something externally to have value. If you learn something from the experience and it keeps your chops up and your brain alert, then it served it's purpose.

As far as the phone not being able to beat world class chess players, unless you're a high tournament league-level player, anything with an ELO rating of above 2000 is going to throw down a mean game. Grandmasters play on a level of about 2800 and I have one free chess engine on my phone that can pull a 2500 ELO. Less than one person out of every thousand is going to be able to beat that.

You also don't win because the program glitched. I'm not even sure where you came up with that idea.

[babsa]

I want to assure everyone that i have been keeping up with the thread since i posted it, and i enjoy the debate thus far.

Originally Posted by Firebrand9 To view links or images in this forum your post count must be 2 or greater. You currently have 0 posts.

It doesn't have to mean something externally to have value. If you learn something from the experience and it keeps your chops up and your brain alert, then it served it's purpose. As far as the phone not being able to beat world class chess players, unless you're a high tournament league-level player, anything with an ELO rating of above 2000 is going to throw down a mean game. Grandmasters play on a level of about 2800 and I have one free chess engine on my phone that can pull a 2500 ELO. Less than one person out of every thousand is going to be able to beat that. You also don't win because the program glitched. I'm not even sure where you came up with that idea.

Silly me, programs never glitch.

[ktgrey]

Exactly what is the debate at hand? The facts are pretty clear. No, a chess program does not play perfectly because it is not possible for it to calculate all the way to the end, but it calculates sufficiently far, and has a sufficiently good evaluation of end positions (along with pruning of branches that don't need to be further evaluated) that the strongest programs are 400+ ELO points higher than the best chess players, which means they stomp all over them. Given perfect play chess is almost certainly a draw, however drawing versus someone 400 ELO points higher than you is pretty difficult. Given that you have mapped out chess fully, then the game is solved.

The halting problem has absolutely nothing to do with mapping out chess as after 50 moves without a pawn move, a capture, or a promotion the game is an automatic draw. Hence any chess game will end in finite time, and the longest possible chess game is under 6000 moves.

The last I heard, a method had been worked out for playing go which scales well with computer hardware, and the best programs are of about 3-4 dan strength. This is pretty strong, although I'm not sure exactly how strong it is. My understanding is that there are 9 levels of dan ratings, and then there are 9 levels of 'pro' ratings, where a 1p is higher than a 9d, but the difference between a 1p and a 9p is about 2 dan levels (i.e. a 9p would be equivalent to about 12d). But anyway, the best go programs, like chess programs, do not play anything like human players.