If there isn't currently a working algorithm to solve a chess problem and win the game, how do user-vs-computer chess games work?

Question

I was watching a video on Computational Complexity and the lecturer mentioned that "we do not current have a algorithm to allow us to win a game of chess".

If so, I'm interested in knowing how chess games/simulators work of which the user plays against the computer? Is the computer deciding on a strategic approach which is then finally chosen randomly?

Answer 1

With a computer program you can do the following:

• The program can go through all the possible moves, all possible reactions of the human, all possible counter-reactions and so on... Now each possible move can be scored by an heuristic. The program can do the move with the best expected outcome...
• The program can look in a database of all recorded chess games in the past, whether the current situation is similar to a situation in an older game. The program can do a move which leads to a win the older game.

These are just two basic algorithms the chess program might use. The first one is the basic algorithm all (most) chess programs use. See also this article.

Answer 2

Any turn-based game like chess can be viewed as a tree, where the root node is the starting position, each possible move for the first player is an arc from the root to another node, then all arcs from nodes in the second layer to positions in the third layer are initial moves for the second player, and so on. The leaf nodes at the bottom of the tree are winning or losing positions for one of the players.

To solve the game, you work the tree from the bottom up. Look at the nodes in the next-to-last layer. The player whose turn it is will naturally choose the outcome best for them, if one is available. Label each node node with the value of the child node that is most favorable for the current player. Then go up a layer and do it again for the other player. This technique is called a minimax search. Eventually you find out that either the first player has a move that guarantees a win, or the second player is guaranteed a win no matter which move the first player chooses.

The game tree for chess is too big to practically do this from the start, so the game tree is only partially calculated. Instead of known win/loss states, the nodes at the bottom of the tree are labeled with a heuristic value (how many pieces does each player still have, how many pieces are under attack, who controls the center squares, how restricted is your king, etc) that estimates the advantage one player or the other holds from that point. Then you minimax your way up from the bottom again to find the move that leaves you in the best available position. Each node will be labeled with a heuristic value instead of a win/loss boolean. in the end, the current player should make the move with the best heuristic value for them.