pythonsearchlogicsequenceplanning

How to generate move sequences from initial state to goal state in python?


I have 8 rows x 7 columns grid. There are 2 players and each player controls 5 colored blocks and 1 colored ball. Different player have different colored blocks and ball (i.e. player 0 has white colored blocks and white ball, player 1 has black colored blocks and black ball). Each square in the board is represented in integer, the most bottom row of the board are 0-6 from left to right, a row above it are 7-13 from left to right, the pattern continues like that until the most upper row of the board with 49-55 from left to right. The block pieces move like a knight in chess. A player’s ball can move from the block piece holding it to a block piece of the same color along vertical, horizontal, or diagonal channels (same as a queen in chess). In a single turn, a player may pass their ball between same color block pieces an unlimited number of times. This is what the grid looks like:

grid

If I want to move white block from 1 to 23, this is the sequence move:

[(((1, 2, 3, 4, 5, 3, 50, 51, 52, 53, 54, 52), 0), (0, 14)), 
(((14, 2, 3, 4, 5, 3, 50, 51, 52, 53, 54, 52), 1), (11, 51)), 
(((14, 2, 3, 4, 5, 3, 50, 51, 52, 53, 54, 51), 0), (0, 23)), 
(((23, 2, 3, 4, 5, 3, 50, 51, 52, 53, 54, 51), 1), (11, 52)), 
(((23, 2, 3, 4, 5, 3, 50, 51, 52, 53, 54, 52), 0), None)]

The white ball from 3 can be at 22 in only one turn, because it can move from 3 to 1 and then from 1 to 22 (i.e. following the rule of ball movement in a single turn).

I have created a search function like this:

def find_sequence(initial_state, end_state):    
    queue = deque([(initial_state, None, None, 0)])
    visited = set([initial_state])
    parents = {}    
    while queue:
        state, prev_state, move, player_turn = queue.popleft()    
        if state[:5] == end_state[:5] and state[5] == end_state[5]:            
            path = []
            while state is not None:
                path.append((state, player_turn, move))
                state, move, player_turn = parents.get(state, (None, None, None))
            sequence = list(reversed(path[1:]))
            sequence_without_turn = [(state, move) for state, _, move in sequence]
            formatted_sequence = [((state, move[0]), move[1]) for state, move in sequence_without_turn]
            return formatted_sequence        
        for next_state in get_next_states(state, player_turn):
            if next_state not in visited:
                visited.add(next_state)
                parents[next_state] = (state, (player_turn, find_move(state, next_state)), 1 - player_turn)
                queue.append((next_state, state, (player_turn, find_move(state, next_state)), 1 - player_turn))    
    return None
        
def find_move(state1, state2):
    for i in range(len(state1)):
        if state1[i] != state2[i]:
            return (i, state2[i])
    return None

But when I test it using this:

initial_state = (1, 2, 3, 4, 5, 3, 50, 51, 52, 53, 54, 52)
end_state = (23, 2, 3, 4, 5, 3, 50, 51, 52, 53, 54, 52)
print(find_sequence(initial_state, end_state))

The output only shows part of the expected result:

[(((1, 2, 3, 4, 5, 3, 50, 51, 52, 53, 54, 52), 0), (0, 14)), 
(((14, 2, 3, 4, 5, 3, 50, 51, 52, 53, 54, 52), 1), (6, 37)), 
(((14, 2, 3, 4, 5, 3, 37, 51, 52, 53, 54, 52), 0), (0, 23))]

It still miss this part:

[(((23, 2, 3, 4, 5, 3, 37, 51, 52, 53, 54, 52), 1), (6, 50)), 
(((23, 2, 3, 4, 5, 3, 50, 51, 52, 53, 54, 52), 0), None)]

What should I fix with my code so it can shows the complete sequences?


Solution

  • Turns out I need to restore the sequence in order to make the final sequence completed (i.e. this includes handling more than 1 goal task). So I add this function to help the existing search function:

    def find_sequence_with_restore(self):
            print(self.initial_board_state.state)
            print(self.goal_board_state.state)
            initial_state = tuple(self.initial_board_state.state)
            end_state = tuple(self.goal_board_state.state)   
            differences = sum(1 for a, b in zip(tuple(self.initial_board_state.state), tuple(self.goal_board_state.state)) if a != b)
            if differences < 2:
                sequence = self.find_sequence(initial_state, end_state)
                if sequence:
                    final_state = sequence[-1][0][0]
                    restore_sequence = self.restore_initial_positions(end_state, final_state, initial_state)
                    sequence.extend(restore_sequence)
                    if all(pos in initial_state or pos in end_state for pos in sequence[-1][0][0]):
                        sequence.append(((sequence[-1][0][0], 1 - sequence[-1][0][1]), None))
                    else:
                        sequence.append(((sequence[-1][0][0], sequence[-1][0][1]), None))
                return sequence
            elif differences == 0:
                return [(((1, 2, 3, 4, 5, 3, 50, 51, 52, 53, 54, 52), 0), None)]
            else:
                return None