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

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 Whites reply was move B (16 th move), the Black victory will be become very complicated, but not fully analysed by pro players. Whites defence move C (16 th move) is not mentioned in this book, after this Whites 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 tournaments, the following eight opening-rules restrictions have been imposed on Black (i.e., the professional Renju Rules). a. Players start the game as tentative Black and tentative White. Tentative Black plays the first move on the centre intersection. b. Tentative White makes the second move diagonally, horizontally or vertically to the first move and adjacent to the first move (i.e., two different openings). c. Tentative Black plays the third move on an empty place within a zone of 55 intersections in the centre of the board (26 opening patterns). d. Tentative White has the right to change the colour of the stones (swap option). e. The player, who now has the white stones, plays the fourth move wherever (s)he wants. f. Black has to offer the opponent two possible asymmetrical fifth moves. g. White chooses one of the fifth moves which will be more advantageous to him/herself and tells Black to make the moves (s)he prefers. h. There are no restrictions on the sixth and later moves.3.TERMS AND DEFINITIONSBelow we provide a list of the terms together with their definitions. Overline: Six or more stones of the same colour in an unbroken row, either horizontally, vertically or diagonally. Five: Exact five stones of the same colour arranged in an unbroken row, either horizontally, vertically or diagonally. Straight four: Four stones of the same colour in an unbroken row (horizontally, vertically or diagonally) with both ends open. A straight four ensures a win. Four: Four stones of one colour in a row, which in one move can become a five. Three: Three stones of the same colour in an unbroken row, or with one-intersection gap between the stones that can become a straight four on the next move. Double-Four: A single move, which builds simultaneously more than one four at one time. Double-Three: A single move, which builds simultaneously more than one three at one time. Four-three: A four and a three produced simultaneously with a single move. It is the usual way for Black to create a winning formation. VCF: This acronym means: Victory by Consecutive Fours. A win that results from making fours one after another. VCT: This acronym means: Victory by Consecutive Threats. A win that results from making threats (four or three) one after another. Japanese terms: Fukumi: A move which threatens to win by VCF. Who played the fukumi move has a VCF if the opponent does not defend against this move. Yobi: A positional offensive move, which threatens to win by VCT. A yobi move is not a direct forced method of attackPlaying A leads to an overline.Playing B leads to a double-four.Playing C leads to a double-three.Playing D leads to a straight four.Playing E leads to a four-three. Figure 24. THE PROGRAM AND THE EXPERIMENTAL APPROACH The solving program was written in Borland Pascal language. The program goal was to establish the game-theoretical value. The program generated a winning tree for Black and stored the tree in a database. The search process used transposition tables to avoid searching symmetrical positions. Moreover, the solving program used the threat-sequence search as suggested by Allis et al. (1993). There was only a very limited possibility to play no-threat moves, the first black moves after a bad opining by White (such as moves far away from the board centre). If a white defending move in such a variation also was a threat then Black countered it and did not lose a tempo in the end. The program operated an iterative-deepening search based on threat sequences up to 17 plies. The speed of the threat-sequence search was 400 nodes/second on a Pentium 200 MHz machine. The deepest variations of the iterative-deepening search (17 plies) took about 15 minutes, then a VCF line was found.It was not possible to speed up the threat-sequence search (cf. Allis, 1994) since by the overline, double-four and double-three rule the order of moves became more complex. In the solving program we had implemented an automatic database builder, but all openings, fukumi, yobi, and positional moves were inputted by the hand of a human expert. In the past, the human expert assistance has been used in game solving (O. Patashnik, 1980). In total, human players produced approximately 5000 positional moves. The threat-sequence search module built all black threat sequences up to a given depth and investigated whether the position is a win for Black against every possible defence by White. After a positional black move, another module examined how Black can win if White passes. If a winning line exists then this module stores the moves of these sequences and in the next step the solving program will use these moves as white answers. All moves of the game tree were stored in the database with the exception of the last 10 plies, since 10 or fewer plies of winning sequences can be found quickly by the threat-sequence search engine. Generating the whole game tree took about 3000 hours on a Pentium 200 MHz PC.5. THE CHECKING PROCEDURE After the generation of the whole game tree, the second stage of the project was checking the database. To making sure of generated database, there is necessary to develop a checking program, which plays backwards all possible white moves and then communicates with the solving program on the forward white moves (meanwhile inspecting the database). When a not-analysed white move was encountered, the solving program first took the black answer most frequently-played in that stage of the game tree. This approach gave many typical first omissions. In the checking loop, we stored white wins, black prohibited answers, and non-proved positions. The checking file contained approximately 2000 previously missing positions, which were corrected in the next proof run. The proof runs and the correction of positions were repeated several times even when the checking log did no longer contain any lacking positions. The programming of the checking program was performed by the second author in Borland Pascal programming language. This part of the solving took about 6000 hours on a Pentium 200 MHz machine.6. CONCLUSIONS We verified and expanded the statement of Japanese Renju experts that the game of free Renju is a theoretical win for the first player to move. The game was solved after 9000 hours of using a Pentium 200 MHz. The size of the overall database is 7 Megabyte. After the final database creation, the database was checked once more and accepted as correct by a checking program written by an independent programmer. In the last checking run, no missing variations were found by the checking program. In conclusion, free Renju should be considered a solved game. The result is that the game is a first-player win. Finally, we have good reason to believe that after building a good opening book, say of 5000 moves, theres no middle game ,provide that an appropriate endgame-analysing routine is available.五子棋是一种微妙的，存在与两个玩家之间的带有战略性的棋盘游戏。它源于日本，是围棋的一种变体。在许多国家中，如中国、爱沙尼亚、日本、拉脱维亚、俄国和瑞典，五子棋都被看做成是一种高智能的游戏。相对于广泛存在于中国和日本的围起来说，五子棋有着非常简单的游戏规则。在1992年Allis揭示了五子棋的问题，他证明这项游戏的胜利取决于先下棋的玩家。在这篇文章中我们也赞同它的说法，认为五子棋是一个偏向于先手获胜的游戏，我们阐述了我们研究方法和怎样实现游戏的理论价值。1. 引言在1992年Allis通过计算机工程VICTORIA（Allis, Van den Herik, 和 Huntjes, 1993; Allis, 1994）的意义揭示了五子棋游戏的问题。主要的技术应用是数据取样研究（Allis, Van der Meulen, 和 Van den Herik, 1994）和危险范围的研究（Allis, Van den Herik, 和 Huntjes, 1995）。自从先手的优势被众所周知后(Sakata 和 Ikawa, 1981)，为了减少先手的优势，许多五子棋的变体得到了发展，并尝试着建立一个平衡的游戏。早在1900年左右，日本的专业选手就改善了五子棋的的简单规则，通过引介禁止先手（黑棋）制造双三、双四和overline的方法。当发现大的棋盘可以增加黑子的优势时，就减少了五子棋的棋盘的大小，从原来的1919减到1515。这些限制黑子进展的改善是为了抵消它最初的优势。在1936年，当建立了日本五子棋联合会后，五子棋的规则就已完全的娴熟，专业选手相信新的规则将会产生一个更加公平的比赛。当五子棋的玩家变的更强一些时，他们发现上面提到的改善后的新规则仍然给了黑子很大的优势，一些日本选手甚至展示了在两个常见比赛中开端形式的黑子的胜利(cf. Sakata 和 Ikawa, 1981)，但是他们的解答时不完全的，因为没有分析一些优秀的白子的移动，并且以后甚至在其中发现错误，在Sakata的书中，见77页指出的31和32点，日本的发起人建议一个更强有力的第15步的落子（见图Figure 1中的A处）。在A处落子之后，如果白子的玩家的反应是在B处落子（第16步），那么黑子的胜利将会变得非常的复杂，但是，赞同的玩家并没有完全地进行分析。白子落在C处防御（第16步）在这本书中并没有提到，从白子的回应后，我们在很长一段时间内不能发现黑子的胜利。所以排除在A处落子（并且不认为是一步好棋），同时我们选择把棋子落在D处作为第15步，事实证明这是成功的一步。另一个问题是将会有35中不同的白棋第二次可能落子的地方，但是仅仅两次主要的变动在那本书中被彻底的分析到。在日本的专业的五子棋选手继续详细地研究五子棋。Sakata 和Ikawa（1981）在书中的第32页发表了他们的分析，我们已经针对我们的工作开展了这项分析，并且发现了一些错误和不足（也见Allis，1994）。尽管如此，日本人的预言现在通过我们已确定的五子棋游戏理论价值的计算机程序看是被认可的、延伸的和正确的。我们的工程在关于五子棋游戏方面将通过计算机程序计实现一个完全的证明，和建立一个解决游戏图普的数据库。在1998年，建立了国际五子棋联盟。与此同时，为了使选手机会的公平化，在官方锦标赛中同过了新的开局规则规章。官方的五子棋规则和新的开局规章在第二部分进行阐述。然而，这篇文章主要集中在没有新的开局规则的情况下证实五子棋游戏的理论价值。我们称所要解决的游戏为五子棋，它是一个带有几分挑衅的游戏，其中几乎黑子的每一步落子都是一个威胁。这篇文章的其余部分的结构如下。在第二、三部分描述规则之后列出了一部分术语，并给出了他们的定义。在第四部分我们解释了我们的试验方法，和针对我们的阐述提供了以观察和实验为依据的证据。在第五部分给出了在检验程序时的一些技术细节，在第六章显示了结果，第七章包含了我么的结论和意见。2.五子棋的规则五子棋游戏是专业Go-Moku的变体。五子棋的规则尽管比起那些Go-Moku要复杂一些，但它仍旧很简单（Sakata 和 Ikawa, 1981）， 这个游戏是在一个1515的棋盘的交叉点上进行的。垂直线用字母A到O标注，水平线用数字1到15标注。棋盘左下方的位置是A1。黑棋白棋两位玩家轮流执他们自己颜色的棋子放在棋盘中空的交叉点上。执黑子玩家先开始下棋，并且必须把棋子放在棋盘的正中间（H8）。最先完成无五子连线（垂直、水平或斜线方向）的玩家获胜。五子棋中黑子有一些限制，例如，对于黑子来说有些落子是被认为禁止的，如果黑子落子被禁止不是偶然的就是被迫的，那么白子就获胜了，禁止黑棋落子的情况有：overline, double-four, double-three（具体定义见第三部分）。白子没有禁止落在的情况，所以白子也可以制造一个overline来赢得游戏，如果没有选手成功的完成五子连线，并且黑子没有被禁止落子和棋盘已满，则认为这盘游戏平局。上面提到的规则被认为是五子棋的规则。在官方锦标赛中为了公平竞争尝试着使游戏更加公正，下面8个开局规则规章已经强加给黑子（专业五子棋规则）。A 选手开始游戏作为黑子或白子，黑子先下棋并且放在棋盘中间。B 第二步白子放在临近第一步棋子处对角线上、水平线或是垂直线上。C 第三步黑子放在以棋盘为中心向外的55个交叉点范围内的空子处。D 白子有权利改变棋子的颜色。E 现在拥有白子的选手下第四步，棋子可以放在他想放的棋盘上的任何处。F 黑子提供给对手两种不对称的可能下第五步棋。G 白子选择黑子提供下第五步棋方法中他认为对自己更有利的一种，然后告诉黑子下他喜欢的地方。H 从第六步起和之后都没有限制了。3术语与定义下面我们提供一系列术语以及他们的定义。Overline：六个或六个以上的同色棋子连成一线，垂直方向、水平方向或斜线方向。Five: 精确的只有五个同色的棋子连成一线，垂直方向、水平方向或斜线方向。Straight four: 四个同色棋子连成一线（垂直、水平或斜线方向）并且两边的位置是空的，是一定会赢的一种情况。Four: 四个一种颜色的棋子连成一排，再添加一个棋子就能连成五个。Three: 三个相同颜色的棋子连成一线，或是在三个棋子间有一个空位，只要再下一个相同的棋子在空位上就能形成Straight four。Double-Four: 只下一步棋，就能形成一个同时存在的不止是一排形成四子连线。Double-Three: 只下一步棋，就形成了同时存在的不止一个三子连线。Four-three: 只下一步棋就形成了一个四子连线和一个三子连线同时存在的情况，对于