Computerspieler

Bisher wurde sowohl für die Konsole, als auch für die grafische Benutzeroberfläche eine View vom Typ Spieler implementiert. Es handelte sich aber stets um denselben Typus, nämlich um einen menschlichen Spieler. In einem Spiel, wie »Schiffe versenken«, möchte man aber auch gegen eine künstliche Intelligenz (KI) spielen können. Der Begriff künstliche Intelligenz ist an dieser Stelle metaphorisch zu verstehen, tatsächlich sind die strategischen Anforderungen an einen Computerspieler in dem Spiel »Schiffe versenken« eher gering anzusiedeln.

Nichtsdestotrotz kann die Konzeption eines guten Computergegners eine Herausforderung darstellen. Ein guter Computerspieler muss ein Spielfeld bewerten können, er sollte seine Schüsse von einigen wichtigen Faktoren abhängig machen. Dazu zählt die Einsicht das Schiffe nicht unmittelbar nebeneinander oder diagonal liegen können.

Ein Problem von Computerspielern ist, dass der Computer so wie ein Mensch, Benutzereingaben machen muss. Er muss auf Spielfelder des Gegners schießen und Felder markieren können. Das Interface PlayerInterface definiert die Methode move. Diese Methode bietet sich als zentrale Anlaufstelle für die Züge des Computers an. Während der menschliche Spieler in dieser Methode zur Eingabe von Befehlen aufgefordert wird, sollte ein Computerspieler an dieser Stelle seine Eingaben ebenfalls durchführen können.

Log

Alle Computerspieler haben eines gemeinsam. Sie besitzen keine Benutzeroberfläche mit einer Ansicht. Sie benötigen auch keine optische Ansicht, schließlich kennt der Computer die internen Daten. Eine View, die einen Computerspieler repräsentiert, muss seine Daten weder auf die Konsole, noch über eine GUI ausgeben. Die View eines Computerspielers loggt allerdings Informationen in eine Datei. Das Logging ist eine wesentliche Eigenschaft von Computer-Views.

Die Logik eines Computerspielers kann vollständig in der View implementiert werden, schließlich repräsentiert die View einen Spieler. Wir wollen in den nächsten Kapiteln drei verschiedene Views, also drei unterschiedliche Computerspieler implementieren.

Dummer Computerspieler

Bei dem „dummen“ Computerspieler handelt es sich um den primitivsten Computergegner. Er berücksichtigt weder die Tatsache das Schiffe nicht diagonal positioniert sein können, noch das Schiffe niemals direkt nebeneinander liegen. Der „dumme“ Computerspieler schießt vollkommen willkührlich auf das Spielfeld des Gegners. Seine einzige „Fähigkeit“ ist das er niemals auf dasselbe Feld schießt. Dies wird vom Model unterbunden.

Die Methode move des „dummen“ Computerspielers ist wie folgt definiert:

/**
 * Performs a computer move.
 */
@Override
public void move()
{
    // Get the board size
    Coordinate size = getModel().getBoardSize( getId() );
 
    // Get a random coord instance
    Coordinate c = Coordinate.getRandom( size.getX(), size.getY() );
 
    // Return the shot
    getController().shoot( this, c );
}

Es ist zu erkennen das zufällige Koordinaten ausgewählt werden um anschließend mithilfe des Controllers den Schuss auszuführen.

Kluger Computerspieler

Der „kluge“ Computerspieler agiert deutlich fortschrittlicher. Er berücksichtigt das ein Schiff nicht diagonal positioniert sein kann. Außerdem kann er Felder markieren, sobald ein Schiff versenkt wurde. Auf diese Weise schließt er Felder aus, die unmittelbar neben einem versenkten Schiffen liegen. Dadurch wird eine elementare Regel beachtet, nämlich das Schiffe niemals unmittelbar nebeneinander liegen.

Die Methode move des „klugen“ Computerspielers ist wie folgt definiert:

/**
 * Performs a computer move.
 */
