4. Frage zum Alpha Beta Algorithmus.

Frage zum Alpha Beta Algorithmus.

  • F

    Hallo
    Ich bin gerade dabei eine Klasse zu schreiben, die eine virtuelle Welt übergebn bekommt, und daraus den besten Spielzug berechnet. Dazu habe ich mir den Alpha Beta Algorithmus ausgesucht, da er am effizientesten ist. Ich habe mich an die Anweisung in Wikipedia gehalten : http://de.wikipedia.org/wiki/Alpha-Beta-Suche

    Ich habe das zweite Beispiel genommen :

    worlaction.java

    package ArtificialIntelligence;

public abstract class WorldAction {

}

    worldobject.java

    package ArtificialIntelligence;

public abstract class WorldObject implements Cloneable {

	public abstract WorldAction[] getNextAction();

	public abstract boolean executeNextAction(WorldAction nextAction);

	public abstract int getWorldValue();

	public abstract WorldObject clone();
}

    worldsearchnode

    package ArtificialIntelligence;

import Example.ExampleAction;

public class WorldSearchNode{

	private WorldSearchNodeValue nodeValue;

	// =================================================== //
	// Helper Class WolrdSearchNodeValue
	// =================================================== //
	public class WorldSearchNodeValue{
		public int nodeDepth			= 0;
		public int maxDepth				= 0;
		public int nodeValue			= 0;
		public WorldObject nodeWorld	= null;
		public WorldAction nodeAction	= null;
		public WorldSearchNode nodeChild= null;
	}

	public WorldSearchNode(WorldObject nodeWorld, WorldAction nodeAction, int nodeDepth, int maxDepth){
		this.nodeValue					= new WorldSearchNodeValue();

		// =================================================== //
		// set depth
		// =================================================== //
		this.nodeValue.nodeDepth		= nodeDepth;
		this.nodeValue.maxDepth			= maxDepth;

		// =================================================== //
		// set world and next action
		// =================================================== //
		this.nodeValue.nodeWorld		= nodeWorld;
		this.nodeValue.nodeAction		= nodeAction;

		// =================================================== //
		// execute next action
		// =================================================== //
		if (this.nodeValue.nodeAction != null){
			this.nodeValue.nodeWorld.executeNextAction(this.nodeValue.nodeAction);
		}
	}

	public WorldAction getAction(){
		System.out.println(AlphaBete(Integer.MIN_VALUE, Integer.MAX_VALUE));
		return null;
	}

	public int AlphaBete(int alpha, int beta){

		WorldAction nextAction[] 	= this.nodeValue.nodeWorld.getNextAction();
		WorldSearchNode tmpNode		= null;
/*
		if (this.nodeValue.nodeAction != null){
			if ( ((ExampleAction)this.nodeValue.nodeAction).acionName.equals("S9") == true){
				System.out.println("Bin in S9");
				for (int i = 0; i < nextAction.length; i++){
					System.out.println("Nachfolger von S9 : " + ((ExampleAction)nextAction[i]).acionName);

				}
			}
		}*/	

		if (nextAction == null){
			System.out.println(((ExampleAction)this.nodeValue.nodeAction).acionName + " " +  this.nodeValue.nodeWorld.getWorldValue());
			return this.nodeValue.nodeWorld.getWorldValue();
		}

		for (int index = 0; index < nextAction.length; index++){

			tmpNode	= new WorldSearchNode(this.nodeValue.nodeWorld.clone(), 
														  nextAction[index], 
														  this.nodeValue.nodeDepth + 1, 
														  this.nodeValue.maxDepth);	
			if (this.nodeValue.nodeDepth % 2 == 0){

				// =================================================== //
				// MAX Player
				// =================================================== //
				alpha	= Math.max(alpha, tmpNode.AlphaBete(alpha, beta));
				this.nodeValue.nodeValue	= alpha;
				if (alpha >= beta){
					if (alpha > this.nodeValue.nodeValue){
						this.nodeValue.nodeValue	= alpha;
						this.nodeValue.nodeChild	= tmpNode;
					}
					printNodeInformation();
					return alpha;
				}

			}else{

				// =================================================== //
				// MIN Player
				// =================================================== //
				beta	= Math.min(beta, tmpNode.AlphaBete(alpha, beta));
				this.nodeValue.nodeValue	= beta;
				if (alpha >= beta){
					if (beta < this.nodeValue.nodeValue){
						this.nodeValue.nodeValue	= beta;
						this.nodeValue.nodeChild	= tmpNode;
					}
					printNodeInformation();
					return beta;
				}				
			}			
		}		

		if (this.nodeValue.nodeDepth % 2 == 0){		
			if (alpha > this.nodeValue.nodeValue){
				this.nodeValue.nodeValue	= alpha;
				this.nodeValue.nodeChild	= tmpNode;
			}
			printNodeInformation();
			return alpha;
		}else{
			if (beta < this.nodeValue.nodeValue){
				this.nodeValue.nodeValue	= beta;
				this.nodeValue.nodeChild	= tmpNode;
			}

			printNodeInformation();
			return beta;			
		}
	}

