This car is smarter than me

In which games a person will never win a computer

At the end of 2015-early 2016, computer programs turned out to be more capable of people in the game GO and in the speed of collecting the Rubik cube . At the request of Medusa, journalist Vladislav Voronin tells what games a person can never win with the computer.

Othello (Reversee)

The game "Othello" became popular in the early 1970s. The rules are simple: two players freely place chips of different colors on a site of 64 cells (8 × 8). The task is to close on both sides the continuous rows of the opponent (horizontal, vertical and diagonal) with their chips. As soon as the row is blocked, all the chips in it cross the opponent and change the color. The one who took a large territory by the end of the party wins.

During the first fight of a person with a computer in 1980, the current world champion in Othello, Hiroshi Inoue, confidently won: out of six games, he lost only one (5: 1) program. In just nine years, computers took revenge in the team tournament in London. Five programs beat five professional players (three of them were included in the world top-4) with a modest score of 12: 8.

Over time, information about all possible positions of chips was placed in computers, and the cars began to calculate the game about 25 moves ahead - in fact, a powerful strategy without weaknesses appeared.

Already in 1997, it became clear that even the strongest players are pointless to compete with computers: the world champion Taesy Murakami lost the Logistello program with a humiliating score of 0: 6.

Backgammon

Computers learned to play backgammon back in the 1970s, but this would certainly not have happened without the influence of chess. For developers of supercomputers who are able to fight chess cresters, this game turned out to be a small intermediate stage. For example, the world chess champion Hans Berliner, using NARD, came up with an algorithm for assessing the situation on the gaming board (the computer analyzes the current situation on the board and views the tree of the game several moves in order to choose the optimal continuation); This later helped him write the chess program HITECH, which in 1988 defeated Grossmaster Arnold Denker.

For Nard, Berliner developed the BKG 9.8 program, in 1979 she beat the current world champion Luigi Villa with a score of 7: 1. The victory was extremely unexpected, even the creator of the computer admitted that a person acted more talented and more stable - the system chose not the best options for continuing the game eight times. But, firstly, the BKG 9.8 several times was lucky with the numbers that fell on the bones, and secondly, the program very successfully made a choice in favor of a doubling of bets (each game begins with a rate of one point; if desired, each participant can double the bet-the second should either accept this doubling, or lose one point without risking two).

Later, the Berliner method (analysis of the situation in the game field) was improved. The work of the Swiss program Snowy and Finnish Jellyfish is based on artificial neural networks that remember the moves of the best players and use them if necessary. True, after the defeat of the villa, none of the champions dared to fight the computer.

Chess

The IBM company has been interested in chess systems since the beginning of the 1950s, but due to the complexity of the game, development has taken a lot of time. Only after 30 years, scientists thought about the project of a powerful Deep Blue computer. Harry Kasparov turned out to put him against the current world champion in 1996.

That match of six parties Kasparov won (3 victories, 2 draws, 1 defeat), he was sure that the era of cars would come soon: “Although I saw some signs of intelligence, the computer still had an ineffective and inflexible manner of playing. This allows me to think that I have several years in reserve, ”he wrote in Time magazine.

However, Kasparov was mistaken. The developers quickly increased the power of the system - now it could evaluate 200 million positions per second. In 1997, Deep Blue defeated the match-match (2 victories, 3 draws, 1 defeat) and became the first computer to overcome the strongest chess player in the world. Kasparov could no longer win back, because IBM refused further competitions, considering the mission of the executed.

Since then, computers have become only stronger. Elo rating (method of calculating the relative power of players in games for two) the strongest chess program Stockfish is 3341 points. People's indicators are significantly lower : Kasparov had 2851 points at the peak, the current leader of Magnus Karlsen - 2850.6.

Go

The ancient game, invented in China more than two and a half thousand years ago, seemed an insurmountable obstacle for computers until Google took up development. At first glance, there is nothing particularly complicated in the GO: two players take turns arranging white and black stones on the site (19 × 19); The wins are the one who seizes a large territory. At the end, stones that make up the border of the same color are considered, and free cells behind the “wall”, where other stones can be freely added. Who has more, he won.

Difficulties in the variety of options. For example, in chess, each player has 20 ways to start a batch, and after the first move on the board there can be 400 different positions. In GO - 361 options for the starting passage and 129,960 possible combinations only after the first round. This incredibly complicates the work of artificial intelligence systems that rely on standard algorithms and databases.

Therefore, the Alphago system, developed under the control of Google, combines two approaches - the so -called “Wood of Options” and deep neural networks, which are trained by 30 million strokes of the strongest players in the GO and thousands of parties inside the system. Now Alphago in 57% of cases predicts human actions.

When testing, Alphago destroyed the most progressive computer state systems, having won 499 out of 500 parties from them. Then the time came to meet with a person, and in October 2015, Alphago defeated the three-time European champion Fan Huya with a score of 5: 0. This is the first computer victory over a professional player in the GO - before that, not a single program rose above an amateur level.

To finally conquer GO, Alphago remains to prove strength in the match with the strongest player in the world Lee Sedol. The meeting is scheduled for March.

Rubika cube

In January, the inventors of Jay Flandland and Paul Rose introduced a robot that could collect a Rubika cube in just a second. This is a cosmic level even for computer systems - before, not one of them managed to cope with a puzzle in less than 3.253 seconds. The best result of the Flatland and Rose is 1.047 seconds.

The car works with a slightly modified chubby cube: on each edge in the center, holes are drilled, behind which walking electric motors are held. With the help of four webcams, the computer evaluates the current layout of the cube and determines the optimal sequence of actions based on the Coema algorithm (solution for no more than 20 moves).

The best result among people in November 2015 was shown by the 14-year-old American Lucas Etter-4.904 seconds.

Checkers

The fairy -tale story of the American Marion Tinsley, who lost to the rivals in the checks (a variety of checkers), only five parties ended with a meeting with a computer. He was the world champion throughout his career from 1955 to 1991; With a break of 17 years, when he missed all tournaments.

The checking system was developed at the Canadian Albert University. The car weighed about 540 kilograms and per minute could process 12 million different game options. In 1992, Chinook deserved a meeting with Tinsley, but the match remained with the person: 4 defeats of the program, 2 victories, 33 draws. It is interesting that once the program lost only because of technical problems-the computer was simply hung , and the developers had to give up.

Already in 1994, a match was held. In the first six batches there were continuous draws, and then Tinsley starred due to health problems-the victory automatically got the computer. A week later, the champion found cancer; In less than a year, he died.

Since then, computers have gained such power that people are unlikely to compete with them. In 2007, Canada announced the creation of an ideal system that cannot lose at all. Even if her opponent holds an impeccable match, he will get a draw at best. The program analyzed all possible options for the development of the game and knows the perfect move in every situation.

Screbble

The screbble, known in Russia as “Erudite”, was submitted to the computer on the first attempt. In 2006, Toronto Robot Quackle defeated the world champion David Boyce.

In two starting parties, the program lost - to beat a person, it was necessary to take the next three, using unusual words like “cadi” (a judge considering the matters based on Sharia) and “anuria” (lack of urine intake into the bladder).

Before fighting a computer, Boyce in a special tournament went around 100 others. Having lost to the robot, he noted with a disorder that "it is still better to be a person than a computer."

Quackle is available on the Internet, so you can also compete.

Telester

The IBM company, which developed a supercomputer, who beat Harry Kasparov, surprised humanity again in 2011 - this time in the intellectual television scientist Jeopardy! (Russian analogue - "its own game"). The Watson robot did not leave any chances to two record holders: Ken Jennings, who at one time did not lose for 74 program issues, and Brad Rutter, who received the largest gain in the history of the show - $ 4.45 million.

The robot recognized the leader’s speech, analyzed the question and looked for the answer in the database. The computer was not connected to the Internet and could not use third -party services, it had only 200 million content pages on a variety of topics, including the full broadcast of Wikipedia.

By the sum of two Watson games, the correct answers earned 77 thousand dollars, more than three times overthrowing each opponent - 24 thousand at Jennings and 21,600 - from Rutter.

As a result, IBM won a million dollars. All money was aimed at charity.

Vladislav Voronin

Moscow