@Override
public void move()
{
    // Get the board size
    Coordinate size = getModel().getBoardSize( getId() );
    Coordinate c = null;
 
    // First check the game board and search for destroyed ships.
    // Mark the surrounding of the ship if this wasn't already done.
    for(int y = 0; y <= size.getY(); y++) {
        for(int x = 0; x <= size.getX(); x++) {
            try {
                // Get and check this field if it's a destroyed ship
                if( getModel().getEnemyBoardFieldState( getId(), new Coordinate(x, y) ).equals(FieldState.DESTROYED_SHIP) ) {
                    // Return a mark command if we found an unknown coord around this destroyed ship
                    if( (c = checkFieldPeriphery( new Coordinate(x, y), size, FieldState.UNKNOWN )) != null )
                        getController().mark( this, c );
                }
            } catch( FieldOperationException e ) {
                showMessage( e.getMessage() );
            }
        }
    } 
 
    // Evaluate the current board of the enemy
    Evaluation eval = new Evaluation( getModel().getEnemyBoard( getId() ) );
 
    // Get a possible coord from this evaluation
    c = eval.getProbableCoordinate();
 
    // Return the shot
    getController().shoot( this, c );
}

Auf den ersten Blick ist zu erkennen, dass die Methode bereits deutlich komplexer ist. Der „kluge“ Computerspieler markiert mithilfe der Methode checkFieldPeriphery Felder um ein zerstörtes Schiff herum. Die Methode ermittelt alle unbekannten Felder und gibt die Koordinaten zurück.

Der „kluge“ Computerspieler verwendet darüberhinaus eine separate Klasse namens Evaluation. Die Klasse Evaluation bewertet ein Spielfeld. So werden beispielsweise Felder, die unmittelbar neben einem getroffenen Feld liegen in ihrer Prioriät heraufgesetzt. Felder die markiert wurden, erhalten die Priorität 0. Die Klasse stellt eine Methode namens getProbableCoordinate zur Verfügung. Diese Methode liefert die am höchsten bewertete Koordinate aus dem Spielfeld.

In dem unten illustrierten Quelltext ist die Methode generatePriorityField der Klasse Evaluation gelistet. Diese Methode generiert die Bewertung für ein Spielfeld.

/**
 * Generates a priority field for the next shot command. Such a field can
 * look like this one:
 * 
 * <code>
 * UUUUU                20102
 * *UUU*   Priorities   02120
 * UUUUU       =>       20103
 * --UU*                00100
 * X-UU*                00100
 * </code>
 * 
 * @param enemyBoard the enemy board
 */
