1. bookVolume 6 (2021): Issue 1 (January 2021)
Journal Details
License
Format
Journal
First Published
01 Jan 2016
Publication timeframe
2 times per year
Languages
English
access type Open Access

An algorithm of moving pieces to become black alternation with white based on dimension reduction

Published Online: 09 Apr 2021
Page range: 163 - 170
Received: 04 Dec 2020
Accepted: 31 Jan 2021
Journal Details
License
Format
Journal
First Published
01 Jan 2016
Publication timeframe
2 times per year
Languages
English
Abstract

Moving pieces to become black alternation with white (MPBBAW)is a game in which black and white pieces are continuously arranged by moving. This article traces the problem of MPBBAW and points out the possibility and necessity of computer calculation and commercial application of the problem. Using the non- recursive algorithm based on dimensionality reduction, this article deals with the problem of n-order MPBBAW. The special-order problem is solved and resubstituted. Thus, the computer processing and rule exploration of n-order and n-order MPBBAW are realised. As an auxiliary card, C++ is used to provide 20 black and 20 white pieces as an example. This article lays a foundation for the computer calculation and commercial application of MPBBAW.

Keywords

Tracing the problem of MPBBAW

Moving pieces to become black alternation with white (MPBBAW), also known as interval chess, or as the Mandarin Duck game is a kind of a continuous arrangement which involves moving black and white pieces after making the moves n times till the interval arrangement of the game. It is a mathematical game in which black and white pieces represent the laws of object movement. The chess game is essentially a mathematical problem. The Chinese Go has a long history. Go players inadvertently have found a new way to play black and white pieces. During the reign of Shunzhi in the Qing Dynasty (1641–1661), Hu Lizhi used Go to move three black and three white pieces continuously arranged ‘ ’,‘ ’, ‘ ’, ‘ ’. In the KangXi period, Chu Renhuo's “solid bottle collection” recorded: ‘when I was young, I met my friend Hu Lizhi, who divided the black and white pieces into three pieces. I asked, “how much could you move?” Li Zhi said:“ from three to ten, can be moved. More is more.” “return to try, from three to ten fruits alternately and not disorderly”’ [1]. In the late years of the Qing Dynasty, various masters such as Yu Yue made an in-depth study of the game of MPBBAW and further proposed the moving steps of 11 to 20 pairs of pieces. Limited by the lack of mathematical knowledge of permutation and combination, these folk game experts did not delve into the rules of permutation and combination. Xu Baoli, founder of China's probabilistic statistics, and Yu Pingbo increased the number of chessmen up to fifty based on the “solid bottle collection”. A year later, Xu Baoli devised a new law of MPBBAW. Yu Pingbo recorded the matter in the “Method of MPBBAW”: ‘In the night of the second day of the New Year, he called me suddenly. I happened to be away and he called on me the next day. Then he told me about the law of “combining four into one”. This method was concise and the language was clear. Although it had no more roots than the four laws, it was not redundant, and not wrong. This method was clearly and immediately understood by the people and the application was also very convenient.’ [2] The fun of MPBBAW aroused the divergent thinking of scholars. You Baosan and Mo Shaokui promoted black and white to be polychromatic. Two adjacent pieces are moved each time and could be generalised as P (P could be one) pieces. It was proved that the two-colour chess pieces ‘move 2’ each time. They also proved that the minimum number was equal to the log n of the chess piece [3]. Hu Zhuxin studied the MPBBAW from the modern combination theory. He pointed out that the problem of MPBBAW fell under the category of inlay theory. The idea was to recombine one sequence into another under a particular combination rule. For example, several data stored in a one-dimensional form in a computer were stored separately by category, or using the shift method to make or break a code. The principle of the game was connected with the problem of moving chess in some way [4], which the ancient literati women did not expect. Contrary to the research purport of Chinese players and scholars, foreign scholars had studied the inverse problem of MPBBAW.

