毕业设计-网络五子棋的外文翻译

Renju is a very old two-player board game with subtle tactics and strategies. It comes from Japan and is a professional variant of Go-Moku. In many countries, such as China, Estonia,

Japan, Latvia, Russia, and Sweden, Renju is played on a high level of performance.

Compared to Renju, the game of Go-Moku, mainly played in China and Japan, has rather simple rules. Go-Moku was solved by Allis in 1992. He proved that it is a won game for the player to move first. In this note we claim that Renju is a first-player win too. We describe our research approach and how we arrived at this game-theoretical value.

1. INTRODUCTION

In 1992 Allis solved the game of Go-Moku by means of the computer program VICTORIA (Allis, Van den Herik, and Huntjes, 1993; Allis, 1994). The main techniques applied were proof-number search (Allis, Van der Meulen, and Van den Herik, 1994) and threat-space search (Allis, Van den Herik, and Huntjes, 1995). Since the advantage for the first player was well-known (Sakata and Ikawa, 1981), many variants of Go-Moku were developed so as to reduce the advantage of the first player, attempting to create a balanced game. Already around 1900 Japanese professional players improved the simple rules of Go-Moku by introducing that the first player (Black) is prohibited from making a double three, a double four, and an overline.After that the Renju

board was diminished from 1919 (Go board size) to 1515 when it was discovered that the larger board size increases Black!s advantage. These improvements were to restrict Black!s moves so as to offset his initial advantage. In 1936 ¤ when the Japanese Federation of Renju was founded ¤ the rules of Renju were fully accomplished. Professional players believed that the new rules would result in a more evenly-balanced game.

When the Renju players became stronger they found that the above-mentioned advanced new rules still gave great advantage to Black. Some Japanese players even showed a black victory in two frequently-played opening patterns (cf. Sakata and Ikawa, 1981), but their solution was incomplete because some good white moves were not analysed and later on even mistakes were found in it. In the Sakata!s book ¤ Figures 31 and 32 facing page 77 ¤ japanese authors suggested an strong 15 th move (A, see Figure 1). After move A, if the White’s reply was move B (16 th move), the Black victory will be become very complicated, but not fully analysed by pro players. White’s defence move C (16 th move) is not mentioned in this book, after this White’s response we were not able to find the Black victory in some weeks. So move A was rejected (and considered to be not good move) and we chose another 15 move (D), which turn out a success. Another problem was, that there are 35 distinct second white moves possible, but only two main variations (adjacent to Black!s first move) were exhaustively analysed in that book. In Japan professional Renju players continued to study Renju in detail. Sakata and Ikawa (1981) published their analysis in 32 pages. We have exploited the analysis for our work and found other mistakes and lacunae (see also Allis, 1994). Nevertheless, the Japanese prediction is now confirmed, extended and corrected by our computer program which established Renju!s game-theoretical value. Our project was to carry out a complete proof about the game of Renju by a computer program and to create a database of the solved game tree.

In 1988, the Renju International Federation was created. At the same time, to equalise the chances of the players at the official tournaments new opening-rules regulations were adopted. The official Renju rules and the new opening regulations are described in Section 2. However, this article focuses on establishing the game-theoretical value of Renju without the new opening-rules regulations. The game we deal with is called freeRenju, it is a quite aggressive game in which almost every black move is a threat. The remainder of this note is structured as follows. After the description of the rules in Section 2, Section 3 provides a list of terms and gives their definitions. In Section 4 we explain our experimental approach and provide empirical evidence for our claim. In Section 5 some technical details on a checking program are given and in Section 6 results are presented. Section 7 contains our conclusions.

Figure 1

2. THE RULES OF RENJU

The game of Renju is a professional variant of Go-Moku. The rules of Renju, although more complex than those of Go-Moku, are still rather simple (Sakata and Ikawa, 1981). The game is played on a board with 1515 points of intersections. Vertical lines are lettered from ’a’ to ’o’, and the horizontal lines are numbered from 1 to 15. The left bottom position on the board is a1. Two players, Black and White, place alternately a stone of their own colour on an empty intersection. Black starts the game and must place a black stone on the centre intersection (h8). The first player completing an unbroken line of five stones (vertically, horizontally, or diagonally) wins the game. In Renju Black has some restrictions with respect to Go-Moku, e.g, some moves are considered to be prohibited for Black. If Black makes a prohibited move either accidentally or by being forced to, White wins the game. The prohibited moves for Black are: overline, double-four, double-three (for definitions, see Section 3). White does not have prohibited moves, so White may make an overline and wins the game. If none of the players succeeds in completing a five-in-a-row, and Black did not make a prohibited move and the board is full of stones, the game

is considered to be drawn.

The above-mentioned rules are known as the free Renju rules. In an attempt to make the game more evenly-balanced for a fair competition in official tournam …… 此处隐藏：16181字，全部文档内容请下载后查看。喜欢就下载吧 ……