private void generatePriorityField(EnemyBoard enemyBoard)
{        
    int height = enemyBoard.getHeight();
    int width = enemyBoard.getWidth();
 
    // We use an existent field for performance issues. Initialize only one time.
    priorityBoard_ = new Priority[height][width];
 
    // First initialize all fields with a low priority
    for( int y = 0; y < height; y++ ) {
        for( int x = 0; x < width; x++ ) {
            priorityBoard_[y][x] = Priority.LOW;
        }
    }        
 
    // Search for all *non* UNKNOWN fields. This fields have a priority of 
    // ZERO (0) and therefore we do *not* shot on them.
    for(int y = 0; y < height; y++) {
        for (int x = 0; x < width; x++) {
            if(enemyBoard.getField( x, y ).getFieldState() != FieldState.UNKNOWN)
                priorityBoard_[y][x] = Priority.ZERO;
        }
    }
 
    // Now comes the second step. We search for all HIT fields and
    // set the field above, below, right and left of this field to MEDIUM if
    // it is not ZERO or to HIGH if it is already MEDIUM.
    // There can't be a ship diagonal of a HIT field, therefore
    // we set this field to ZERO. This automatically excludes long
    // ships and elimates them.
    for( int y = 0; y < height; y++ ) {
        for( int x = 0; x < width; x++ ) {
            // Search for a HIT field
            if( enemyBoard.getField( x, y ).getFieldState() == FieldState.HIT ) {
 
                // ------------------------------------------------                  
                // First look at the vertical and horizontal fields
 
                // Above
                if( (y - 1) >= 0 ) {
                    // Check if not ZERO
                    if( priorityBoard_[y - 1][x] != Priority.ZERO ) {
                        // Check if already MEDIUM
                        if (priorityBoard_[y - 1][x] == Priority.MEDIUM) {
                            priorityBoard_[y - 1][x] = Priority.HIGH;
                        } else {
                            priorityBoard_[y - 1][x] = Priority.MEDIUM;
                        }
                    }
                }
 
                // Below
                if( (y + 1) < height ) {
                    // Check if not ZERO
                    if (priorityBoard_[y + 1][x] != Priority.ZERO) {
                        // Check if already MEDIUM
                        if (priorityBoard_[y + 1][x] == Priority.MEDIUM) {
                            priorityBoard_[y + 1][x] = Priority.HIGH;
                        } else {
                            priorityBoard_[y + 1][x] = Priority.MEDIUM;
                        }
                    }
                }
 
                // Right side
                if( (x + 1) < width ) {
                    // Check if not ZERO
                    if (priorityBoard_[y][x + 1] != Priority.ZERO) {
                        // Check if already MEDIUM
                        if (priorityBoard_[y][x + 1] == Priority.MEDIUM) {
                            priorityBoard_[y][x + 1] = Priority.HIGH;
                        } else {
                            priorityBoard_[y][x + 1] = Priority.MEDIUM;
                        }
                    }
                }
 
                // Left side
                if( (x - 1) >= 0 ) {
                    // Check if not ZERO
                    if (priorityBoard_[y][x - 1] != Priority.ZERO) {
                        // Check if already MEDIUM
                        if (priorityBoard_[y][x - 1] == Priority.MEDIUM) {
                            priorityBoard_[y][x - 1] = Priority.HIGH;
                        } else {
                            priorityBoard_[y][x - 1] = Priority.MEDIUM;
                        }
                    }
                }                                 
 
                // -----------------------------------                   
                // Now set all diagonal fields to ZERO      
 
                // Right upper corner
                if( (y - 1) >= 0 && (x + 1) < width ) {
                    priorityBoard_[y - 1][x + 1] = Priority.ZERO;
                }
 
                // Left upper corner
                if( (y - 1) >= 0 && (x - 1) >= 0 ) {
                    priorityBoard_[y - 1][x - 1] = Priority.ZERO;
                }
 
                // Right lower corner
                if( (x + 1) < width && (y + 1) < height ) {
                    priorityBoard_[y + 1][x + 1] = Priority.ZERO;
                }
 
                // Left lower corner
                if( (x - 1) >= 0 && (y + 1) < height ) {
                    priorityBoard_[y + 1][x - 1] = Priority.ZERO;
                }                                         
            }   
        }
    }   
}

Genialer Computerspieler

Die Krönung des Computergegners ist der „geniale“ Computerspieler. Der „geniale“ Computerspieler vereint alle Eigenschaften des „klugen“ Computerspielers und geht sogar noch einen Schritt weiter.

/**
 * Performs a computer move.
 */
