minesweeper-score.py

""" Disclaimer: This is just pseudocode that's really similar to Python.
"""

# Generiere ein Spielfeld. Hierbei ist `n` die Seitenlänge
# (das Feld ist quadratisch) und `b` die Anzahl der Minen.
field = Field(n, b)

# - `startFields` ist eine Liste mit allen möglichen Startfeldern. [1]
# - `solvedFields` ist eine Liste mit Lösungen für alle Felder `startFields`.
#    Bis zu diesem Punkt werden sie nur mit den Regeln der Logik gelöst. [2]
startFields = generateStartingFields(field)
solvedFields = map(startFields): x -> solveWithLogic(x)

# Sortiert alle Felder aus bei welchen man früh anfangen muss zu raten. [3]
# In diesem Fall zählt die Anzahl der geöffneten Zellen als Maß dafür.
# - `exclusionThreshold` ist der hierfür verwendete Schwellwert.
solvedFields = filter(solvedFields): x -> field.openCells > exclusionThreshold
solvedFields = withoutDuplicates(solvedFields)

# Nun wird jedes Feld Schritt für Schritt weiter gelöst. Hierbei wird immer
# einmal geraten und dann mit Logik fortgesetzt (soweit das möglich ist).
# - `scores` ist danach eine Liste welche die durchschnittlich
#    erreichbare Punktzahl für jedes Feld enthält.
# - `depthThreshold` stellt dar wie häufig geraten werden soll.
scores = map(solvedFields): x -> x.score + solve(x, depthThreshold)
averageScore = average(scores)

#
# `averageScore` enthält nun die im Durchschnitt
# erreichbare Punktzahl des Feldes `field`.
#


#
# Ein "Schritt" (step) ist folgendermaßen definiert:
# - Es wird erwartet dass das Feld (Parameter `field`) in einem Zustand ist
#   in welchem man durch Logik keine weitere Zelle mehr aufdecken kann. Der
#   erste Schritt liegt somit darin eine Zelle durch Raten aufzudecken.
# - Danach wird das Feld (soweit es geht) mit Logik weiter aufgedeckt.
#
# Die Funktion gibt alle Möglichkeiten zurück wie das Feld weiter aufgedeckt
# werden kann und zusätzlich die Anzahl an Punkten die dabei im Durchschnitt
# erreicht wird.
#
def step(field):
    # `permutations` enthält alle Möglichkeiten wie das Feld `field` weiter
    #  aufgedeckt werden kann indem nur eine Zelle geöffnet wird und diese
    #  Zelle einer der Zellen ist welche die geringste Wahrscheinlichkeit
    #  aufweisen eine Mine zu enthalten.
    guessCells = optimalGuesses(field)
    permutations = map(guessCells): cell ->
        copy(field).withOpened(cell)

    # In diesem Fall kann man nicht raten. Hier muss frühzeitig
    # abgebrochen werden damit später nicht durch 0 geteilt wird.
    if (count(permutations) is 0): return ([], 0)

    # Berechnet die durchschnittliche Anzahl an Punkten die man
    # bekommt wenn man eine der zuvor genannten Zellen aufdeckt.
    validPermutations = filter(permutations): x -> not x.hasOpenedMine
    guessScoreDeltas  = map(validPermutations): x -> x.score - field.score
    averageGuessScore = sum(guessScoreDeltas) / count(guessCells)

    # Nachdem einmal geraten wurde wird das Feld soweit mit Logik gelöst
    # wie es möglich ist. Desweiteren wird gespeichert wieviele Punkte man
    # dadurch für jedes Feld bekommt.
    (permutations, logicScoreDeltas) = map(permutations): x ->
        newField = solveWithLogic(x)
        scoreDelta = newField.score - x.score
        return (newField, scoreDelta)

    averageScore = averageGuessScore + average(logicScoreDeltas)
    return (permutations, averageScore)


#
# Deck das Feld weiter auf indem `guessDepth` Schritte ausgeführt werden.
# `guessDepth` stellt hierbei dar wie oft geraten werden darf.
#
# Die Funktion gibt die Punktzahl zurück die im Durchschnitt erreicht wird.
#
def solve(field, guessDepth):
    if (guessDepth is 0): return 0

    # Es muss nur einmal geraten werden oder es
    # gibt keine Stelle an der man raten kann.
    (permutations, averageScore) = step(field)
    if (guessDepth is 1 or isEmpty(permutations)):
        return averageScore

    nextScores = map(permutations): x -> solve(x, guessDepth - 1)
    return averageScore + average(nextScores)