In 1743, the early Japanese document ‘ double paper of Kan Zhe Yu Jia’ called it ‘Mandarin Duck game’ [5]. Three pairs of black and white pieces spaced apart from each other, through three times moving, became three white pieces and three black pieces in a row. , , , . This was the exact opposite of the MPBBAW of Chinese players and scholars. The rules of the arrangement of more pieces were the same as those which were applicable to the three pieces; these rules required that two adjacent pieces were moved each time and that the position remained the same and did not change after moving. In 1884, the British physicist Tate replaced the black and white pieces with four gold coins (denoted by B) and four silver coins(denoted by A). He proposed how to generate the ‘BBBBAAAA’ alignment through four moves for ‘ABABABAB’. Unlike Chinese and Japanese scholars, Tate used letters instead of black and white pieces, and his method was exactly the same as that of Japanese scholars. In 1887, Delanoy, a French mathematician, proved the inverse problem of MPBBAW by mathematical method for the first time. The article containing this proof was published in the Journal Nature. In 1899, Dr. Lin Heyi, a Japanese scholar, once again tested the inverse problem of MPBBAW by adding one on each side of the black and white pieces [5].

Different from foreign scholars who paid attention to the inverse problem of MPBBAW, Geng Ji, the contemporary Chinese scholar, insisted on studying the problem of MPBBAW which originated in the late Ming Dynasty and early Qing Dynasty. After a systematic review of research results of the Chinese and foreign scholars, Geng Ji thought that c was still an open question. Through the permutation and grouping method, he found that the core problem of MPBBAW was the distribution of fixed terms. If the position of the fixed item could be determined, different shifting methods could be adopted according to the different regional distribution of the fixed item, and then the regularity of MPBBAW could be deduced. That was when the positive integer n≥ 4, there were n times movings between moves (minimum n times movings) to make the initial form become the final form [6, 7]. This made the MPBBAW experience of Chinese ancient players and scholars mathematically concluded and proved. Further, the MPBBAW problem was more formalised and mathematical.

Computer calculation and commercial application of the MPBBAW problem

At this point, the mathematical properties of the phase problem are fully confirmed, and the mathematical law of the phase problem is revealed. However, it is still difficult to move the large chess pieces in the phase-shifting problem, and the practical application value of the phase-shifting law has not been explored. Only a few scholars have made some bold attempts to explore the practical application value of the phase-shifting problem. ShaYanFei et al. through their observation found that n = 4, n = 5, n = 6, n = 7 four special structures can set an operator in the n of 8 or in arrangement of the pieces; this is because any number of pieces can be in ‘Divided by 4, leaving 0, 1, 2, 3’, the form of simple operation, which is based on the proposed simple mathematical proof of MPBBAW, and the interval arrangement rule is applied to building design [8]. The phenomenon of simple and static space arrangement is common among people, which is abstracted as the rule of space arrangement in primary school mathematics and modelled by scholars. However, for the complex and dynamic spacer arrangement, it has not attracted wide attention from scholars, and the related applied research is rare. Taking graphic design and display as an example, at present, the application of English letters and Chinese characters with graphic expression has been mature and has the limitation of a small amount, mechanical, monotonous and so on.

The main application scenarios of this chess are thinking, training and LED electronic display. This rule can be applied in many aspects, such as electronic display, building layout, etc. The large-scale movement and commercial application of MPBBAW require the help of computers. Through this research, we find that the solution algorithm of MPBBAW can reduce dimension using stack [9, 10, 11], and continuously reduce dimension for the phase shift problem of the n-order. Also, we carry out a special solution and back-substitution for special-order problem to realise the computer operation of the whole MPBBAW problem of n-order.

Principle of dimensionality reduction and moving method of the problem of MPBBAW

The basic rules of MPBBAW are that:(1) in the process of moving, the position of adjacent pieces cannot be exchanged; (2) after a pair of chess pieces move, the original position becomes vacant and (3) the space arrangement finally formed has no vacancy.

We use the black circle for the black and the white circle for the white and set the ‘underline’ only to indicate the two pieces to be moved next.

When n = 3,

When n = 4,

When n =5,

When n = 6,

When n = 7,

For n = 7, we find that the diagram contains a ‘3 black 3 white’, which we call the 7 black 7 white subsets. Marked with a quotation, we mark to distinguish it from the normal 3 black 3 white. In the ‘3 black and 3 white’ movement order, the moving pieces and direction of the ‘first step’ are the same as that of the ‘3 black and 3 white’, and the moving pieces of the ‘second step’ are the same, but in different directions (the second step of the normal 3 black and 3 white is to move to the right, while the ‘3 black and 3 white’ moves to the left because there is a space on the left). So 3 black and 3 white can be considered as special cases.