@Override
public void move()
{  
    // Get the board size
    Coordinate size = getModel().getBoardSize( getId() );
    Coordinate c = null;
 
    // First check the game board and search for destroyed ships.
    // Mark the surrounding of the ship if this wasn't already done.
    for( int y = 0; y <= size.getY(); y++ ) {
        for( int x = 0; x <= size.getX(); x++ ) {
            try {
                // Get and check this field if it's a destroyed ship
                if( getModel().getEnemyBoardFieldState( getId(), new Coordinate(x, y) ).equals(FieldState.DESTROYED_SHIP)) {
                    // Return a mark command if we found an unknown coord around this destroyed ship
                    if( (c = checkFieldPeriphery( new Coordinate(x, y), size, FieldState.UNKNOWN )) != null)
                        getController().mark( this, c );
                }
            } catch(FieldOperationException e) {
                showMessage( e.getMessage() );
            }
        }
    } 
 
    // Evaluate the current board of the enemy
    Evaluation eval = new Evaluation( getModel().getEnemyBoard( getId() ) );
 
    // Get a possible coord from this evaluation
    c = eval.getProbableCoordinate();        
 
    // Make sure that we didn't found a coord where a ship was hit in the
    // surrounding. Only then use backtracking.
    if( checkFieldPeriphery( c, size, FieldState.HIT ) == null ) {  
 
        Fleet eFleet = getModel().getAliveEnemyFleet( getId() );
 
        // Use recursive backtracking if less than 4 ships in the enemys fleet 
        // are alive. Otherwise we will use the evaluation coord (Performance)
        if( eFleet.getTotalShips() < 4 ) {                
            showMessage( getModel().getString( "BATTLESHIP.START_BACKTRACKING" ) );
 
            // Create a new backtracking instance
            Backtracking bt = new Backtracking( getModel().getEnemyBoard( getId() ), eFleet );
 
            if( bt.calcProbabilities() ) {
                c = bt.getProbableCoordinate();
            }      
        }
    }
 
    // Return the shot
    getController().shoot( this, c );
}

Ein „genialer“ Computerspieler nutzt neben der Evalution eines Spielfeldes auch einen bekannten Algorithmus - das sogenannte Backtracking. Der Begriff Backtracking (engl. Rückverfolgung) bezeichnet eine Problemlösungsmethode innerhalb der Algorithmik.

Backtracking geht nach dem Versuch-und-Irrtum-Prinzip vor, d. h. es wird versucht, eine erreichte Teillösung schrittweise zu einer Gesamtlösung auszubauen. Wenn absehbar ist, dass eine Teillösung nicht zu einer endgültigen Lösung führen kann, wird der letzte Schritt bzw. die letzten Schritte zurückgenommen, und es werden stattdessen alternative Wege probiert. Auf diese Weise ist sichergestellt, dass alle in Frage kommenden Lösungswege ausprobiert werden können. Mit Backtracking-Algorithmen wird eine vorhandene Lösung entweder gefunden, oder es kann definitiv ausgesagt werden, dass keine Lösung existiert. Backtracking wird meistens am einfachsten rekursiv implementiert und ist ein prototypischer Anwendungsfall von Rekursion.

Die Klasse Backtracking sucht mithilfe des gleichnamigen Algorithmus nach Schiffen. Sobald dem Gegner weniger als 4 Schiffe verbleiben, wird der Algorithmus aktiv. Dabei versucht der Algorithmus alle möglichen Schiffspositionierungen in Erfahrung zu bringen. Der Computer weiß welche Schiffe dem Gegner verblieben sind. Mit diesen Informationen geht er alle möglichen Kombinationen durch, indem er versucht die restlichen Schiffe nacheinander auf dem Spielfeld zu positionieren.
Gelingt ihm das, inkrementiert er auf einem Feld mit Wahrscheinlichkeiten auf den entsprechenden Koordinaten die Zahlen. Diese Operation wird für alle möglichen Schiffspositionierungen durchgeführt. Am Ende entsteht dadurch ein zweidimensionales Zahlenfeld, wobei die erfolgversprechendsten Felder besonders hohe Zahlen aufweisen, weil die Wahrscheinlichkeit das ein Schiff diese Koordinaten besitzt hoch ist.

Der Backtracking Algorithmus arbeitet rekursiv. Dabei ensteht ein Suchbaum der folgenden Art.

Alle „Zweige“ die nicht abgeschlossen werden, d.h. bei denen die Positionierung aller verbliebenen Schiffe fehlschlägt werden nicht weiter berücksichtigt. Die Klasse Backtracking implementiert den Suchalgorithmus in der Methode placeShip.

/** 
 * This is the recursive function for the backtracking algorithm that 
 * tests all possible ship constellations. It will build a search tree 
 * in depth, like this one:
 * 
 * <pre>
 * 
 *           1
 *         / | \
 *        2  7  8
 *      / |     | \
 *     3  6     9  12
 *   / |        |   \
 *  4  5       10   11
 * 
 * </pre>
 * 
 * @param shipNumber Number of the ship that is currently to be set
 */
private void placeShip(int shipNumber)
{
    // Get the current ship
    Ship ship = backtrackingBoard_.getFleet().getShipAt(shipNumber);
 
    // Cycle through the whole field and put the ship whereever possible.
    // Then recursively call this method with the next ship if this one 
    // is not the last one.
    for( int y = 0; y < backtrackingBoard_.getHeight(); y++ ) {
        for( int x = 0; x < backtrackingBoard_.getWidth(); x++ ) {
 
            ALIGNMENT:
            for( int align = 0; align < 2; align++ ) {   // If align 0 -> horizontally              
 
                int xpos = x;
                int ypos = y;
                int endpos = 0;
 
                // If ship cannot be positioned on the current coords then continue.
                if (align == 0) {
                    endpos = xpos + ship.getLength() - 1;
 
                    if (endpos >= backtrackingBoard_.getWidth())
                        continue ALIGNMENT;
 
                    for (int t = xpos; t <= endpos; t++)
                        if (backtrackingBoard_.getField(t, ypos).getFieldState() == FieldState.MARKED)
                            continue ALIGNMENT;
 
                } else {
                    // Test vertical ship placing
                    endpos = ypos + ship.getLength() - 1;
 
                    if (endpos >= backtrackingBoard_.getHeight())
                        continue ALIGNMENT;
 
                    for (int t = ypos; t <= endpos; t++)
                        if (backtrackingBoard_.getField(xpos, t).getFieldState() == FieldState.MARKED)
                            continue ALIGNMENT;
                } 
 
                // Was it possible to put the ship on the coordinates with alignment
                if( backtrackingBoard_.placeShip( ship.getShipType(), new Coordinate( x, y ), (align != 0) ) ) {
 
                    // Is the currently ship the last ship to put on the field?
                    if( shipNumber >= backtrackingBoard_.getFleet().getTotalShips() - 1 ) {
                        // We have an Endnode
 
                        // If yes, evaluate the generated ship-constellation
                        evalProbabilityBoard();
 
                        // Now delete this ship again, so we can move back in the 
                        // search tree and try to place this ship at other coords
                        backtrackingBoard_.removeShip( ship, FieldState.UNKNOWN );
                    } else {
 
                        // If there are more ships to be put on the board,
                        // go deeper in the tree.
 
                        // Call the placeShip method recursively with the next ship in the fleet
                        placeShip( shipNumber + 1 );
 
                        backtrackingBoard_.removeShip( ship, FieldState.UNKNOWN );
                    }
                }
            }
        }
    }
}

Bei der Tiefensuche werden bei maximal z möglichen Verzweigungen von jeder Teillösung aus und einem Lösungsbaum mit maximaler Tiefe von N im schlechtesten Fall 1 + z + z² + z³ + ... + z^N Knoten erweitert.

Die Tiefensuche und somit auch Backtracking haben im schlechtesten Fall nach der O-Notation mit O(z^N) eine exponentielle Laufzeit. Das ist eine katastrophale Zeitkomplexität. Bei großer Suchtiefe n und Verzweigungsgrad z > 1 dauert die Suche somit oft sehr lange. Daher ist das Backtracking primär für Probleme mit einem kleinen Lösungsbaum geeignet, weshalb der Algorithmus erst bei vier verbliebenen Schiffen zum Einsatz kommt.

Mit dem „genialen“ Computerspieler endet die Programmierung der Views. Im Quellcodepaket sind alle implementierten Klassen für die Computerspieler, die Konsole und die GUI zu finden. Das Package eu.codeplanet.battleship.view enthält alle Views, auch die Klassen und Methoden, die in dem Artikel nicht explizit angesprochen wurden. Der letzte Schritt bei dem Entwurf von Battleship betrifft den Controller. Diesem wollen wir uns im nächsten Kapitel widmen.