Home Page Diaries**Hobbies Learning Notes**Academics Leave Your Cmts.**More Info.Hex chess is a chess game we have never heard of before. Not knowing the rules and techniques is our first enemy. On the first day when the competition title was released, my friend and I logged into Botzone and played for a whole day. Although we were not in the same dormitory, we communicated through voice, summed up the experience of winning or losing in each game, and discovered the basic "bridge" strategy. Writing a program that can build a "bridge" has become our first goal.
The next day, we started writing the first version of the program. The general idea of the program is to move forward from one side to the other. The jump frame "building a bridge" has priority. If others block it, we will go around. Completely achieved victory over random placement strategies. In this strategy, "bridging" is the key, and we conceived a bridging method similar to the revolver magazine. The general idea is as follows, first scan the entire chessboard, the position of the current point is (i, j), and the 6 points near the current point can also be obtained from this. Add the status of the nearby $6$ grids to a queue of size $6$ in counterclockwise order. If queue[1] is your color, queue[3] is your color, and queue[2] is an empty checkerboard, then queue[2] is an optional point for connecting bridges. After others block our "bridge", we need to connect bridges, and after we have locked in the victory, we need to connect bridges. This method can be used to achieve this.
Although we were able to win against bots with any strategy, our current version was like a “dumb kid” in front of a real human being, with no thinking and no fighting ability at all. We then began to experiment with constructing valuation functions, using more mainstream methods. Our first attempt at a valuation function was the following, the second version of our group: To calculate the strength of a game, we need to calculate the degree of connectivity, which is the degree of connectivity from one end of the board to the other. We can set the total number of routes connecting from the top to the bottom as the top-to-bottom connectivity, then we set the array q[i][j] to be the connectivity at point (i,j), (for convenience of representation, in the following description, the values of i and j start from $1$, and the width of the board, $n$, is the upper limit) with the following formula:
This is only the case when there are no pieces on the board, but when there are, it is handled as follows:
At this point, we can indicate the strengths and weaknesses of the current field by means of a variable sum:
This simple valuation function proved to have a number of drawbacks. For example, when we attack, we can only travel from one side to the other, and the problem of repeated bridges may occur. After nearly a day of debugging, the results were satisfactory, but still not good enough to play against human opponents, and we believe that we have reached the upper limit of the debugging of this method. We thought we had reached the upper limit of this method. We needed a better value to measure the strengths and weaknesses of the field, and it might be feasible to take the point with the highest value each time we landed a piece and got a value for it. Over the course of the night, we began an extensive literature search.
From these texts, we selected the ones that were within our reach, achievable, and time-permissible, and worked together to translate them verbatim. We finally settled on AreBeesBetterThanFruitfliesTheis [1]. The algorithm involved in this paper is the idea behind our formal version of the algorithm.