Referring to the research of Delanoy in 1887 (his article was published in the 15th issue of Nature in 1887), Dr. Lin Heyi in 1899 [5] and Geng Ji in 2010 [6, 7], we believe that for any n > = 4, that is, with n black pieces and n white pieces, MPBBAW can be achieved in at least n steps of movement. When n=4, n=5, n=6, and n=7, the operation steps of the chess pieces are in the basic mode or fixed state. Since the first move, the second move, the penultimate move and the last move are consistent, thus: when n is congruent with 0 (mod4), the intermediate state of the chess piece can be converted to 4 sub-modes. When n is congruent to 1 (mod4), the intermediate state of the chess piece can be converted to 5 sub-modes. When n is congruent to 2 (mod4), the intermediate state of the chess piece can be converted to 6 sub-modes. When n is congruent to 3 (mod4), the intermediate state of the chess piece can be converted to 7 sub-modes.

Initial state:

The first:

The second

……

The penultimate

The last:

If we take 8 pieces as an example, it can be converted into 4 pieces mode:

When n≥ 8, the method of ‘Divided by 4, leaving 0, 1, 2, 3’, by Sha Yanfei et al, [8] can be used for simple treatment, which is in line with the rigorous and complex mathematical proof and movement of Geng Ji [6, 7]. This has laid a foundation for the large-scale computer calculation and commercial application of MPBBAW.

Algorithm design of reduction dimension of MPBBAW

It can be seen from the dimensionality reduction process of the MPBBAW problem that this algorithm can be based on recursive design, but because of the low efficiency of the recursive algorithm, a non-recursive algorithm is adopted to reduce dimensionality by using stack for n-order of MPBBAW problem. With the help of the programme stack, the non-recursive algorithm transforms the programme into a loop and effectively and reduces the time complexity [12, 13, 14] For the n-order of MPBBAW, the problem is continuously processed by reducing the dimension by the 4-order [15, 16]. The feasible interval of the current moving game phase is kept by stack until n<8. Then, the problem of the special MPBBAW problem that is less than 8 is solved in a special way. Also, the problem of the whole n-order moving game phase is solved by back-substitution [17, 18]. The specific algorithm design is as follows:

Create the initial solution data[1 ∼ 2n+2] and the initial interval [low, high], low=1, high =2n+2 for the n-order of MPBBAW problem. (the convention data[I] takes 1 for black, 0 for white, and 2 for empty).

Set the feasible interval stack s that retains the current MPBBAW and set empty stack.

The process of dimensionality reduction.

While (n > 7)

{(1) move four groups of dimension reduction.

  data[high-1]=data[low+1];data[low+1]=2;

  data[high]=data[low+2];data[low+2]=2;

  data[low+1]=data[high-5];data[high-5]=2;

  data[low+2]=data[high-4];data[high-4]=2;

(2) press the current feasible interval [low, high] into the feasible interval stack s.

(3) reduce by 4 dimensions.

low + = 4; high − = 4; n-=4;

}

Carry out a special solution to the problem of special MPBBAW with n less than 8 (for n=7,6,5,4,3).

Step-by-step reverse processing.

While (stack s is not empty)

{

(1) the top element of feasible interval stack s is pushed to [low, high];

(2) carry out four group moves of back-substitution.

  data[low+4]=data[high-2];data[high-2]=2;

  data[low+5]=data[high-1];data[high-1]=2;

  data[high-2]=data[low];data[low]=2;

  data[high-1]=data[low+1];data[low+1]=2;

}

The flow chart of the algorithm is shown in Figure 1.

Fig. 1

The flow chart of the algorithm of the MPBBAW problem

Example of dimension reduction algorithm of MPBBAW problem

The specific steps are: for more than 7 pieces, it can be converted to one of the four cases. The first two steps are to put ‘2, 3’ at the end of the table, and then put ‘2n-5’ (2n means double colour, -5 means penultimate fifth) and ‘2n-6’ in the space so that you get a black and white sequence with an ‘n-4’ in the middle. Then put ‘2n-3’ and ‘2n-2’ in the space, and then put the first two in the space. This is a round operation, which is solved if the middle ‘n-4’ is one of the ‘4, 5, 6, 7’, otherwise continue the above recursive operation for the black and white strings of the middle n-4’.

We take 20 black and 20 white (abbreviated as 20) as an example and explanations. n=20

The running steps of the 20 computer are:

Step 1: place‘2,3’ pieces at the back. (note that there are 20+20+2 Spaces)

Step 2: place the 37th and 38th pieces on the empty positions of ‘2,3’. (fifth and sixth from last). So we have a string of ‘16 black and 16 white pieces’ starting from the fifth position.

