4. Flashcenhals im Programm

Flashcenhals im Programm

  • D

    Bei mir läuft es noch gar nicht, weil ich noch nicht genügend speicher zur verfügung gestellt habe. Aber es dauert definitiv viel länger als 3 Minuten.

    Ich denke du berechnest etwas viel und vor allem das ständige Klonen kostet Zeit. Aber genauer ahbe ich das noch nicht untersucht^^

    0
  • F

    Danke für deine Antwort
    Aber das Klonen ist doch notwendig oder gibt des da eine Möglichkeit

    0
  • S

    Hast du deinen Code schon mal mit einem Profiler untersucht?

    0
  • D

    26 Sekunden!

    Wie konnte das bei dir laufen? Ich bin in einer Endloschleifen geraten xD

    Beim clonen suchst du den Wert von (x, x)

    (wenn es imemr noch nicht geht, hab ich irgendwo noch was entscheidendes geändert, was ich aber geradenicht mehr finde)
    Schreib dann einfach nochmal. Ich werde heute abend meinen Quellcode posten(muss jetzt weg)

    0
  • F

    Ich muss jetzt leider auch weg und werde vor so nicht zum testen kommne, erst mal allen vielen dank.

    ich habe leider bisher noch nie mit profilern gearbeitet. nutze als entwicklungumgebung eclipser

    0
  • F

    Poste bitte mal deinen Code. Bei mir geht es leider nicht

    0
  • F

    Kannst du mir die Anzahl der Elemente in der Result Queue anzeigen lassen. Wie viele sind es bei dir ?

    Habe den Fehler gefunden aber bei mir sind es 1786 aber das ist nicht richtig

    0
  • D

    2754 (wieviele sollen es denn sein?)

    Application.java(ich hab die files etwas gekürtz(Kommentare etc.), damit ich einen besseren Überblick habe^^)

    import java.awt.Point;

public class Application {

    public static void main(String[] args) throws InterruptedException {

        long zeit1 = 0, zeit2 = 0;

        PlayingField playingField = new PlayingField();
        playingField.setFieldValue(2,2);
        playingField.getWinner();
        playingField.clone();

        ExpandField expandField = new ExpandField(playingField);
        System.out.println(expandField.ResultQueue.size());
        for(PlayingField pf : expandField.ResultQueue) {
        	for (Point p : pf.History) {
        		//System.out.print(p.x + "/" + p.y + "\t");
        	}
        	//System.out.println();
        }
    }
}

    ExpandField

    import java.awt.Point;
import java.util.Vector;
class ExpandField {

    public ExpandField(PlayingField field) {       
        Queue.add(field);
        while (Queue.size() > 0){
            ExpandNode(Queue.get(0));
            Queue.remove(0);
        }
    }

    public void ExpandNode(PlayingField field){
        Point nextField = new Point(UNDEFINED,UNDEFINED);

        do{
            nextField = getNextField(nextField);
            if (nextField.x != UNDEFINED){       
                if (field.getFieldValue(nextField.x, nextField.y) == PlayingField.DEFAULTVALUE){
                    PlayingField newField = field.clone();
                    newField.setFieldValue(nextField.x, nextField.y);

                    if (newField.getWinner() == PlayingField.NOTFINISHED){
                        Queue.add(newField);
                    }else{
                        ResultQueue.add(newField);
                    }
                }
            }

        } while (nextField.x != UNDEFINED);
    }

    private Point getNextField(Point start){

        if ((start.x == UNDEFINED) && (start.y == UNDEFINED)){
            return new Point(0,0);
        }

        if ((start.x == 2) && (start.y == 2)){
            return new Point(UNDEFINED,UNDEFINED);
        }

        start.x++;
        if (start.x == 3) {
        	start.x = 0;
        	start.y++;
        }
        return start;

        //return new Point(UNDEFINED,UNDEFINED);
    }