	private void printNodeInformation(){
		if (this.nodeValue.nodeAction != null){
			System.out.println(((ExampleAction)this.nodeValue.nodeAction).acionName + " " + this.nodeValue.nodeValue);	
		}else{

			WorldSearchNode child	= this.nodeValue.nodeChild;
			/*
			while (child != null){
				System.out.println(((ExampleAction)child.nodeValue.nodeAction).acionName);
				child	= child.nodeValue.nodeChild;
			}*/

			System.out.println("null " + this.nodeValue.nodeValue + " " + ((ExampleAction)this.nodeValue.nodeChild.nodeValue.nodeAction).acionName);
		}

	}
}

    exampleaction.java

    package Example;

import ArtificialIntelligence.WorldAction;

public class ExampleAction extends WorldAction {

	public String acionName	= "";

	public ExampleAction(String name){
		this.acionName	= name;
	}
}

    exampleworld.java

    package Example;

import ArtificialIntelligence.WorldAction;
import ArtificialIntelligence.WorldObject;
import ArtificialIntelligence.WorldSearchNode;

public class ExampleWorld extends WorldObject implements Cloneable{

	private ExampleAction currentAction	= new ExampleAction("S1");

	public WorldObject clone(){

		ExampleWorld returnValue	= new ExampleWorld();
		returnValue.currentAction	= this.currentAction;

		return returnValue;		
	}

	@Override
	public WorldAction[] getNextAction() {

		ExampleAction returnValue[];

		if (currentAction.acionName.equals("S1")){
			returnValue	= new ExampleAction[3];
			returnValue[0]	= new ExampleAction("S2");
			returnValue[1]	= new ExampleAction("S3");
			returnValue[2]	= new ExampleAction("S4");
			return returnValue;
		}

		if (currentAction.acionName.equals("S2")){
			returnValue	= new ExampleAction[2];
			returnValue[0]	= new ExampleAction("S5");
			returnValue[1]	= new ExampleAction("S6");
			return returnValue;
		}

		if (currentAction.acionName.equals("S3")){
			returnValue	= new ExampleAction[2];
			returnValue[0]	= new ExampleAction("S7");
			returnValue[1]	= new ExampleAction("S8");
			return returnValue;
		}

		if (currentAction.acionName.equals("S4")){
			returnValue	= new ExampleAction[2];
			returnValue[0]	= new ExampleAction("S9");
			returnValue[1]	= new ExampleAction("S10");
			return returnValue;
		}

		if (currentAction.acionName.equals("S5")){
			returnValue	= new ExampleAction[3];
			returnValue[0]	= new ExampleAction("S11");
			returnValue[1]	= new ExampleAction("S12");
			returnValue[2]	= new ExampleAction("S13");
			return returnValue;
		}

		if (currentAction.acionName.equals("S6")){
			returnValue	= new ExampleAction[3];
			returnValue[0]	= new ExampleAction("S14");
			returnValue[1]	= new ExampleAction("S15");
			returnValue[2]	= new ExampleAction("S16");
			return returnValue;
		}

		if (currentAction.acionName.equals("S7")){
			returnValue	= new ExampleAction[3];
			returnValue[0]	= new ExampleAction("S17");
			returnValue[1]	= new ExampleAction("S18");
			returnValue[2]	= new ExampleAction("S19");
			return returnValue;
		}

		if (currentAction.acionName.equals("S8")){
			returnValue	= new ExampleAction[3];
			returnValue[0]	= new ExampleAction("S20");
			returnValue[1]	= new ExampleAction("S21");
			returnValue[2]	= new ExampleAction("S22");
			return returnValue;
		}

		if (currentAction.acionName.equals("S9")){
			returnValue	= new ExampleAction[3];
			returnValue[0]	= new ExampleAction("S23");
			returnValue[1]	= new ExampleAction("S24");
			returnValue[2]	= new ExampleAction("S25");
			return returnValue;
		}

		if (currentAction.acionName.equals("S10")){
			returnValue	= new ExampleAction[3];
			returnValue[0]	= new ExampleAction("S26");
			returnValue[1]	= new ExampleAction("S27");
			returnValue[2]	= new ExampleAction("S28");
			return returnValue;
		}

		return null;
	}

