The Origins of Chess

 

Supposition on Results of Man vs. Machine on Chess
by Hong Fei Teng (1,2), Yan Zhang (2), Yi Shou Wang (1), Hong Xia Zhao (2)

(1) (School of Mechanial Engineering, Dalian University of Technology, Dilian, Liaoning P.R. China, 116024)
(2) (Department of Computer Science and Technology, Dalian University of Technology, Dilian, Liaoning P.R. China, 116024)

---

Abstract: Russian Kasparov, world champion of chess, played chess with machine twice respectively in1997 and 2003, which was called ‘Man VS Machine battle’, and had attached extensive attention. The paper proposes a supposition on the results of the future ‘Man VS Machine battle’ on chess, that is, “when omniscient chess machine plays chess with man, no matter whether the machine plays antecedently or not, the result is the machine would either beat down or tie with the man, but could not necessarily win”. The supposition can be expanded to I-go(weiqi), and several corresponding deductions are presented. Key words: machine, chess, game theory, denouement, supposition

In May, 1997, the IBM company invited Kasparov, world champion of chess tournament, to Manhattan, U.S., in order to play six stanzas of chess games with 97-type “Deep Blue”(“deeper blue”) machine made by the company, which was called the ‘Man VS Machine battle’ on chess. The result was: in the first stanza, the man moved firstly, and won; the machine moved firstly in the second stanza, and won (it should have been a tie); the man moved firstly in the third and fifth stanza, the machine moved firstly in the fourth stanza, which all resulted in a tie; in the sixth stanza, the machine moved firstly, and won. Eventually, Kasparov failed at the score of 2.5:3.5.[1]

In November, 2003, Kasparov who was already 40 years old then, played another four stanzas of chess games with chess program named “X3D Fritz”. The result was: in the first stanza, the man moved firstly, and the game finished in a draw after 37 moves; the machine took the start in the secondly stanza, and won; the man moved firstly in the third stanza, he defeated his machine adversary; in the last stanza, the machine moved firstly, a tie again. Both players brought the competition to an end of 2:2, and we could not yet tell which won, and which failed.[2]

Let us make a forecast, that is, what the denouement will be if the game is to recur several years or even hundreds of years later. In other words, let us predict the denouement of chess (including both chess and Chinese chess) games played between man and machine. This issue can be seen as an algorithm problem of playing chess with machine. [3] In mathematics it is a matter of computation complexity, computability and NP-hard problem.

In order to elucidate the supposition, on the premise that the chess rules are scientific, reasonable and there are three probabilities of denouement——victory, defeat or tie, some definitions should be presented firstly:

Definition 1: chess manual information: the one which records information of the progress in a single stanza from the beginning to the end, including which chessman is involved, where the chessman is put and what effect it causes (such as taking opposing chessman, checkmate, etc) in every move, as well as the result information (victory, defeat or tie).

Definition 2: omniscient chess machine: the one which possesses of all the possible information recorded in the chess manual.

Based on the definitions above, supposition is proposed as follows:

Supposition: when omniscient chess machine plays chess with man, no matter whether the machine plays antecedently or not, the result is the machine would either beat down or tie with the man, but could not necessarily win.

In light of the supposition, three corollaries can be reduced:

Corollary 1: when omniscient chess machine plays chess with man, no matter whether the machine plays antecedently or not, the result is the man would either fail or tie with the machine, but could not necessarily lose.

Corollary 2: when omniscient chess machine plays chess with man, probability of a tie is bigger, and probability of man failure is smaller in the case that the man plays antecedently than not.

Corollary 3: when two omniscient chess machines play chess game, no matter which one plays antecedently, the result is always a tie.

A slight modification is added to above supposition, which have been published in literature, and they are used as a reference here, for the following discussion.

Till now we haven't presented theoretical validation to the supposition above, we estimate it to be a certain issue correlated with the principle which constructs a type of chess game (the algorithm is generated thereby), that is, to provide the structure of a type of chess (include the chessboard and chessman) and the rules, let the both play the game according to a tree structure, then there are two choices (correct or incorrect) in every move and three probabilities of denouement (victory, defeat or tie). The results of the ten competitions above suggest that the one that takes the initial move is likely to win. The results of another three times between man and machine are showed in Table 1, and we can’t justify that foregoer gains extra advantages just by Table 1. The above supposition couldn’t be validated in this way, because the premises are different between the both.

---

Table 1
Results of three time chess games between man and machine

Date	Two Sides	First Stanza	Second Stanza	Third Stanza	Fourth Stanza	Fifth Stanza	Sixth Stanza	Seventh Stanza	Eighth Stanza	Man vs. Machine
1996	Kasparov VS Deep Blue	MC first MC wins	MN first MN wins	MC first Tie	MN first Tie	MC first MN wins	MN first MN wins			4: 2
Oct . 2002	Kramnik VS Deep Fritz	MC first Tie	MN first MN wins	MC first MN wins	MN first Tie	MC first MC wins	MN first MC wins	MC first Tie	MN first Tie	4: 4
Jan - Feb. 2003	Kasparov VS Deep Junior	MN first MN wins	MC first Tie	MN first MC wins	MC first Tie	MN first Tie	MC first Tie			3: 3

(MC : machine; MN: man)

Attention: above information is cited in www.chende.net watching chess online (April 2003)

---

By the way, we can extend the supposition and two corollaries above analogously to I-Go, but pay attention that the numbers of chessman are also involved in games.

Now we will discuss the certain issue about the chess game denouement between man and machine, which is specially designed against the man (sir Wu Qing-yuan for example).

Definition 3: Artificial Intelligence Chess Machine (Intelligence Machine for short): it is not the omniscient chess machine, but based on the artificial intelligent technology, it is devised to defeat some specific man who has the corresponding competence level, which is called Given Adversary Man (Given Man for short).

Definition 4: Chess Competence Degree (CDD): the one demonstrates the chess competence of both sides. Let's take a basketball game as an analog, if two persons play 100 basketball games, each one wins 50 times, but the score may be different according to the accumulation, thereby the "Basketball Competence Degree" of the two sides differs.

 

Take I-Go for example, the total times of the game is n, the winning or losing numbers of machine and man I-Go in ith stanza is symbolized as G machine, G man, respectively. Black goes first and, according to Chinese rule, black must subtract standard number (180.5) and also subtract 3 3/4 from black numbers. Then we can deduce the conclusion as follows:

Surely, it can be computed by probability method, but it is omitted here.

It should be notified that present chess players would rather attach importance to being sure of success than win more chessman, so this kind of CCD is insignificant. If traditional score rules are changed, that is, we account not only times of winning or losing, but also the chessman numbers of winning, the games may be more drastic. This is also one of the important reasons why soccer games are more attractive.

Based on analysis above, more corollaries are proposed:

Corollary 4: Under the precondition that the chess rule is scientific and reasonable, Intelligence Machine plays enough stanzas with Given Man, both of them move firstly in turn, if the results of large probabilities are tie, CCD of Intelligence Machine is equal to or lower than that of Given Man.

Corollary 5: Under the precondition that the chess rule is not scientific or reasonable, Intelligence Machine plays enough stanzas with Given Man, both of them move firstly in turn, if the results of large probabilities are tie, CCD of Intelligence Machine is higher than or equal to that of Given Man.

It is necessary to make clear that whether current chess rules (especially the methods for calculating victory, defeat or tie) are actually scientific and reasonable, and moreover, how to make the rules more scientific and more reasonable is also a science problem worthy of further discussion.

---

Acknowledgements:

This work is supported by the National Natural Science Foundation of China (Granted No. 60073036)

References:

[1] May 11., 1997 - the bout between chess world champion Kasparov and "Deep Blue" (2002)
http://news.beelink.com.cn/20020511/1103081.shtml (in Chinese).

[2] Chess King couldn't conquer computer (2003): http://news.beelink.com.cn/20031119/1462382.shtml (in Chinese).

[3] Wen-qi Huang, En-ming Song & Liang Chen, (1995), An invisible Algorythm for chess Playing. Journal of Huazhong University of Science and Technology (in Chinese), 23(5):1-4.

[4] Hong-fei Teng (1997), See Future result of "Human vs. Machine Battle" in Chess from the Competition of Kasparov vs "Deep Blue". China youth and Science & Technology (in Chinese), 10:25-26

 

Author Introductions:

Hon-fei TENG is currently a professor in the School of Mechanical Engineering, Dalian University of Technology. His research interests include CAD and optimization, computational intelligence, human-computer cooperation.

Yan ZHANG is a Master candidate in the Department of Computer Science and Technology, Dalian University of technology. Her researach interests include computational intelligence and computer-assisted writing.

Yi-shou WANG is a Ph.D. candidate in the School of mechanixal Engineering, Dalian University of Technology. His research interests include layout optimization, emergency design and coputational intelligence.

Hong-xia ZHAO is a Msster candidate in the Depatment of Computer Science and Technoogy, Dalian University of Technology. Her research interests include Chinese language literature.