This is simply not true. There have been programs that attempted to work out every possible move and counter-move to the end of the game, but these aren't successful against the best human players. Modern programs have rules of thumb to guide them.
But chess is a bad example because all the legal moves in any situation are stipulated. Much more interesting would be a poker playing program, or a car driving program. Such things exist, although admittedly not ready for prime time.
Tortoise can, and has many time, explained why the construction of a thinking machine is difficult. The difficulty involves the state of technology rather than theoretical possibility.
Not that I know of - the number of possible configurations of a chessboard is something like 10120, which is far more than can be managed in the available space or time, so the program has to prune the search tree somehow - that's where the "rules of thumb" come in. "Deep Blue", for reference, was capable of evaluating about 200,000,000 positions per second - do the math, and you'll see that the total search space is waaaayyyy out of reach. In such a case, the real trick is in the search algorithm - how "clever" the computer is about finding the best possible moves in a limited time and with limited resources, since it can't examine them all.
If, on the other hand, you want serious complexity, the number of possible moves in Go is said to be 10750, which is part of the reason that Go-playing computers, by and large, suck compared to humans - in such a game, the human facility for pattern-matching just blows the brute force of the computer right out of the game.