Step 3: start the fifth position with a string of ‘16 black and 16 white pieces’ as an independent string. The third move is similar to the first, moving the ‘23’ piece (actually moving the 6th and 7th pieces). Placing the second and third bits of the ‘16 black and 16 white pieces’ at the end of the ‘16 black and 16 white pieces’ is equivalent to placing the sixth and seventh bits of the entire globe into the 37th and 38th positions.

Step 4: place the fifth and sixth from ‘16 black and 16 white pieces’ to the second and third from ‘16 black and 16 white pieces’. Then you can get a set of 12 black and ‘12 white black and white pieces’.

Next, repeat steps (each time will be the beginning of a new series of ‘2, 3’, and finally, the new bottom fifth and sixth in the first ‘2, 3’ and each time will get a less than 4 before a series of black and white) until the rest of the series of black and white is one of the ‘4, 5,6,7’. This is a special method to solve the four kinds of circumstances.

After solving the special case, repeatedly put the reciprocal ‘2, 3’ of the current black and white sequence into the current position to the beginning of the current sequence ‘5, 6’. And put the current beginning of the current sequence to the current reciprocal of the current reciprocal ‘2, 3’. Then it becomes possible to solve the current black and white sequence, and then it is necessary to repeat one of the steps to solve the previous black and white sequence. Until it is all settled. The result of ‘n=20’ is shown in Figure 2.

Figure 2

The arrangement of 20 pieces of MPBBAW

For any n pieces, the running steps and algorithm of the computer are as follows:

n = k, k≥8„ k ∈ N*

Step 1: place ‘2, 3’ pieces at the back. (note the spaces, k+k+2 positions)

Step 2: place the fifth and sixth from the bottom (i.e. 2k+2–5, 2k+2–4) pieces on ‘2, 3’ vacancy. So we get a ‘k-4’ substring starting from the fifth position.

Step 3: treat the ‘k-4 substring’ at the beginning of the fifth digit as an independent sequence. The third move is similar to the first, moving the ‘2, 3’ pieces (actually moving the 6th and 7th pieces). That is the end of the ‘k-4’ substring with the second and third bits in ‘k black and k white pieces’.

Step 4: place the penultimate fifth and sixth place of the ‘k-4’ substring to the ‘2, 3’ place of the ‘k-4’ substring. Then you can get a black and white string of ‘k-4-4’ pieces.

Next, repeat steps (each time will be the beginning of a new series of ‘2, 3’ and finally, the new bottom fifth and sixth in the first ‘2, 3’, and each time will get a less than 4 before a series of black and white) until the remaining black and white sequence is one of ‘4,5,6,7’, which have special solutions.

After solving the special case, repeatedly put the reciprocal of the current black and white sequence to the beginning of the current sequence ‘5, 6’, and put the current beginning of the current sequence to the current reciprocal ‘2, 3’. Then you can solve the current black and white string. Then repeat this step to solve the previous black and white sequence until all the white and black spaces are formed.

To summarise, so far, we think of the three pieces as a special case, and what we’ve concluded is merely a rule, and there should be other rules. This rule can be applied to all aspects of social and economic life.

Fig. 1

The flow chart of the algorithm of the MPBBAW problem
The flow chart of the algorithm of the MPBBAW problem

Figure 2

The arrangement of 20 pieces of MPBBAW
The arrangement of 20 pieces of MPBBAW

Liu Dun. Mathematical historical materials in some notes of Ming and Qing Dynasties [J]. Historical materials of science and technology in China, 1989 (4): 49–55 DunLiu Mathematical historical materials in some notes of Ming and Qing Dynasties [J] Historical materials of science and technology in China 1989 4 49 55 Search in Google Scholar

Xu Baolu, Festschrift editorial committee. Xu Baolu festschrift [M]. Beijing university press, 2010 BaoluXu Festschrift editorial committee. Xu Baolu festschrift [M] Beijing university press 2010 Search in Google Scholar

Yu Baosan, Mo Shao Kui. Theory of moving pieces to become black alternation with white [J]. Journal of mathematics, nanjing university, 1986 (1): 60–71 BaosanYu KuiMo Shao Theory of moving pieces to become black alternation with white [J] Journal of mathematics, nanjing university 1986 1 60 71 Search in Google Scholar

Hu Zhuxin. Historical origin and modern development of inscriptions [M]. Shandong education press, 1986 ZhuxinHu Historical origin and modern development of inscriptions [M] Shandong education press 1986 Search in Google Scholar