	@Override
	public boolean executeNextAction(WorldAction nextAction) {

	//	System.out.println(currentAction.acionName + "->" + ((ExampleAction)nextAction).acionName);

		this.currentAction	= (ExampleAction) nextAction;
		return false;
	}

	@Override
	public int getWorldValue() {

		if (currentAction.acionName.equals("S11")){
			return 10;
		}

		if (currentAction.acionName.equals("S12")){
			return -5;
		}

		if (currentAction.acionName.equals("S13")){
			return 3;
		}

		if (currentAction.acionName.equals("S14")){
			return -6;
		}

		if (currentAction.acionName.equals("S15")){
			return 12;
		}

		if (currentAction.acionName.equals("S16")){
			return 1;
		}

		if (currentAction.acionName.equals("S17")){
			return 10;
		}

		if (currentAction.acionName.equals("S18")){
			return 12;
		}

		if (currentAction.acionName.equals("S19")){
			return 3;
		}

		if (currentAction.acionName.equals("S20")){
			return 13;
		}

		if (currentAction.acionName.equals("S21")){
			return 5;
		}

		if (currentAction.acionName.equals("S22")){
			return 3;
		}

		if (currentAction.acionName.equals("S23")){
			return 3;
		}

		if (currentAction.acionName.equals("S24")){
			return 2;
		}

		if (currentAction.acionName.equals("S25")){
			return -4;
		}

		if (currentAction.acionName.equals("S26")){
			return 1;
		}

		if (currentAction.acionName.equals("S27")){
			return 2;
		}

		if (currentAction.acionName.equals("S28")){
			return 3;
		}

		return 0;
	}

	public static void main(String argv[]){
		System.out.println("Example World gestartet");
		ExampleWorld world	= new ExampleWorld();
		WorldSearchNode searchTree	= new WorldSearchNode(world, null, 0, Integer.MAX_VALUE);

		System.out.println( ( (ExampleAction)searchTree.getAction()).acionName );
		//System.out.println(searchTree.getAction());

		//System.out.println(searchTree.AlphaBeta(Integer.MIN_VALUE, Integer.MAX_VALUE));
		//System.out.println(((ExampleAction)searchTree.getAction()).acionName);
		System.out.println("Example World beendet");

	}

}

    wenn ich nun mein besipiel ausführe, bekomme ich als "Zugempfehlung" S4
    ich sollte aber s3 bekommen, so wies es in der wiki steht.

    Ich hhoffe es kann mir jeamnd bei der Fehlersuche helfen, ich finde den fehler nicht.

    Nicht wundern beim kompilieren kommt eine NullPointer Exception das ist "noch" okay.

    Vielen Dank

    0
  • ?

    Fischkopf2009 schrieb:

    Nicht wundern beim kompilieren kommt eine NullPointer Exception das ist "noch" okay.

    🙄

    Es ist NICHT ok so einen Müllberg an Code ins Forum zu packen wenn er nichtmal kompilier- oder ausführbar ist.

    0
  • M

    Alpha-Beta-Suche ist doch nur eine Tiefensuche... Wieso baust du Dir da so umständlich einen eigenen Baum auf, anstatt das einfach rekursiv zu implementieren?

    0
Anmelden zum Antworten