Spiele

Du hast eine Idee für ein Projekt?
Antworten
Simon_2468
User
Beiträge: 6
Registriert: Dienstag 17. November 2020, 19:04

Hallo liebe Community,
in Rahmen meines Informatik Labors, soll ich ein Programm schreiben, welches das Spiel Khun Pan lösen kann.
Es gibt mehrere Möglichkeiten um an die Lösung zu kommen, jedoch erscheint mir die Breitensuche als die Beste von denen.
Es ist eine interessante Aufgabenstellung, doch leider habe ich kaum mit Python gearbeitet.
Ich bin offen für Umsetzungsvorschläge und wäre dankbar für Hilfe beim Lösen dieses Problems.
Mit freundlichen Grüßen
Simon. :D
einfachTobi
User
Beiträge: 491
Registriert: Mittwoch 13. November 2019, 08:38

Wie sieht dein Code aus? Was ist die konkrete Frage? Wo kommst du nicht weiter?

Als Einstieg bietet sich das offizielle Python-Tutorial an.
Simon_2468
User
Beiträge: 6
Registriert: Dienstag 17. November 2020, 19:04

Dieses Programm dient als Orientierung.
Dort sind gleich zwei Algorithmen untergebracht, einmal die Breitensuche und einmal A*, wobei A* nochmal zwei weitere Möglichkeiten aufweist.
Manhatten distance und counts the numbers of misplaced tiles.
http://www.khunpan.de/ ...hier ist der Link zum eigentlichen Spiel.
Ich habe es erst mit A* und der Manhatten distance versucht, jedoch brauchte ich viele Regeln wie ich die Steine bewegen darf und es war nicht der optimale Lösungsweg.
Es gibt darüber hinaus gleiche Steine, die keine feste Position haben und das erschwert das Ganze.
Ich habe mir ein Konzept zur Breitensuche überlegt, habe aber die Befürchtung, dass der Rechenaufwand unverhältnismäßig hoch wird, da es bei Khun Pan deutlich mehr Möglichkeiten gibt als im Beispiel.

Code: Alles auswählen


## Quelle
## https://github.com/MilanPecov/15-Puzzle-Solvers

import pprint
pp = pprint.PrettyPrinter(indent=4)

def puzz_breadth_first(start,end):
    """
    Breadth First algorithm
    """
    front = [[puzzle]]
    expanded = []
    expanded_nodes=0
    while front:
        i = 0
        for j in range(1, len(front)):    #minimum
            if len(front[i]) > len(front[j]):
                i = j
        path = front[i]         
        front = front[:i] + front[i+1:]
        endnode = path[-1]
        if endnode in expanded: continue
        for k in moves(endnode):
            if k in expanded: continue
            front.append(path + [k])
        expanded.append(endnode)
        expanded_nodes += 1
        if endnode == end: break
    print ("Expanded nodes:", expanded_nodes)
    print ("Solution:")
    pp.pprint(path)

def puzz_astar(start,end):
    """
    A* algorithm
    """
    front = [[heuristic_2(start), start]] #optional: heuristic_1
    expanded = []
    expanded_nodes=0
    while front:
        i = 0
        for j in range(1, len(front)):
            if front[i][0] > front[j][0]:
                i = j
        path = front[i]
        front = front[:i] + front[i+1:]
        endnode = path[-1]
        if endnode == end:
            break
        if endnode in expanded: continue
        for k in moves(endnode):
            if k in expanded: continue
            newpath = [path[0] + heuristic_2(k) - heuristic_2(endnode)] + path[1:] + [k] 
            front.append(newpath)
            expanded.append(endnode)
        expanded_nodes += 1 
    print ("Expanded nodes:", expanded_nodes)
    print ("Solution:")
    pp.pprint(path)


def moves(mat): 
    """
    Returns a list of all possible moves
    """
    output = []  

    m = eval(mat)   
    i = 0
    while 0 not in m[i]: i += 1
    j = m[i].index(0); #blank space (zero)

    if i > 0:                                   
      m[i][j], m[i-1][j] = m[i-1][j], m[i][j];  #move up
      output.append(str(m))
      m[i][j], m[i-1][j] = m[i-1][j], m[i][j]; 
      
    if i < 3:                                   
      m[i][j], m[i+1][j] = m[i+1][j], m[i][j]   #move down
      output.append(str(m))
      m[i][j], m[i+1][j] = m[i+1][j], m[i][j]

    if j > 0:                                                      
      m[i][j], m[i][j-1] = m[i][j-1], m[i][j]   #move left
      output.append(str(m))
      m[i][j], m[i][j-1] = m[i][j-1], m[i][j]

    if j < 3:                                   
      m[i][j], m[i][j+1] = m[i][j+1], m[i][j]   #move right
      output.append(str(m))
      m[i][j], m[i][j+1] = m[i][j+1], m[i][j]

    return output

def heuristic_1(puzz): #bracuht 2600 Schritt, sehr lange
    """
    Counts the number of misplaced tiles
    """ 
    misplaced = 0
    compare = 0
    m = eval(puzz)
    for i in range(4):
        for j in range(4):
            if m[i][j] != compare:
                misplaced += 1
            compare += 1
    return misplaced

def heuristic_2(puzz): #schneller als heuristic_1
    """
    Manhattan distance
    """  
    distance = 0
    m = eval(puzz)          
    for i in range(4):
        for j in range(4):
            if m[i][j] == 0: continue
            distance += abs(i - (m[i][j]/4)) + abs(j -  (m[i][j]%4));
    return distance

if __name__ == '__main__':
    puzzle = str([[1, 2, 6, 3],[4, 9, 5, 7], [8, 13, 11, 15],[12, 14, 0, 10]])
    end = str([[0, 1, 2, 3],[4, 5, 6, 7], [8, 9, 10, 11],[12, 13, 14, 15]])
    #puzz_astar(puzzle,end)
    puzz_breadth_first(puzzle,end)

Benutzeravatar
__blackjack__
User
Beiträge: 13004
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

Breitensuche ist bei ≈100 Schritten bei der Lösung machbar, denke ich.
“Most people find the concept of programming obvious, but the doing impossible.” — Alan J. Perlis
Antworten