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

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 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 DEFINITIONS Below 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 attack Playing 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 2 4 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 there s 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 的方法 当发现大的棋盘可以增加黑子的优势时 就减少了五子棋的棋盘的大小 从原来的 19 19 减到 15 15 这些限制黑子进展的改善是为了抵消它最初的优势 在 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 这个游戏是在一个 15 15 的棋盘的交叉点上 进行的 垂直线用字母 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 只下一步棋就形成了一个四子连线和一个三子连线同时存在的情况 对于黑子 的胜利这是一种常用的办法去建立一个胜利的布局 VCF 这个缩写字母的意思是 通过一步步的逼近才取得的胜利 游戏胜利的取得来自于制 造一步又一步的逼近 four 或 three 日本的术语 Fukumi 想通