Automatic Solution of Pushing Box Game
Introduction
Push the box, also known as the movement, is a very popular single intelligence game. The player's task is to manipulate a porter in a warehouse, push N the same box to N identical destination. Pushing the box game appears in the computer to start from the warehouse of Li Guzhao, Taiwan Province, in the computer, also known as the warehouse, and the box can only be pushed, can't pull, and one can only drive one. Its rules are so simple, but the charm is endless. But people think that the depth and speed of thinking, can we use a computer to help us solve?
Basic part of the game
First, I chose C to do this program. This step is not too difficult, and many programming enthusiasts must have written a lot of games. So here I only briefly describe the necessary pavement.
I will push the data and operation of the box game into a Boxroom class, the following is the members and data structures used later automatic solution algorithms.
1
// Move one, if you have a box
Short Movepush; Direction;
// Move to a point and return a mobile path
Short Goto (Position P, MovePath & Path);
The above two are used to move the porter, they return to the number of steps that have passed, and the failure returns -1. Where GOTO has used the MovePath structure.
TypedEf vector
About the GOTO algorithm, the shortest path algorithm can refer to the "9CBS Development Master" 2004 "Path Search Algorithm Discussion" in PC Games. Considering that the map of the box is not large, I use a classic Dijkstra algorithm. This should be found in the textbooks in the data structure, so there is not much pen ink.
2
In order to remember the state that has been searched, Boxroom also provides functions for recording and saving status:
Void Savestate (BoxroomState & s) Const;
Void LoadState (Const BoxroomState & s);
The BoxroomState structure will be discussed later.
3
It is used to detect if it has been victorious.
Bool isfinished () const {
Return m_nbox == std :: count (m_map.begin (), m_map.end (), em_box_target);
}
Framework of automatic solving algorithm
The essence of artificial intelligence is exhausted in a sense, but how effective exhaustion is a good problem to solve in a good intelligent algorithm. The known fact is that the box problem is NP-HARD. The first question is that the space we have to search is quite huge, "silly" search is quite time, what we have to do is to use various means to reduce unnecessary search to save time. There is also a problem with such a large search space, how we use a limited space to save effectively, and fast judgment has been searched.
The search space has been mentioned in many times, then we describe the search space of the push box problem.
The SaveState and LoadState function of the Boxroom class are mentioned above for boxroomstate. It describes the nodes in the problem space. First, its implementation is to save space, because the quantity state is recorded during the automatic solving process. I used Boost :: Dynamic_bitSet, because there is a weak point in the BitSet of the standard library to determine their digits, and we don't want to make Boxroom template.
Class BoxroomState {
Friend class boxroom;
Boost :: Dynamic_bitSet <> m_extracted_map;
Position M_manpos;
Short m_totlestep; // Compare the status is equivalent
/ / Equivalent: If the state A can reach the status of state B in the case of the box, then a <=> B
// Nature: self-translocation, transfer, symmetry
//
// Note: It is more difficult to say, so we can only use its sufficient conditions! So strictly say that this is not in line with ==, that is,! Operator == () does not mean! =
PUBLIC:
Bool Operator == (const boxroomstate & ba) const {
Return m_manpos == os.m_manpos && m_extracted_map == os.m_extracted_map;
}
Inline int gettotlestep () const {return m_totlestep;}
Inline void settotlestep (int S) {m_totlestep = S;}
}
SetTotlestep seems to be a bit strange (you can even change it to 1 without considering its rationality), providing it purely for the needs of the algorithm. Note has explained how to determine if the two status is equivalent, specifically mentioned that this is just sufficient condition rather than the necessary conditions. Provide a strengthened sufficient condition (if it is a fill condition, it will be more perfect) will be able to further reduce the space of the search.
The transfer between these states is the side, which constitutes an outwardly. Searching for general figure is very troublesome, because it is easy to cause loops. Consider such a situation, push a box to the left and push one to the right and then push the left to the left. The state is significantly equivalent. The number of steps that continue to search for the latter situation is significantly greater than The former, so this can be removed. That is, we only reserve a state A-> State B require a minimum number of steps in the path (my algorithm only solves the optimal movement, of course, there are also many people need to be optimally promoted). In this way, we have got a more special map - tree.
For the search, everyone should be quite familiar. It can generally be divided into depth priority search and breadth priority search. Because the optimal solution I have to get (step), the basic idea of the algorithm I use belongs to the breadth priority search.
Framework of the algorithm:
// Indication once effective movement: indicates to a box, and promote him
Struct validstep {
Position P;
Direction D;
Validstep (): p (-1), d (east) {}
ValidStep (int PP, Direction DD): P (PP), D (DD) {}
}
TypedEf Vector
Int solidboxyRoom (Boxroom Room, SolveResult & Path) {
/ / Save the root state
Solvestate StartState (Room);
Solvesearchtree SearchTree (StartState);
Solvestate contains BoxroomState, which is saved in SolveSearchTree, which will be discussed later.
// The limit of the number of steps, each increment, this guarantee is the best way to solve the number of steps
INT LIMIT = room.gettotlestep ();
Bool no_solution;
Do {
Solvestate curState = startstate;
INT CurDepth = -1; // Save INDEX of each layer has been searched
Vector
NO_SOLUTION = True;
LIMIT ;
Do {
Curdepth;
// At the beginning, the initial status has not yet been opened
IF (CurDepth! = 0) {
// Search this layer for the first time, let IndexList [curdepth] = -1
IF ((int) indexlist.size () <= curdepth) indexlist.push_back (-1);
Searchtree.getnextchild (CurDepth - 1, IndexList [curdepth-1], indexlist [curdepth], curState;
// This layer has not been able to get available nodes.
IF (IndexList [curdepth] == -1) {
// I have already gone
IF (CurDepth <= 1) Break;
//what? did nothing? Abolished this
IF (no_solution)
SearchTree.set_disabled (CurDepth - 1, IndexList [CurDepth - 1]);
// I didn't come back, go back
CurDepth- = 2; Continue;
}
}
// has exceeded the depth limit, other nodes of the same depth
IF (Limit NO_SOLUTION = FALSE; --CurDepth; Continue; } Room.LoadState (CURSTATE.ROOMSTATE); IF (curState.isfinished) { SolveResult Result; For (int i = curdepth; i> 0; i = curState.depth) { Result.push_back (curState.laststep); Searchtree.Getfather (CURSTATE.DEPTH, CURSTATE.DEPTHINDEX, CURSTATE); } Path.Insert (Path.end (), Result.Rbegin (), Result.Rend ()); Return room.gettotlestep (); } // Expand a node, if you have not yet exposed IF (searchtree.have_not_been_expanded (curdepth, indexlist [curdepth)) { // Expand this node Boxroom :: BoxroomState TmpState; Room.SAVESTATE (TMPSTATE); For (position i = 0; i IF (Room.InsNotbox (i)) Continue; / / Indicate four directions For (int J = 0; j <4; j) { Position nman = i - room.getoffset (static_cast IF (Room.goto (NMAN)! = -1) { // Note that ISBOXROOMDEAD, it turns out that the quality of this function can greatly affect our search range to affect our solving speed. IF ((static_cast && isboxOMDead (room)) { Solvestate SS (Room); Ss.laststep = validstep (nman, static_cast } Room.LoadState (TmpState); } } } Searchtree.set_expanded (CurDepth, IndexList [CurDepth]); NO_SOLUTION = FALSE; } WHILE (TRUE); } while (! no_solution); // Solve failure Return -1; } State tree and haveh table Notice that the above code is: Solvestate StartState (Room); Solvesearchtree SearchTree (StartState); I have used Solvestate, SolveSearchtree two classes to save and organize status. It is mentioned above, our algorithm is to judge that the state has already appeared, so how efficient search is a problem. If the state is saved directly in the tree, then the search will consume a lot of time. Let's take a look at the definition of Solvestate: Struct solid. { Boxroom :: BoxroomState RoomState; Int hash; INT depth; INT depthindex; Bool isfinished; Validstep laststep; Solvestate (const boxroom & room); BOOL Operator == (const solidate & ba) const { Return hash == oscn.hash && roomstate == os.roomstate; } Inline int gettotlestep () const {return roomstate.gettotlestep (); Inline void settotlestep (int s) {roomstate.SettotLestep (s); } It is just a packaging of the Boxroom :: boxroomState type. RoomState saves the status value; in order to map the tree back from the node, depth, depthindex saves the necessary information in the tree; isFinished In order to avoid calling boxroom :: isfinished (); LastStep Represents from the parent status to this state, porter How should I move. There is also a member hash. If you look at the name, it is related to the Hash table, yes, it is the HASH value of this state, which means that we are separated from the relationship between the node's storage and the power-saving. Come see SolveSearchtree, you will understand: Class solvesearchtree { Class statelib { Typedef Vector Vector PUBLIC: STATELIB: M_HASH_TABLE (Hash_SIZE (Rank)) {} INT Add_State (Const Solvestate & ns); Solvestate & Get_State (int StateIndex); Struct node { INT StateIndex; // Status index value in STATELIB Vector Int FatherIndex; BOOL IS_EXPANDED; BOOL IS_DISABED; Node (): is_expanded (false), IS_DISABED (FALSE) {} } // Similar to a generalized form as a tree representation. Data [n] represents the ninth layer of the tree, DATA [N] [M] represents the mth member of the ninth layer Vector Solvestate DummyState; PUBLIC: SolveSearchtree (Solvestate & R); Void Insert (int FatherDepth, Int FatherIndex, Solvestate &); Void getNextchild (int FatherDepth, int FatherIndex, Int & LastchildIndex, Solvestate &); Void getfather (int CHildepth, Int ChildIndex, Solvestate &); BOOL HAVE_NOT_BEEN_EXPANDED (int Depth, int index) const {return! (data [defth] [index] .is_expanded); Void set_expanded (int defth, int index) {data [defth] [index] .is_expanded = true; BOOL HAVE_NOT_BEEN_DISABED (int Depth, int index) const {return! (data [defth] [index] .is_disabled); Void set_disabled (int defth, int index); } as the picture shows: By calling get_state with StateIndex we can get the only Solvestate, add a new state through add_state, then the power of the Hash table is displayed: #define hash_rank 16 #define hash_size (rank) (1 << Rank) // Demand mode for a value is smaller than have Hash_Size #define hash_mod (hash) (Hash & ((1 << Hash_Rank) - 1)) ...... INT Add_State (const solidate & ns) { Hashnode & data = m_hash_table [ns.hash]; Hashnode :: item.begin (), data.end (), ns); Long H1; IF (iter == data.end ()) { Data.push_back (ns); H1 = (long) DATA.SIZE () - 1; Return (H1 << Hash_Rank) ns.hash;} else { IF (ns.gettotlestep () <(* iter) .gettotlestep ()) { H1 = (long) (iTER - data.begin ()); (* iTer) .SettotLestep (ns.gettotLestep ()); (* iTer) .laststep = ns.laststep; Return - ((H1 << Hash_Rank) ns.hash); } // Magic Number, indicating that this new state cannot be added because there is an equivalent state of the number of steps. // Because Hash! = 0, the following (H1 << Hash_rank) ns.gethash () will definitely equalize 0 Return 0; } } Solvestate & Get_State (int StateIndex) { Hashnode & data = m_hash_table [hash_mod (stateIndex)]; Return Data [StateIndex >> Hash_Rank]; } StateIndex is increasing speed, and its idea is not difficult to understand. Through the Hash table we can greatly reduce the time of searching, then what is the Hash value? I have chosen a fairly simple way: Solvestate :: Solvestate (Const Boxroom & Room): Hash (0) { Room.SAVESTATE (RoomState); ISFINISHED = Room.isfinished (); // Seeking Hash value For (int i = 0; i IF (Room.isbox (i)) { Hash = i * (i 1) * (i 2); Hash = hash_mod (hash); } } } Oh, simple, there must be a better Hash value, but here I steal it too lazy. The INSERT operation of the tree is responsible for the processing of the equivalent node, ensuring the equivalent node only retains the best cloth: Void SolvesearchTree :: Insert (int FatherDepth, Int FatherIndex, Solvestate & ss) { INT newildStateIndex = statelib.add_state (ss); // This state already exists, and the previous number of steps is better IF (NewchildStateIndex == 0) Return; // This state is not a new state, but it is better than the previous steps. IF (NewChildStateIndex <0) { NewChildStateIndex = -newchildstateindex; Solvestate & ts = statelib.get_state (NewChildStateIndex); Set_disabled (ts.depth, ts.depthindex); } IF ((int) data.size () <= fatherDepth 1) data.push_back (vector Node childNode; ChildNode.StateIndex = NewChildStateIndex; ChildNode.fatherIndex = FatherIndex; Data [FatherDepth 1] .push_back (childnode); INT newildDepthIndex = (int) Data [FatherDepth 1] .size () - 1; Solvestate & Ts = statelib.get_state (NewChildStateIndex); Ts.Depth = FatherDepth 1; Ts.Depthindex = NewChildDepthindex; Data [FatherDepth] [FatherIndex] .children.push_back (NewchildDepthIndex); } The GetNextChild operation of the tree is going to skip the branches that have been abolished: Void SolveSearchtree :: GetNextchild (int FatherDepth, Int FatherIndex, Int & LastchildIndex, Solvestate & RT) { Vector Vector IF (LastchildIndex == -1) { iTer = childindex.begin (); } else { iter = find (childIndex.begin (), childindex.end (), lastchildindex) 1; } Do { IF (iter == childIndex.end ()) { LastChildIndex = -1; Rt = DummyState; Return; } else { LastchildIndex = * ip; IF (Data [FatherDepth 1] [LastChildIndex] .is_disabled) { iTer; CONTINUE; } Rt = statelib.get_state (Data [FatherDepth 1] [LastChildIndex] .StateIndex); Return; } WHILE (TRUE); } Deadlock detection All is ready except for the opportunity. We are still a IsBoxroomDead function. The dead lock is once the box is pushed to some locations, and some boxes can no longer promote or cannot be pushed to the purpose, such as four boxes 2 × 2 placed. Instead of pushing the box masters, the deadlock is very sensitive, so that they do not know some situation, this is one of the reasons why the master is higher than the common man. Of course, I am not a master of the box, so I only give two simple judgment rules: Rule 1: #B # # b # ## #b B # BB BB BB # B # #b # bb #b B # ## BB BB Where b means the box, # 表示. If there is any case above, then a certain deadlock Rule 2: The number of boxes on the edge is greater than the number of targets on the edge. For example, as follows: ############# # T t b b # T represents the target. It may be disappointed that my program only solves the judgment of these two obvious deadlocks, v_v !. Online Ge Yonggu (http://notabdc.vip.sina.com) There is a program that is automatically solved by box, and its program has a fairly advanced deadlock detection algorithm, but unfortunately no source code. So this part can only be expanded in detail. Conclusion This program is still not very complete, my experiment proves that its complexity and the number of boxes have a big relationship. When the box is much more, it is not good to solve. The purpose of this article is just a framework for an algorithm, so it can solve some problems, and it is a full of brick. If you have any interested, please share with me: About the author: The author hellwolf (formerly: Miao Zhicheng), it is a freshman computer science freshman Southeast University. It is mainly interested in Linux programming and operating system (but there is not enough temporary level), and occasionally write some small games to entertain. Email: hellwolf_ok@seu.edu.cn MSN: Hellwolf_ok@hotmail.com QQ: 406418169 Blog: http://blog.9cbs.net/hellwolf Contact address: Dongnan University Pukou Campus 090043 Mailbox Zip code: 210088 true name: 志澄