    private final static int UNDEFINED = -1;
    public static Vector<PlayingField> Queue = new Vector<PlayingField>();
    public static Vector<PlayingField> ResultQueue = new Vector<PlayingField>();
}

    PlayingField

    import java.awt.Point;
import java.beans.FeatureDescriptor;
import java.util.ArrayList;
import java.util.Vector;

class PlayingField implements Cloneable{

    /**
     * Ruft den Konstruktor auf um den das Spielfel
     */
    public PlayingField(){
        this(PLAYER1);   
    }

    /**
     * Initialisiert das Spielfeld mit default Daten
     * Initialisiert den aktiven Spieler
     * @params player : aktiver Spieler
     */
    public PlayingField(int player){
        initField();
        initActivePlayer(player);   
    }
    /**
     * Liefert den Wert eines Feldes zurueck
     @params x : x Koordinate des Feldes
     @params y : y Koordinate des Feldes
     @return Wert an der Stelle x, y
     */
    public int getFieldValue(int x, int y){
        return field[x][y];
    }

    /**
     * Beschreibt den Wert eines Feldes mit der aktuellen Spielfarbe
     * @params x : x Koordinate des Feldes
     * @params y : y Koordinate des Feldes
     * @return true bei Erfolg , false bei einem Fehler
     */
    public boolean setFieldValue(int x, int y){
        if (field[x][y] != DEFAULTVALUE){
            return false;
        }
        else{
            field[x][y] = activePlayer;

            // Add field to history
            History.add(new Point(x,y));

            return true;
        }
    }

    /**
     * Liefert den Gewinner des Spiels
     * @return PLAYER1 oder PLAYER2 bei einem Sieg
     * @return NOWINNER bei einem Unentschieden
     * @return NOTFINISHED wenn das Spiel noch nicht beendet ist.
     */   
    public int getWinner(){

        for (int x = 0; x < 3; x++){
            if ((getFieldValue(x,0) == getFieldValue(x,1)) && (getFieldValue(x,0) == getFieldValue(x,2)) && (getFieldValue(x,0) != DEFAULTVALUE)){
                return  getFieldValue(x,0);
            }
        }

        for (int y = 0; y < 3; y++){
            if ((getFieldValue(0,y) == getFieldValue(1,y)) && (getFieldValue(0,y) == getFieldValue(2,y)) && (getFieldValue(0,y) != DEFAULTVALUE)){
                return getFieldValue(0,y);
            }
        }

        if ((getFieldValue(0,2) == getFieldValue(1,2)) && (getFieldValue(0,2) == getFieldValue(2,2)) && (getFieldValue(0,2) != DEFAULTVALUE)){
            return getFieldValue(0,2);
        }

        if ((getFieldValue(0,0) == getFieldValue(1,1)) && (getFieldValue(0,0) == getFieldValue(2,2)) && (getFieldValue(0,0) != DEFAULTVALUE)){
            return getFieldValue(0,0);
        }

        if (History.size() == 9)
            return NOWINNER;

        return NOTFINISHED;
    }

    public PlayingField clone(){
        try{
            PlayingField newField = (PlayingField) super.clone();

            // Kopiere die Feldinhalte
            newField.field = new int[3][3];
            for (int x = 0; x < 3; x++){
                for (int y =  0; y < 3; y++){
                    newField.field[x][y] = this.getFieldValue(x, y);
                }
            }

            // Kopiere die Historie
            newField.History = new Vector<Point>();
            for (int i = 0; i < History.size(); i++){
                newField.History.add(this.History.get(i));
            }

            return newField;

        }catch(CloneNotSupportedException e){

        }
        return null;   
    }

    private void initActivePlayer(int player){
        // Init active player with player
        activePlayer = player;
    }

    /**
     * Initialisiert das Spielfeld mit default Werten
     */
    private void initField(){
        // Init Field with default values
        for (int x = 0; x < 3; x++){
            for (int y =  0; y < 3; y++){
                field[x][y] = DEFAULTVALUE;
            }
        }
    }

