Rex and combinatioral analysis

Rex Game Analysis

The object of this analysis is to give the solution of the Rex Game (Reverse hEX) for a hexboard Hn, whatever n may be. (We suggest calling hexboard Hn, of order n, the support, having the general shape of a diamond, with nxn hexagonal cells on which the Rex Game is played.)

This study has been carried out using the very simple notions of the Graph Theory which would certainly not have displeased Claude Berge. It has enabled us to develop 2 sorts of solutions. The first solution, geometrical solution, already known without using the Graph Theory, makes the solution to hexboards Hn, n inferior or equal to 5 possible, without , however, making an exhaustive analysis of these hexboards. Please note that until now no-one has ever given the solution of the Rex Game to hexboards Hn, n higher than 5. The second solution, analytical solution, which we have created, enabled us to give the solution to hexboards Hn, n higher or equal to 2.

The graphs we use can be divided into 2 parts: the closed graphs, a generalization of the solutions used for the hexboards H n, n inferior or equal to 5, and the open graphs we created in order to solve, without the use of a computer, the Rex Game for a hexboard Hn , n higher or equal to 2. Please note here that without using the open graphs, it would never have been possible to solve the Rex Game. All the closed graphs are created from the same definition. The same applies to all the open graphs. Consequently, it has been possible to analyse all of them using the same winning technique enabling us to analyse them once and for all.

Employing the same method as the one we used for the Hex Game, we began by defining some position-types for the Rex Game.

The analysis method we used is the same as the one we created for the Hex Game, which is the following: we analyse only one move of the winning side each time it has the move, and all the moves of the losing side each time it has the move. As well as this, we stop the analysis of a line of play as soon as the last move of the losing side makes it possible to create a closed or open graph, as, in this case, the end of the analysis is no more than a technical problem.
For a hexboard Hn, the winning strategy of the winning side is simple. It must only play on the ring comprised between the hexboard Hn and the Hexboard Hn-2 situated in its centre. Obviously each move of the winning side must enable this side to create a winning position, whatever the move played by the losing side, i. e. a position which, sooner or later, makes it possible to create a closed or open graph. We show that when the 2 sides have occupied all the cells of the ring (Hn Hn-2), Whites, with the move (if the order n is even), must be the first to play on the central hexboard Hn-2. If an exhaustive analysis of this central hexboard has already been carried out, the analysis of the hexboard Hn is finally completed.

There is no point in imagining strategies and tactics for the losing side as all the possible moves are analysed each time it has the move. On the other hand, we show that the winning side has to choose very carefully the moves it is going to play on the 2 extreme columns (ranks) as well as on certain cells of the 2 extreme ranks (columns) if this side is the one which plays with the White (Black) pawns if it does not want to be forced to play on the central hexboard Hn-2 .If such a situation occurs during an analysis, it is the proof that the winning side has committed a fault in playing one of its former moves which it subsequently has to replay correctly.

The best moves of the losing side are the direct result of the method of analysis. The same does not apply to the winning side .Since at the end of a game all the cells are covered in pawns, it would be wrong to conclude that all the moves of the winning side are equivalent. It is useful to remember that it is possible to stop the analysis of a line of play as soon as a closed or open graph is created. Consequently, it is possible to say that a move on behalf of a winning side is better than any other move, if it leads to the creation of a closed or open graph in a smaller number of moves.

Due to the analytical solution we have been able to carry out an exhaustive analysis of the hexboard Hn , n inferior or equal to 5; then for a hexboard H6 we have also been able to carry out an exhaustive analysis of the position obtained after 1.(6,1) . [We give in annex the exhaustive analysis of the variation 1. (6,1), (1,6)]; following this, for the hexboard H7, we give an exhaustive analysis of the positions obtained after the first moves 1.(4,3);1.(4,4);1.(5,3);1.(5,4);1.(3,3) et 1.(2,2); finally, for a hexboard H8 we give in annex an analysis of the position obtained after 1.(8,1), (4,4), analysis we stopped as soon as it seemed to be sufficiently advanced to be able to understand how to solve the few difficulties that could appear.

It is important to notice, finally, that the preceding analyses effectively prove that for a hexboard Hn, order n even, Whites win, and for a hexboard Hn, order n odd, Blacks win. In the same way as for the Hex Game, the solution of the hexboard Hn, n higher or equal to 6, is obtained from the solutions of the hexboards

Hn-2 , Hn-4 , …………., H8 and H6. (n even)

After having solved the Hex Game, NP-complet problem, without the use of a computer, we have solved, again without the use of a computer, the Rex Game, which to our knowledge the complexity level has not yet been studied.

We suppose, however, that this complexity level is higher than the complexity level of the Hex Game.

May we be allowed to ask the question: would we not have the equality P=NP ?

See studies: