Application of Multithreading Technology in Boao Procedure
禹 晓 辉 Jiang Xiao Dong Summary: How to introduce Java multi-threading mechanism in traditional Boao procedures to improve the search efficiency of Boyao, and give 1 specific application example. Keywords: Java multi-thread mechanism Bo Tree thread is a new concept of the operating system, which is a unit that is more concurrently compared with a smaller particle size of the traditional process. C and C use a single-threaded architecture, while Java provides multi-threaded support. On the one hand, the Java environment itself is multithreaded; on the other hand, the Java language has built-in multi-thread control, providing 1 THREAD, which is responsible for start, run and terminate the thread and check the thread state. The Java thread also includes synchronization primitives for multi-threading implementation concurrent control. With Java multi-threaded programming interfaces, it is convenient to construct a multi-threaded application, improve the program's concurrency, and perform efficiency. The author participated in the development of black and white chess based on IBM Visual Age for Java environment. By introducing Java multi-threading mechanism into Boyao tree search, the search average depth is significantly increased, and it has achieved good results. 1 Thread concept and life cycle so - called "thread" is a single order of the "process". Emerging operating systems, such as MacOS, Windows NT, etc., considers threads as their basic execution unit. Threads are also a considerable component of Java, such as any one Java Applet's Paint () and Update () methods are called by the AWT drawing and event processing thread. Figure 1 shows a method of threading at any time in its life cycle, and a method of causing state changes. Figure 1 Thread Life Cycle 2 Boyao Bo Wei is a countermeasure or trip, not only in the chess game, but also among political, economic, military, and bio-competition. In the field of artificial intelligence, most of the following chess are studied as an example. Boi provides 1 good test site for artificial intelligence. Many of the concepts and methods in artificial intelligence are refined from chess programs. Many of the research results of Boao have now been used in military command and economic decision-making systems. . The status space of the Boao issue - Bo Yu is a special and / or tree, and the node represents the pattern. The so-called pattern is all information reflecting the playback situation, such as a chess position, and the rotation of the next step, the available state variables. Figure 2 is a partial part of 1 Boao tree. Figure 2 Bachelor's part of the Boao tree is in Boao (ie, the interests of the bilateral interests), and the two parties have to find 1 to find the most path in the status space. All the finals that make Party A won is the end of the decrease, it is divided into b; all the finals winning the victory of Party B is the unlearable end of the end, divided into -b; respectively, according to Party B and Party B, To the root can step by step to calculate the scores of each intermediate node and root node, this is the minimal maximization analysis method for Boyao trees. However, even if there is a small Boao status space, it may also generate a very large Boao tree. It may have a large number of finals. It is impossible to attempt to adopt a complete minimal maximization analysis, and the actual feasibility is: under one of the analytical nodes, only part of the "like" albeit "is part (given depth restrictions, Remove duplicate and hopeless branches), and use the score function F to estimate the values of the leaves of the tree, and then use a very large minimization analysis to calculate the score valuation of each node and root node in the tree. To select the best strategy of the current estimate. These calculations are referred to as a back up value, which is a score function. Obviously, how to improve the depth of search as much as possible within a limited time (5S this system) is critical. It is generally considered that this is to be improved to the hardware facilities. However, it was found that in the traditional single-line Bo Yan program, the opponent was used to think about the time of the play, and it was difficult to use.
However, after introducing multi-threading mechanism, the technology of "time stealing" is used to transform the other party's thinking time to our utilization time, used to increase search depth, or improve the accuracy of the score function under the search depth constant condition Thus, there is a significant improvement of the overall performance of the Bao. 3 Application instances Based on the above ideas, we developed a black and white chess in the IBM Visual Age for Java environment. The main architecture of the program and related code involving multi-threaded applications are given below. In order to facilitate understanding, it is necessary to introduce the black and white chess rules. 1. Black and White Chess Rules (1) The chessboard is 8 × 8 squares, and the two sides are black and white. (2) Initial status: 4 classes in the middle of the chessboard are put in black, white 2 pieces, as shown in Figure 3 (a). (3) Reputation, eating rules (taken as a case): 1 When black chess fall, take this in the center along 8 directions (upper, lower, left, right, left, upper right, left, right down) To find the original black and white, if the first black child found in a certain direction is spaceless, all the white pieces between the two blacks becomes a black child, as shown in Figure 3 (b), Figure 3 (c). Figure 3 Black and White Chess Rules 2 If you can't find the white chess into a black, you must give up a step, and the other party will come back; if you find it, you can't give up this step. 3 wins and negative decisions, when both parties give up one step or on the chessboard, the two-color chess pieces on the chessboard will win. 2. Program Design Requirements (1) Person with your computer and players, play chess in the chessboard. Players can choose first or later. (2) The calculation time of each step of each step is limited to 5s (Pentium 75, 32MB RAM), and the timeout is enforced by the program. 3. Programming (1) This software is 1 applet. The definition is defined in the program. 4 classes: Reversi: is the skeleton of the entire applet, responsible for the management of user interface; Revboard: Responsible for each program related to chess games, such as search Scheduling of programs such as chess games; Revsearch: Search; Revplate: Defines the internal storage structure of the chess game and 1 set of maintenance methods. (2) During the operation of this software, there will be 2 threads TH-Search, TH-SLEP parallel, as shown in Figure 4 (assuming player first hand). Figure 4 TH-Search and TH-SLEP Running Status When the applet starts running, start the TH-Search thread, start search; when the player is falling, the THEP thread is started, and immediately performs Sleep (5000), and performs sleep state . TH-Search performs a search. After 5S, TH-SLEP woke up and asked TH-Search to provide search results, and by this program, the TH-SLEP turned into a Suspend state, at this time, the player is thinking, and the search of TH-Search is also in progress . When the other party falls, restart the TH-SLEP thread, so restart until the end of the program. It can be seen that TH-SLEP actually plays a role of 1 timer.