Pin Shanfi. East-west mathematics [M]. Ttranslation. Dai Qin. Shanghai: Shanghai education press, 2005 ShanfiPin East-west mathematics [M] Ttranslation. QinDai Shanghai Shanghai education press 2005 Search in Google Scholar

Geng Ji. Mathematical entertainment (6) – moving pieces to become black alternation with white [J]. Journal of hainan university (natural science edition), 2010, 28 (1): 1–10, JiGeng Mathematical entertainment (6) – moving pieces to become black alternation with white [J] Journal of hainan university (natural science edition) 2010 28 1 1 10 Search in Google Scholar

Geng Ji. Mathematical entertainment (16) – the problem of moving pieces to become black alternation with white and international scientific research results [J]. Journal of hainan university (natural science edition), 2015 (03): 197–203 JiGeng Mathematical entertainment (16) – the problem of moving pieces to become black alternation with white and international scientific research results [J] Journal of hainan university (natural science edition) 2015 03 197 203 Search in Google Scholar

Sha Yanfei, Sha Bowen, Fu Pingping. Application of move chess phase method in architectural appearance design [J]. Design, 2018 (5): 140–142 YanfeiSha BowenSha PingpingFu Application of move chess phase method in architectural appearance design [J] Design 2018 5 140 142 Search in Google Scholar

Zhang Guifen, Ge Lina, Huang Yinjuan. Research on kongming chess algorithm based on stack structure [J]. Computer technology and development, 2009 (12): 51–54 GuifenZhang LinaGe YinjuanHuang Research on kongming chess algorithm based on stack structure [J] Computer technology and development 2009 12 51 54 Search in Google Scholar

Silver D., Huang A., Maddison C.J., et al., Mastering the game of Go with deep eural networks and tree search [J]. Nature, 2016, 529(7587): 484–489 SilverD. HuangA. MaddisonC.J. Mastering the game of Go with deep eural networks and tree search [J] Nature 2016 529 7587 484 489 Search in Google Scholar

Silver D., Schrittwieser J., Simonyan K., et al., Mastering the game of Go ithout human knowledge [J]. Nature, 2017, 550(7676):354 SilverD. SchrittwieserJ. SimonyanK. Mastering the game of Go ithout human knowledge [J] Nature 2017 550 7676 354 Search in Google Scholar

Sato N., Ikeda K., Three types of forward pruning techniques to apply the alpha beta algorithm to turn-based strategy games. 2016 IEEE Conference on Computational Intelligence and Games. 2016 SatoN. IkedaK. Three types of forward pruning techniques to apply the alpha beta algorithm to turn-based strategy games 2016 IEEE Conference on Computational Intelligence and Games 2016 Search in Google Scholar

Companez N, Aleti A., Can Monte-Carlo tree search learn to sacrifice. Journal of Heuristics. 2016 CompanezN AletiA. Can Monte-Carlo tree search learn to sacrifice Journal of Heuristics 2016 Search in Google Scholar

Baier H, Winands M H M., Monte-Carlo tree search and minimax hybrids with heuristic evaluation functions. Proc of International Conference on Computers and Games. 2014 BaierH WinandsM H M. Monte-Carlo tree search and minimax hybrids with heuristic evaluation functions Proc of International Conference on Computers and Games 2014 Search in Google Scholar

Silver D., Schrittwieser J., Simonyan K. et al., Mastering the Game of Go without Human Knowledge. Nature. 2017 SilverD. SchrittwieserJ. SimonyanK. Mastering the Game of Go without Human Knowledge Nature 2017 Search in Google Scholar

Silver D., Hubert T., Schrittwieser J. et al., Mastering chess and shogi by self-play with a general reinforcement learning algorithm. 2017 SilverD. HubertT. SchrittwieserJ. Mastering chess and shogi by self-play with a general reinforcement learning algorithm 2017 Search in Google Scholar

Dubey R., Agrawal P., Pathak D., et al., Investigating human priors for playing video games. 2018 DubeyR. AgrawalP. PathakD. Investigating human priors for playing video games 2018 Search in Google Scholar

Andre Barreto, Diana Borsa, John Quan, et al., Transfer in deep reinforcement learning using successor features and generalised policy improvement. 2018 BarretoAndre BorsaDiana QuanJohn Transfer in deep reinforcement learning using successor features and generalised policy improvement 2018 Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo