Flashcenhals im Programm



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



  • 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?



  • 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



  • 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



  • Sieht nach einer Hausaufgabe aus 🙂



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



  • 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.



  • 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



  • Danke schönen Urluab



  • 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


Anmelden zum Antworten