import java.awt.*; import java.util.*; import java.io.*; /* * full contact info: * Sieuwert van Otterloo * Rijnlaan 33bis * 3522BB Utrecht * homepage www.bluering.nl or go.to/sieuwert * phone +31615524227 * coauthor Ernst van Rheenen */ /** * reversi.java is an applet for playing the reversi othello board game against the computer. * Designed by * bluering software development . * You can send questions about this source to * sieuwert@bluering.nl * this applet can be freely used for whatever you want if you first ask permission from * the author. *

project overview

* This applet consists of several classes.We have put all the classes in one file * for easy downloading. To get the right * javadoc documentation, we had to make all classes and many methods public. You * might want to put each class in a separate file with the filename equal to the class * name. You can also make all classes except reversi non-public (just remove the word public) * to avoid errors. The drawback is that you will not see those classes in the documentation. *

the javadoc files contain much of the comment, but not all of it. Check the sourcecode * for the last details. The list of all classes is: *

*
reversi
the toplevel applet class. It contains and handles the buttons.
*
newgamewindow
the window that allows you to set up a new game. It appears when * you press new game
*
boardview
the class that paints the pieces. It also handles the mouse clicks.
*
board
The class containing the state of the board. This class knows the rules * of the game. Designers say it contains the game logic. It is in some way the most pure, and basic * class, where all others rely on.
*
player
the functions to calculate what move to do. This class contains * the minimax algorithm with the alpha-beta heuristic. With these techniques a search is * done to find the best position it can reach. The other classes are needed for estimating the * winning value of positions.
*
weightvector
This class contains the adjustable parameters that are needed for * determining the values of positions.
*
genetictrain
This class contains the genetic algorithm that can search the best * weight vector. If you want to search a good weight vector, you must run this class, and * in a few minutes it will select good weight vectors by letting them play against each other.
*
file
This is just a utility class for reading and writing files in an easy way.
*
*

*/ public class reversi extends java.applet.Applet{ /** * the interface components in this applet. slabel means status label. */ Label slabel=new Label("please do a move"); board b=new board(); boardview bview=new boardview(b,this); Button newgame=new Button("new game"), undo=new Button("undo move"); /** * constructor for running this applet as an application */ public reversi(){} /** * the init method is called when the applet is loaded by the browser. */ public void init(){ setBackground(Color.white);//you can set the background color of the applet in this line //resize(bview.SX+30,bview.SY+100); //this line not needed in applets, they cannot resize Panel buttonpanel=new Panel();//panel to keep buttons together buttonpanel.setLayout(new GridLayout(1,3));//add three buttons beside each other buttonpanel.add(newgame); buttonpanel.add(undo); Panel superpanel=new Panel(); superpanel.setLayout(new GridLayout(3,1)); superpanel.add(slabel); superpanel.add(buttonpanel); setLayout(new BorderLayout()); add("North",bview); add("South",superpanel); } /**the start method of the applet. It is called any time the window re-appears on the * screen. All we do here is start the animation. */ public void start() {bview.start();} /** * here we stop the animation */ public void stop() {bview.stop();} /** * the action method is called when a button is pressed. It first checks whether * bview might be busy. In that case, it does nothing. Else it undoes a move or * launches a new game window. * @return true to indicate success */ public boolean action(Event ev, Object O){ if(bview.wait)return true; if(ev.target==newgame) new newgamewindow(this); else if(ev.target==undo) undo(); return true; } /** * this method is called by newgamewindow. */ public void newgame(){ b.clear();//b.clear() restores the opening position on the board. bview.repaint();//this updates the screen } /** * this method undoes a move, if possible. */ public void undo(){ if(b.moves!=0) bview.undomove(); } /** * sets a given text in the message label. * @param s the message to display. */ public void message(String s){ slabel.setText(s);//set a message in the status label. } /** * this method is quick & dirty trick for running this applet as * an application. It is not used when a browser runs this class * as an applet. */ public static void main(String[] ps) {Frame f=new Frame("reversi"); reversi r=new reversi(); f.resize(500,500); f.add("Center",r); r.init(); r.start(); f.show(); } } /** * this is a window for popping up to create a new game. the user * can set what kind of game he wants, and then press cancel or start. */ class newgamewindow extends Frame{ reversi r; Choice[] cm={new Choice(),new Choice()}; Button start=new Button("start"); Button cancel=new Button("cancel"); /** * create a new newgamewindow. It shown immediately. You can use this * dialog only once. * @param ir the applet that wants a new game. */ public newgamewindow(reversi ir){ super("new game"); r=ir; r.bview.wait=true; setLayout(new GridLayout(2,3)); cm[0].add("human"); cm[0].add("computer"); cm[1].add("computer"); cm[1].add("human"); add(cm[0]); add(new Label(" versus ")); add(cm[1]); add(start); add(cancel); resize(250,100); setLocation(100,100); show(); } /** * this method is called any time a button is pressed or an option selected. */ public boolean action(Event ev, Object o){ if(ev.target==start){ r.newgame(); r.bview.setplayers( cm[0].getSelectedIndex()==1, cm[1].getSelectedIndex()==0); r.bview.wait=false; dispose(); } else if(ev.target==cancel){ r.bview.wait=false; dispose(); } return true; } } /** * a boardview is a canvas (a rectangle that can be displayed on the screen and painted on) * that can display a board. It can be used in two ways *

    *
  1. by an applet. In this case the boardview listens to the mouse, * and lets the players do moves. It also starts an animation for fading in any * changes. *
  2. By genetictrain. Animation is no longer needed, and it does not listen to the mouse. *
*/ class boardview extends Canvas implements Runnable { board b;//the board that is viewed int fieldsize=32;//size in pixels of a field. int SX,SY;//the total size in pixels of this canvas reversi top;//the applet that uses this boardview boolean wait=false;//if wait==true the mouse will be ignored player[] players={null,null}; boolean[] computer={false,true}; //wether the computer plays that player. int[] oldboard; //a copy of the A table of the board. String statusbartext="";//the text under the applet Color[] r2g={Color.red, new Color(213,43,0), new Color(171,85,0), new Color(128,128,0), new Color(85,171,0), new Color(43,213,0), Color.green};//the colors for the morph int framenumber;//how far we are in morphing int frames=r2g.length;//the total number of frames Graphics g; Frame superframe;//only in non-applet mode /** * constructor for applet mode */ public boardview(board ib,reversi ir){ top=ir; b=ib; myresize(b.X,b.Y); players[0]=new player(b,0,this); players[1]=new player(b,1,this); statusbartext=b.statusmessage(); } /** * constructor in non-applet mode */ public boardview(board ib){ b=ib; wait=true; myresize(b.X,b.Y); display(); } /** * creates a frame that shows this boardview. Used in nonapplet-mode. */ public void display(){ superframe=new Frame("reversi"); superframe.resize(SX+20,SY+20); superframe.add("Center",this); superframe.show(); } /** * this method is called if the user clicked the mouse. * @param evt an object that contains details on the click. * @param x the horizontal position of the cursor * @param y the vertical position * @return true to indicate success */ public boolean mouseDown(Event evt,int x,int y){ if(x>=SX||y>=SY||wait) return true; clicked(b.co(x/fieldsize,y/fieldsize)); return true; } /** * do the given move on the board. * @param m the move to be done. */ public void domove(int m){ highlightoff();//stops the morph b.domove(m);//do the move statusbartext=b.statusmessage();//set the message highlighton();//starts the morph } /** * undo the last move on the board. */ public void undomove(){ highlightoff(); b.undomove(); statusbartext=b.statusmessage(); highlighton(); } void clicked(int c){//called if user clicked field c if(!computer[b.getplayer()]){ if(b.posmoves==0) domove(-1); else if(b.canmove(c)) domove(c); } if(computer[b.getplayer()]) computermove(); } void computermove(){ message("computer is thinking..."); wait=true; players[b.getplayer()].ask("Please do your move."); /*the computer player will start calculating, and call answer with its answer.*/ } /** * you can indicate here whether computer players must be used. * @param a true if a computer player must be used for the first * player. False if the user operates this player. * @param b same for second player. */ public void setplayers(boolean a,boolean b){ computer[0]=a; computer[1]=b; } /*resize this object.*/ void myresize(int x,int y){ SX=x*fieldsize; SY=y*fieldsize; resize(SX,SY+20);//the 20 is room for the message under the screen. } boolean painting=false; /** * this method is called by the operating system if the frame must be redrawn, and by * the rest of the program if something changed on the board. It is synchronized * because genetictrain calls this method very often, and we do not want these paints * to happen in parallel. */ public void paint(Graphics newg){ synchronized(this){ if(painting) return; painting=true; } g=newg; for(int j=0;jg, 2 g->r*/ Color back[]={new Color(128,128,128),new Color(100,100,100)}; Color c1=new Color(255,0,0); Color c2=new Color(0,255,0); /** * paint one field */ void paintfield(int i,int j){ paintback(i,j); paintnormalstone(i,j); } /** * is called every 150 milliseconds. It must fade the colors of the stones that * recently changed. */ void fade(){ if(framenumber==-1) return; if(framenumber>=frames){ repaint(); framenumber=-1; return; } for(int j=0;j * because A is onedimensional, you just need one integer to indicate a field. * So instead of an object move all methods dealing with moves just use int's * (note the huge speed improvement). */ public int[] A; static int[] all;//all indices of visible fields. static int X=8,Y=8;/*the size of the visible board. You can play on larger boards by changing these values. Note that the computer AI will be confused if you do so. Try to keep X==Y (or modify the kinds code) and recompile all classes after you did, and retrain the player.*/ static int N=X*Y;//the number of visible fields. static int BASE=X+2;/*the number used in converting 1dimensional and twodimensional coordinates*/ //the values A can have. public static int OUT=88,P1=0,P2=1,FREE=3; /*the information needed to undo a move.*/ //the moves already done. int[] move=new int[128]; //the number of stones flipped in that move. int[] undoflips=new int[128]; //the positions of the stones flipped in that move. int[][] undoflip=new int[128][24]; int moves; //number of moves done. int[] can;//the number of flips if you move here, int posmoves;//the number of moves possible. if it is zero the current player must pass. int thisp;//the player that is currently moving. valid values are P1 and P2. int[] posmove=new int[N];/*the moves that are possible.*/ int[] points={0,0};//the points for each player. int free;//the number of free fields. int status; /*values:*/final static int RUNNING=1,FINISHED=2; /*these fields are needed by the computer AI:*/ static int[] kind;//the 'kind' of each field static int kinds;//the total number of different kinds. static int evalvectorlength;//the length of an evaluation vector. static{/*preparations for this class*/ all=new int[N]; int cur=0; for(int j=0;j1){ set(co(3,3),P1); set(co(3,4),P1); set(co(4,3),P2); set(co(4,4),P2); }else{ set(co(3,3),P2); set(co(3,4),P1); set(co(4,3),P1); set(co(4,4),P2); } setcan(); status=RUNNING; } /*sets the can array with the right values (and) status, free, etc... call this method after each change.*/ void setcan(){ points[P1]=points[P2]=posmoves=0; free=0; thisp=getplayer(); for(int i=0;i0) { posmove[posmoves++]=all[i]; } } if(finished()) status=FINISHED; else status=RUNNING; } /** * do the given move on this board. */ public void domove(int c){ /*do a move on this board.*/ undoflips[moves]=0; if(status==FINISHED) return; if(c!=-1) {int otherp=opponent(thisp); int i,dir,d; A[c]=thisp; for(i=0;i<8;i++){ dir=around[i]; if(count(otherp,c,dir)>0) for(d=dir+c;A[d]==otherp;d+=dir){ A[d]=thisp; undoflip[moves][undoflips[moves]++]=d; } } } move[moves++]=c; setcan(); } //all directions you can flips stones in. Given as the difference in //1dimensional field numbers. int[] around={1,-1,BASE,-BASE,BASE+1,BASE-1,-BASE+1,-BASE-1}; /** * calculate the number of stones that would flip if you put * a stone at the given position. */ int flips(int c){ if(A[c]!=FREE) return 0; int ret=0; int otherp=opponent(thisp); for(int i=0;i<8;i++) ret+=count(otherp,c,around[i]); return ret; } /** * count the flips that would happen if you put a * stone at position c and looking in the direction dir. */ int count(int otherp,int c,int dir){ int ret=0; if(A[dir+c]!=otherp) return 0; for(c=dir+c;A[c]==otherp;c+=dir) ret++; if(A[c]==thisp) return ret; return 0; } /** * returns whether the current player is allowed to place a stone at c. */ public boolean canmove(int c) {return can[c]>0;} /** * returns true iff the game is finished. */ public boolean finished() {return free==0||(posmoves==0&&move[moves-1]==-1);} /** * returns true if player 1 won the game. */ public boolean P1wins() {return points[0]>points[1];} /** * returns true if player 2 won the game. */ public boolean P2wins() {return points[0] * 0 1 3 6 6 3 1 0 * 1 2 4 7 7 4 2 1 * 3 4 5 8 8 5 4 3 * 6 7 8 9 9 8 7 6 * 6 7 8 9 9 8 7 6 * 3 4 5 8 8 5 4 3 * 1 2 4 7 7 4 2 1 * 0 1 3 6 6 3 1 0 * But you should not care about how this table looks: What is important * is that we value counters regarding their position, but using symmetries to * limit the number of situations. * the 11th number (that is out[10] or out[kinds]) * return how many counters you are ahead (negative if behind) * the twelth number return the number of moves you can do * the last number tells you the number of counters you can flip in total. *

* If you add a certain feature that you think is important for * winning chances, do it here and change evalvectorlength. The * genetictrain and weightvectorclasses will automatically adjust if you recompile them. * you must retrain before you use the applet, beacuse the standard weigth vector in the * player class will then be too short. * @param out an optional array you want the result in (reusing memory improves the speed) * You can make it null if you do not have such array. * @return returns an evalvector. It will be out if that was not null. */ public int[] getevalvector(int[] out){ if(out==null) out=new int[evalvectorlength]; for(int i=0;i=0;undoflips[moves]--) A[undoflip[moves][undoflips[moves]]]=opp; setcan(); } /** *returns a line of text describing the situation. */ public String statusmessage(){ if(finished()){ if(P1wins()) return "RED wins with "+points[P1]+" against "+points[P2]; if(P2wins()) return "GREEN wins with "+points[P2]+" against "+points[P1]; return "The game ended in DRAW"; } if(thisp==P1) return "RED to move:"+points[P1]+" (green: "+points[P2]+")"; return "GREEN to move:"+points[P2]+" (red: "+points[P1]+")"; } } /** * this class is a computer player, that calculates what move to do * in a given situation. */ class player implements Runnable{ /*general variables*/ board realb,b; int side; int maxlevel; /*The Artificial intelligence used here is not very complictated I use a alphabeta algorithm to search a few moves deep. Then I do a simple evaluation with a number of adjustable parameters. To find good values for these parameters I used a genetic algorithm. This genetic algorithm is not used while your playing: to slow. */ /*evaluation variables*/ /** * The string W is the evaluation string used to evaluate situations. It was * calculate with the genetictrain class, and then inserted in this sourcecode. */ public String W="8 0 -7 2 -8 2 0 -2 1 -6 2 3 1 -2 1 1 -2 0 -1 0 1 -2 -1 4 3 5 53 best"; int[] weight=new weightvector(W).a; int offset; /*if you used genetictrain to calculate a new weightvector, change the line String W to hold a line of the new output file. typically, pick the first or last line. */ /*for use in a parallel thread (applet mode)*/ boardview bv; long time; /** * determines how far the computer looks ahead, higher value plays * better, but takes more time. I think even values are better, because * that gives the opponent the last move, but that is personal.*/ public void setstrength(int l){ if(l>6) l=6; if(l<1) l=1; maxlevel=l; } /** * set the weight vector this player should use. */ public void setweight(int[] w) {weight=w;} /** * create a player. * @param ib the board that is used. * @param iside the side the player takes: board.P1 or board.P2 */ public player(board ib,int iside) {this(ib,iside,null);} /** * create a player for applet mode: the player calculates in a separate thread, * and wait 4 seconds before answering. * @param ib the board that is used. * @param iside the side the player takes: board.P1 or board.P2 * @param ibv the boardview it must answer to. */ public player(board ib,int iside,boardview ibv){ realb=ib; side=iside; bv=ibv; setstrength(4); } /** * the method you can call if you want this player to think of a move in a * separate thread. This function returns immediately, so the caller can do something * different. The answers will be given after 4 seconds or longer to the * boardview by the method answer. * @param s a string that is not used. It can be used for comment by a caller. Do * not take it too seriously: it is an inside joke to include comment in extra parameters. */ public void ask(String s){ new Thread(this).start(); } /*for timing*/ void timestart() {time=System.currentTimeMillis();} int gettime() {return (int)(System.currentTimeMillis()-time);} /** * the method that will run in a separate thread. Do not call this function yourself, * but use ask. */ public void run(){ timestart(); int move=bestmove(); while(gettime()<4000) {try{Thread.sleep(400);}catch(Exception e){}} bv.answer("Well, this is my move:",move); } /** * this functions returns the move that this player thinks is best. Use this function * if you just want the best move, no extra threads and no delays. * @return a move */ public int bestmove(){ b=realb.copy(); if(b.posmoves==0) return -1; setoffset(); int s,best=-1,alpha=-100000; int k=b.posmoves; for(int i=0;ialpha) {alpha=s; best=i; } } return b.posmove[best]; } /*returns how good the current situation looks.*/ int prognosis(int alpha, int beta, int level) { if(level>=maxlevel||b.posmoves==0) return simplescore(); int s; /*try all moves and return the estimate we get when doing the best move*/ for(int i=0;ibeta) return s; if(s>alpha) alpha=s; } return alpha; } void setoffset(){ /*determines which part of the eval vector,the first or the last, to use.*/ if(b.getcoverage() * A genetic algorithm is a method for solving an optimisation proble. Our * problem is to find the best weight vector. The methods works much like * biological evolution: random weight vectors are calculated, and in each round they play against a randomly selected opponent and the winners survive. * The winners are then copied (with small changes), or two * winners are mixed (called cross-over) and a new round starts: they are again tested * against each other... until you say it is enough. The main advantage of a genetic algorithm * is that it works whithout assuming anything about the problem. It just let two * 'individuals' against each other, does not care what they do exactly, but only needs * to know the winner.

* The exact description of a round is this: there is a fixed population size * (the number of weightvectors). They are randomly ordered, and the odd even numbers * play against the next odd number. The winner is stored in the even position, the odd * position is empty. Now per group of four a random decision is made: if they mutate, * the odd positions are filled with mutated copies of the winners. If crossover is chosen, * the winners are crossed over, producing two children that are random mixtures of the * parents. Remember that individuals are just lists of numbers. For example:

* parent1:-3 -5  2  6 0
* parent2 -7  0 -4  1 2
* could give:
* child1: -3  0 -4  6 2
* child2: -7 -5  2  1 0 
* In the literature this is called uniform crossover. There are other kinds of crossover. * the last position (which is odd) is filled with the average of all other individuals. */ class genetictrain { int popsize; weightvector[] pop; board b=new board(); boardview bv; player[] P={new player(b,b.P1),new player(b,b.P2)}; boolean onscreen=true; /** * @param p the population size for the genetic algorithm. */ public genetictrain(int p){ setpopsize(p); for(int i=0;i
  • first line: the population size. *
  • one line per weightvector in the population * each line has the weights on it, and can end with a comment. * @param filename the file to open. */ public void read(String filename){ /*read a file back in*/ file f=new file(); f.readopen(filename); setpopsize(f.num(f.read())); for(int i=0;i=0;i--){ System.out.println(""+i); run(); }}catch(Exception e){e.printStackTrace();} } /*does one round of the algroithm.*/ void run(){ int crossoverchance=25;//percentage /*raise this parameter if you think crossover is usefull. set to zero if you only want mutation to happen*/ randomorder(); for(int i=0;i+11;i--) swap(i,rand(i+1)); } /** * swap to elements of the population. */ void swap(int a,int b){ weightvector dummy=pop[a]; pop[a]=pop[b]; pop[b]=dummy; } /** * this method lets two weightvectors play against each other, and * returns the winner (or w1 if in draw) */ weightvector winner(weightvector w1,weightvector w2){ P[0].setweight(w1.a); P[1].setweight(w2.a); b.clear(); int onturn=0; while(!b.finished()){ b.domove(P[onturn].bestmove()); if(onscreen) bv.repaint(); onturn=1-onturn; } if(b.P1wins()) return w1; return w2; } /*return a random integer between 0 and r (r not included)*/ int rand(int r) {return (int)(Math.random()*r);} /*returns true with the given chance*/ boolean maybe(int percent) {return rand(100)max) return max; return x; } } /**This is a class for reading and writing textfiles. * basic use :
      *
    • make a file object *
    • do readopen *
    • do some read *
    • do close *
    • or: *
    • make an object *
    • do writeopen *
    • do some writing *
    • do close *
    */ class file{ BufferedReader in; PrintWriter out; boolean OK; /** * open a file for reading. */ public void readopen(String f1) {readopen(new File(f1));} /** * open a file for reading. */ public void readopen(File f1){ try{ in=new BufferedReader(new FileReader(f1)); OK=true; }catch(Exception e) {e.printStackTrace();OK=false;} } /** * read one line of the input file. */ public String read(){ if(!OK) return null; try{ return in.readLine().trim(); }catch(Exception e) {e.printStackTrace();} return null; } /** * close the file opened for reading. */ public void readclose(){ try{ if(in!=null)in.close(); }catch(Exception e) {e.printStackTrace();} } /** * open a file for writing. Note that it is allowed to have both a file to * read and a file to write with the same file object. */ public void writeopen(String f1) {writeopen(new File(f1));} /** * open a file for writing. Note that it is allowed to have both a file to * read and a file to write with the same file object. */ public void writeopen(File f1){ try{ out=new PrintWriter(new FileOutputStream(f1)); OK=true; }catch(Exception e) {e.printStackTrace();OK=false;} } /** * Write out the given string as a separate line. */ public void write(String s) {if(OK)out.println(s);} /** * close the writefile */ void writeclose() {if(out!=null)out.close();} /** * close both the file opened for reading and the one for writing (if any) */ public void close() {readclose();writeclose();} /** * converts a String to an int. */ public static int num(String s){ return Integer.parseInt(s.trim()); } /** * converts a String to a double. */ public static double dnum(String s){ return new Double(s).doubleValue(); } }