    // Public Constants
    public static final int DEFAULTVALUE     = 0;
    public static final int PLAYER1         = 1;
    public static final int PLAYER2         = 2;   
    public static final int NOWINNER        = 3;
    public static final int NOTFINISHED        = 4;
    public static final int FINISHED         = 5;

    // Private Variables
    private int[][] field = new int[3][3];
    private int activePlayer = DEFAULTVALUE;
    public Vector<Point> History = new Vector<Point>();

}
    0
  • F

    Danke für deine Antwort. Aber es müssen 9! sein also 362880

    0
  • D

    ne müssens nicht, denn wenn du die oberste reihe füllst fallen 6! Möglichkeiten weg, dadurch, dass schon jemand gewonnen hat, oder überseh ich da was?

    0
  • F

    Es geht doch dann nicht darum wer gewinnt, sondern alle möghlichkeiten also auch unentschieden. und dann gibt es doch so viele möglichkeiten oder nicht

    0
  • D

    Wenn du einen Stein setzt, sodass es folgendermaßen aussieht:

    111
000
000

    Dann gibt dir die getWinner() funktion 1 zurück.
    Du testest in der If-abfrage danach auf == NOTFINISHED (also 4)
    Somit kommst du in den else-Zweig, der das Spielfeld nur in die resultQueue packt und nciht in die Queue. Dadurch werden nciht weiter die 6 verbleibenden Felder besetzt(was auch irgendwie sinnvoll ist^^)

    Wenn du wirklich an alle möglichen Füllungen kommen willst(also das das Feld auf jeden Fall gefüllt wird, musst du bei Rückgabe von NOWINNER es in die RQ packen, in allen anderen Fällen in die QUEue. Wobei NOWINNER bedeutet, alle Felder sind belegt(-> History == 9) und dieses NOWINNER muss priorität haben, d.h. in getWinner() muss am anfang auf == 9 getestet werden.
    Wenn du diese änderungen vornimmst, kommst du auf 9!

    Achja, ich hab auch ganz am anfang das setzten von (2,2) und clonen weggelassen

    0
  • S

    Sieht nach einer Hausaufgabe aus 🙂

    0
  • ?

    Ließe sich das nicht mit Backtracking lösen?

    0
  • F

    Hallo. Also es ist keine Hasuaufgabe. Denn ich versuche gerade mich in Java einzuarbeiten.
    Naja das Problem ist das es ich ja alle möglichen Endzustände haben will. Also ntürlich nur die , dei auch logisch sind. Wenn ein Spielfeld bereits den Zustand Fertig hat, braucht man natürlich nicht weiter zu versuchen irgendwelche Felder zu beschreiben. Ich dachte immer, dass das dem Backtracking schon ziemlich nahe kommt.

    0
  • D

    1. die 9! möglichkeiten(also alle vollständigen belegungsreihenfolgen) kriegst du nur, wenn du nach einem sieg weitermachst(so wie in meinem letzten Code). Wenn du das nicht weillst, mach meine änderungen mit der getWinnerabfrage rückgängig(dann sind es aber bedeutend weniger(nach 7 Zügen ist es auf jedenfall zu ende, da du nur einen spieler hast im Moment).

    2. Für Backtracking(bin mir nicht ganz sicher), müsstest du einfach immer einen stein setzten(ohne clone()). wenn du bei voll oder einem Sieger angekommen bist, den letztenSchritt rückgängigmachen(z.B. über die History) und den Stein eins weiter setzten:

    110
101
000

    dann setzten

    110
101
100

    dann rückgängig weil fertig(vorher natürlich zustand + history speichern)

    110
101
000

    dann nächsten stein setzten

    110
101
010

    und wenn du den Stein nicht mehr setzten kannst(weil du außerhalb des Feldes landen würdest), noch einen Stein weiter zurückgehen.

    So jetzt ist erstmal Urlaub. Ich kann dir also nicht weiterhelfen für 10 Tage xD

    Mfg
    DerBaer

    0
  • F

    Danke schönen Urluab

    0
  • F

    Ich brauche doch noch mal Hilfe . Sitze nun schon seit 3 Tagen dran und finde einfach den Fehler nicht. Er erzeugt rund 295000 Elemente in der Result Queue. Dabei sollten es ca 5.478 ( laut wikipedia) . Aber ich weiß nicht wieso er so viele erzeugt. Zu mal wenn er alle Möglichkeiten erzeugen würde wäre das 9! und das sind aber weniger. Vielleicht hat jemand von euch eine idee.

    PlayingField :

    import java.awt.Point;
import java.util.ArrayList;

 public class PlayingField implements Cloneable, Comparable<PlayingField>{

	private Color activePlayer;
	public enum Color {NOPLAYER, PLAYER1, PLAYER2, UNDEFINED};
	public enum State {FINISHED, NOTFINISHED};
	private Color[][] field = new Color[3][3];
	private ArrayList<Point> History = new ArrayList();

	/**
	 * default constructor
	 */
	public PlayingField(){
		this(Color.PLAYER1);
	}

	/**
	 * constructor with the active player
	 * @param active player
	 */
	public PlayingField(Color activePlayer){
		for (int x = 0; x < 3; x++){
			for (int y = 0; y < 3; y++){
				field[x][y] = Color.NOPLAYER;
			}
		}

		this.activePlayer = activePlayer;
	}

	/**
	 * write the field with activePlayer
	 * @param x : x coordinate of the field
	 * @param y : y coordinate of the field
	 * @return true if successful else false
	 */
	public boolean setFieldValue(int x, int y){
		if ((x > 2) | (x < 0) | (y > 2) | (y < 0)){
			return false;
		}

		if (field[x][y] == Color.NOPLAYER){
			field[x][y] = activePlayer;
			changeActivePlayer();
			addFieldToHistory(x,y);
			return true;
		}

		return false;
	}

	/**
	 * write the field value
	 * @param x : x coordinate of the field
	 * @param y : y coordinate of the field
	 * @return the value of the field
	 */
	public Color getFieldValue(int x, int y){
		if ((x > 2) | (x < 0) | (y > 2) | (y < 0)){
			System.out.println("Fehler");
			return Color.NOPLAYER;
		}

		return field[x][y];
	}

	/**
	 * change the active player
	 */
	private void changeActivePlayer(){
		if (activePlayer == Color.PLAYER1){
			activePlayer = Color.PLAYER2;
		}else{
			activePlayer = Color.PLAYER1;
		}	
	}

	/**
	 * create a new entry for the history
	 */
	private void addFieldToHistory(int x, int y){
		History.add(new Point(x,y));
	}

	/**
	 * checks the row
	 * @param row : number of the row
	 * @return true if all fields have the same content
	 */
	private boolean checkRow(int row){
		return ((field[0][row] == field[1][row]) & (field[0][row] == field[2][row]) & (field[0][row] != Color.NOPLAYER));
	}

	/**
	 * checks the column
	 * @param column : number of the column
	 * @return true if all fields have the same content
	 */
	private boolean checkColumn(int column){
		return ((field[column][0] == field[column][1])  & (field[column][0] == field[column][2]) & (field[column][0] != Color.NOPLAYER));
	}

	/**
	 * checks the diagonal
	 * @param diagonal : number of the diagonal
	 * @return true if all fields have the same content
	 */
	private boolean checkDiagonal(int diagonal){
		if (diagonal == 1){
			return ((field[0][0] == field[1][1]) & (field[0][0] == field[2][2]) & (field[0][0] != Color.NOPLAYER));	
		}

		if (diagonal == 2){
			return ((field[2][0] == field[1][1]) & (field[2][0] == field[0][2]) & (field[2][0] != Color.NOPLAYER));
		}

		return false;		
	}

	/**
	 * returns the field state
	 * @return finished or not finished
	 */
	public State getFieldState(){

		if (History.size() == 9){
			return State.FINISHED;
		}

		if (History.size() == 0){
			return State.NOTFINISHED;
		}

		Point lastField = History.get(History.size() - 1);

		if ((lastField.x == 0) && (lastField.y == 0)){
			if (checkRow(0) | checkColumn(0) | checkDiagonal(1)){
				return State.FINISHED;
			}			
			return State.NOTFINISHED;
		}

		if ((lastField.x == 1) && (lastField.y == 0)){
			if (checkRow(0) | checkColumn(1)){
				return State.FINISHED;
			}			
			return State.NOTFINISHED;
		}

		if ((lastField.x == 2) && (lastField.y == 0)){
			if (checkRow(0) | checkColumn(2) | checkDiagonal(2)){
				return State.FINISHED;
			}			
			return State.NOTFINISHED;
		}

		if ((lastField.x == 0) && (lastField.y == 1)){
			if (checkRow(1) | checkColumn(0)){
				return State.FINISHED;
			}			
			return State.NOTFINISHED;
		}

		if ((lastField.x == 1) && (lastField.y == 1)){
			if (checkRow(1) | checkColumn(1) | checkDiagonal(1) | checkDiagonal(2)){
				return State.FINISHED;
			}			
			return State.NOTFINISHED;
		}

		if ((lastField.x == 2) && (lastField.y == 1)){
			if (checkRow(1) | checkColumn(2)){
				return State.FINISHED;
			}			
			return State.NOTFINISHED;
		}

		if ((lastField.x == 0) && (lastField.y == 2)){
			if (checkRow(2) | checkColumn(0) | checkDiagonal(2)){
				return State.FINISHED;
			}			
			return State.NOTFINISHED;
		}

		if ((lastField.x == 1) && (lastField.y == 2)){
			if (checkRow(2) | checkColumn(1)){
				return State.FINISHED;
			}			
			return State.NOTFINISHED;
		}

		if ((lastField.x == 2) && (lastField.y == 2)){
			if (checkRow(2) | checkColumn(2) | checkDiagonal(1)){
				return State.FINISHED;
			}			
			return State.NOTFINISHED;
		}	

		return State.NOTFINISHED;		
	}

	/**
	 * get the winner
	 * @return the color of the player
	 */
	public Color getWinner(){		
		for (int row = 0; row < 3; row++){
			if (checkRow(row) == true){
				return field[0][row];
			}
		}

		for (int column = 0; column < 3; column++){
			if (checkColumn(column) == true){
				return field[column][0];
			}
		}

		if (checkDiagonal(1) == true){
			return field[1][1];
		}

		if (checkDiagonal(2) == true){
			return field[1][1];
		}

		if (History.size() == 9){
			return Color.NOPLAYER;
		}

		return Color.UNDEFINED;
	}

	/**
	 * create a copy of the playingfield
	 */
	public Object clone(){
		try{
			PlayingField temp = (PlayingField) super.clone();
			temp.activePlayer = this.activePlayer;
			temp.field = new Color[3][3];
			temp.History = new ArrayList();

			for (int x = 0; x < 3; x++){
				for (int y = 0; y < 3; y++){
					temp.field[x][y] = this.field[x][y];
				}
			}

			for (int i = 0; i < History.size(); i++){
				temp.History.add(this.History.get(i));
			}

			return temp;

		}catch(CloneNotSupportedException e){

		}
		return null;	
	}

	/**
	 * compares the fields
	 * @return 0 equal, 1 field is behind the curretn , -1 field is bevore the current
	 */
	public int compareTo(PlayingField field){

		if (this.History.size() < field.History.size()){
			return -1;
		}

		if (this.History.size() == field.History.size()){

			if (this.getWinner() == field.getWinner()){
				return 0;
			}

			if (this.getWinner() == Color.PLAYER1 ) {
				return -1;
			}

			if ((this.getWinner() == Color.PLAYER2 ) && (field.getWinner() == Color.PLAYER1)){
				return 1;
			}

			if ((this.getWinner() == Color.PLAYER2 ) && (field.getWinner() == Color.NOPLAYER)){
				return -1;
			}

			if (this.getWinner() == Color.NOPLAYER ){
				return -1;
			}			
		}

		if (this.History.size() > field.History.size()){
			return 1;
		}

		return 0;
	}

	/**
	 * @return the size of the History
	 */
	public int getHistorySize(){
		return History.size();
	}

	 /**
	  * 
	  */
	public Point getHistoryPoint(int round){
		return History.get(round);
	}

	public void PrintPlayingField(){
		System.out.println("* * *");
		for (int i = 0 ; i < 3; i++){
			System.out.println(getFieldValue(0, i)+ " " + getFieldValue(1, i) + " " + getFieldValue(2, i));
		}
	}

 }

    ComputerPlayer :

    import java.util.ArrayList;
import java.awt.Point;

 public class ComputerPlayer extends Player{

	private ArrayList<PlayingField> Queue = new ArrayList();
	private ArrayList<PlayingField> ResultQueue = new ArrayList();

	/**
	 * create a new player
	 * @param name : name of the player
	 * @param color : color of the player
	 */
	public ComputerPlayer(String name, PlayingField.Color color){
		super(name, color);
	}

	public Point getNextMove(PlayingField field){
		Queue.clear();
		ResultQueue.clear();

		if (field.getFieldState() != PlayingField.State.FINISHED){

			Queue.add(field);
			while (Queue.size() > 0){
				ExpandField(Queue.get(0));
				Queue.remove(0);	
				System.out.println(Queue.size() + " "  +ResultQueue.size());
			}		

			return  getBestMove(field.getHistorySize());
		}

		return new Point(-1,-1);
	}

	/**
	 * checks whether it is possible to win.
	 * @return Point 
	 */
	private Point getBestMove(int round){
		PlayingField temp = null;
		for (int i = 0; i < ResultQueue.size(); i++){			
			if (temp == null){
				temp = ResultQueue.get(i);
			}else{			
				if (ResultQueue.get(i).getHistorySize() < temp.getHistorySize()){
					temp = ResultQueue.get(i);
				}else{
					if (ResultQueue.get(i).getHistorySize() == temp.getHistorySize()){
						if (ResultQueue.get(i).getWinner() == getColor()){
							temp = ResultQueue.get(i);
						}
					}
				}
			}			
		}
		return temp.getHistoryPoint(round + 1);	
	}

	/**
	 * expands the field and save the results in a queue
	 */
	private void ExpandField(PlayingField field){
		Point nextField = new Point(-1,-1);
		if (field.getFieldState() != PlayingField.State.FINISHED){
	        do{
	            nextField = getNextField(nextField);
	            if (nextField.x != -1){      
	            	PlayingField newField = (PlayingField)field.clone();
	            	if (newField.setFieldValue(nextField.x, nextField.y) == true){
	            		if (newField.getFieldState() == PlayingField.State.NOTFINISHED){
	            			Queue.add(newField);	
	            		}else{
	            			ResultQueue.add(newField);  	
	            		}
	            	}            
	            }           
	        } while (nextField.x != -1);
		}
	}

	/**
	 * get the next possible field for this field
	 * @param start : the last field is the new startfield
	 * @return next free field.
	 */
	private Point getNextField(Point start){

        if ((start.x == -1) && (start.y == -1)){
            return new Point(0,0);
        }

        if ((start.x == 2) && (start.y == 2)){
            return new Point(-1,-1);
        }

        start.x++;
        if (start.x == 3) {
            start.x = 0;
            start.y++;
        }
        return start;        
    } 
 }

    Vielen Dnak

    0
Anmelden zum Antworten