Scheduled to kill

2010/02/01 Roa Zubia, Guillermo - Elhuyar Zientzia Iturria: Elhuyar aldizkaria

• Adimen artifiziala
• Softwarea

(Photo: Guillermo Roa)

There is a perfect way to play chess. The movement sequence of the pieces is optimal, since with this sequence there is no danger of losing the game. However, there is a problem: no one knows what the perfect sequence is.

The game theory, a branch of mathematics, proved long ago that it exists, but the complexity of chess has prevented mathematicians from going beyond. They do not know if that sequence leads to win or to tie. The match is perfect, but no one knows who it is. This is good news for chess players.

However, computer scientists have advanced a lot. At present, chess software is not based on mere calculation, but has been integrated within the framework of the strategy. "It evaluates the locations of the pieces according to a strategic criterion, analyzing different characteristics: endrokes, the location of the pawns, if there are open diagonals for parades, etc. ", explains Antonio Salmerón, computer scientist of the University of Almería. "Of course, then you have to use the calculation to know if the move has led or not to an incorrect situation. But, basically, the strategy orients the computer game."

Human Strategy Human Strategy

The strategy also guides the game of human players. At the base, as in a battle of a war, he tries to take control of the zone; in chess, to dominate the center of the board is to take control of the zone, both of the location of the pieces, and of the central zone from other locations. Once achieved, the game is well oriented. And to achieve this you have to use the strategy.

The strategy itself is difficult to define. It works at many levels and covers many factors. For example, the use of strategy involves making decisions, making movements to deceive the other, measuring the benefits of exchanging parts (sacrificing one piece to eat another to the enemy), entering into attack with more than one piece, etc. And that's more than calculating the moves and the opponent's response.

Some great teachers say that you can play chess without making any calculations and with a pure strategy. "I think that is to say too much, but at least it indicates the importance of the strategy regarding calculations," says Salmerón.

Antonio Salmerón (Almería, 1971). Computer. He is Professor of Statistics and Operational Research at the University of Almería. Expert in artificial intelligence and chess. José Cuena Prize at the Congress of the Spanish Association of Artificial Intelligence 2001, CAEPIA'2001. And Bayes is the director of the development project of chess software Chess. He is also a chess player: In 2005 he was Champion of Almeria for teams with the team Alboran, member of the Revert University of Almeria, and in 2008 he was Champion of Andalusia in Honor. Ed. : José Miguel Puerta.

Computer strategy

In fact, in recent years chess software has advanced in this, adding to programming a strategic perspective.

"From a computer point of view, chess is a search problem. We have to look for the most appropriate motion sequences that lead to maximum benefit," says Salmerón. There are known algorithms that do so, such as Minimax. The computer builds a tree of possible moves but not entirely, detects and does not develop branches that direct Minimax algorithms to unfavorable results. This avoids many unnecessary calculations. It is a basic strategy. However, current software uses much more refined strategies than Minimax.

"For this purpose artificial intelligence is necessary," says Salmerón. The computer learns to play through very complex algorithms, analyzing the databases of chess games.

There are many techniques for this. Antonio Salmerón and his companions, for example, have applied to the problem of chess the idea of bayegas networks. It is a mathematical representation of a probability distribution from a set of variables. In the case of chess, this representation indicates to the computer which moves are directed towards a good result and which are not.

"On the one hand, it is a means to learn from the databases of the games played by human players and, on the other, it helps to discover how the player in front is." In the base there are three types of players: the aggressors, the position and the intermediate ones. "We want the computer to act as a human being, that is, when it opposes an aggressive enemy, it adopts a position and vice versa. A player doesn't feel comfortable when he forces him to play an opposite type of game."

Deep Blue Deep

Using artificial intelligence techniques, computer scientists have managed to make the machines work perfectly. "Currently chess programs have more strength than almost any player," says Salmerón. It is not too long for IBM's Deep Blue computer and player Gari Kasparov to tackle, in 1996 for the first time and in 1997 five more games were played. The second match was won by Deep Blue, the first time a computer won against a great master. The computer had a large computing capacity, but it also used the strategy.

(Photo: © George Mayer/123 RF)

Since then there is no doubt about the ability of computer chess. However, during those matches there was much talk about the Turing test. It was an old idea of artificial intelligence. In the 1950s, English Alan Turing claimed that machines would soon be able to imitate humans in terms of intelligence. Therefore, he proposed a test to be able to differentiate a machine from a person through an interview. And being so close to the world of chess in the field of artificial intelligence, many proposed completing a Turing test through chess, a test that allowed differentiating a machine or a person depending on how a player played a chess game.

When Deep Blue won Kasparov the doubt arises whether this Turing test with chess would be possible or not. After the second match, Kasparov indicated that Deep Blue had not played as a computer. He was compared to a human player.

However, since then, chess programs have greatly improved. Improvement of programming and improvement of computers. As a result, the situation has changed radically. "Today there are very advanced programs for the home computer, which can be purchased at 50 or 60 euros," says Salmerón. "They are programs that win almost anyone. They are normally used by chess players to train."

The best known program is Fritz, a very common commercial software today. Fritz, although he wins most of the matches -- with complicated strategies -- does not behave like man. In the Turing test it would be clearly seen that it is a program. "That's why these programs are not attractive, they have too much capacity, they always win and are also very monotonous. They always earn the same," says Salmerón. "That is, in my opinion, the challenge of programmers: to humanize this game. I don't like to play against a current chess program."

This is the goal of companies that perform chess programs. The theme of the strategy may not have reached the ceiling, but it has reached a very high level. About. But now they want to develop a game similar to the human game, not to overcome a test, but to give it vitality. There is still a lot left for computers to think like humans, even in chess.

Value parts

It is not the same a tower as a bishop. The first is more powerful than the second, but how much? Computer users work numerically and must quantify these values. Thus, there is a scale of values for the pieces: the pawn is assigned the value 1, the horse the value 3, the pin the value 3, the tower the value 5 and the queen the value 9. These values depend on the mobility of the piece and the possibilities it offers. But these values are not enough to program chess.

If a horse is in a corner of the board, you can only move to two sites in one move. If you are in the center of the table you can jump to eight places. And depending on the location of the other pieces, their location in a given place may have greater or lesser value.

(Photo: Guillermo Roa)

Therefore, along with the intrinsic value of the piece, programmers use an array of 8 x 8 dimensions per piece. Each element of the matrix corresponds to a box of the table. A negative value can also be given to the tables. For example, in order to try to get the horses out at the beginning of the match, the negative value is given to the horse's own box. In this way you can numerically direct the game.

However, the matrices and values of the pieces do not define a player's strategy. For this it is necessary to perform an analysis beyond the numbers.