Author: michael
Date: Mon May 7 02:30:29 2007
New Revision: 12
Log:
This is a little java applet i wrote 8 years ago
Added:
trunk/TicTacToe/
trunk/TicTacToe/IllegalMoveException.java
trunk/TicTacToe/README
trunk/TicTacToe/State.java
trunk/TicTacToe/TicTacToe.java
trunk/TicTacToe/empty.jpg (contents, props changed)
trunk/TicTacToe/emptyL.jpg (contents, props changed)
trunk/TicTacToe/o.jpg (contents, props changed)
trunk/TicTacToe/oL.jpg (contents, props changed)
trunk/TicTacToe/ttt.htm
trunk/TicTacToe/x.jpg (contents, props changed)
trunk/TicTacToe/xL.jpg (contents, props changed)
Added: trunk/TicTacToe/IllegalMoveException.java
==============================================================================
--- (empty file)
+++ trunk/TicTacToe/IllegalMoveException.java Mon May 7 02:30:29 2007
@@ -0,0 +1,3 @@
+class IllegalMoveException extends Exception
+ {
+ }
Added: trunk/TicTacToe/README
==============================================================================
--- (empty file)
+++ trunk/TicTacToe/README Mon May 7 02:30:29 2007
@@ -0,0 +1,12 @@
+About:
+This is a little java applet i wrote 8 years ago (1999)
+pictures where generated with povray, sadly ive not found their .pov files
+
+License:
+GPL
+
+Compilation:
+javac *.java
+
+Execution
+open ttt.htm in your favorite browser
\ No newline at end of file
Added: trunk/TicTacToe/State.java
==============================================================================
--- (empty file)
+++ trunk/TicTacToe/State.java Mon May 7 02:30:29 2007
@@ -0,0 +1,354 @@
+//TicTacToe 1.0 Copyright (c) 1999 Michael Niedermayer
+
+/**
+ * @author Michael Niedermayer
+ */
+class State
+ {
+ private static final int [] POW3= {1, 3, 9, 27, 81, 243, 729, 2187, 6561};
+ private static final boolean DO_RANDOMIZE= true;
+ private static final double EPSILON= 1E-10;
+ private boolean [][] linePosArray= new boolean[3][];
+ protected static final int COMP= TicTacToe.COMP;
+ protected static final int USER= TicTacToe.USER;
+ protected static final int STATES= 19683;
+ protected int current=0;
+ protected int firstPlayer=-1;
+
+ private class Score
+ {
+ int nTies[]= {0,0};
+ int [][] nWins= {{0,0}, {0,0}};
+
+ Score(int iState)
+ {
+
+ if( !isLegal(iState) )
+ {
+ return;
+ }
+
+ int w= getWinner(iState);
+ if( w != -1 )
+ {
+ nWins[w^1][w]= 1;
+ return;
+ }
+ if( isFull(iState) )
+ {
+ nTies[0]= 1;
+ nTies[1]= 1;
+ return;
+ }
+
+ for(int x=0; x<3; x++)
+ {
+ for(int y=0; y<3; y++)
+ {
+ if( get(x, y, iState) != -1) continue;
+ try
+ {
+ int [] m= new int[2];
+ m[0]= set(x, y, iState, 0);
+ m[1]= set(x, y, iState, 1);
+// System.out.print( m[0] + " " + m[1] + " ");
+ if(score[ m[0] ]==null) score[ m[0] ]= new Score( m[0] );
+ if(score[ m[1] ]==null) score[ m[1] ]= new Score( m[1] );
+// System.out.print( "n ");
+
+ nTies[USER] += score[ m[USER] ].nTies[COMP];
+ nWins[USER][0]+= score[ m[USER] ].nWins[COMP][0];
+ nWins[USER][1]+= score[ m[USER] ].nWins[COMP][1];
+ }
+ catch( IllegalMoveException e )
+ {
+ throw new IllegalStateException();
+ }
+ }
+ }
+
+// System.out.print("is"+iState+ " ");
+ int bestMove= findBestMove(iState);
+ int m;
+ try
+ {
+ m= set(bestMove%3, bestMove/3, iState, COMP);
+ }
+ catch(IllegalMoveException e)
+ {
+ throw new IllegalStateException();
+ }
+
+
+ nTies[COMP] += score[ m ].nTies[USER];
+ nWins[COMP][0]+= score[ m ].nWins[USER][0];
+ nWins[COMP][1]+= score[ m ].nWins[USER][1];
+
+
+ }
+
+ }
+ private Score [] score= new Score[STATES];
+
+ State(int firstPlayer)
+ {
+ for(int i=0; i<3; i++)
+ {
+ linePosArray[i]= new boolean[3];
+ }
+
+ setFirstPlayer(firstPlayer);
+ score[0]= new Score(0);
+ }
+
+ private boolean isFull(int iState)
+ {
+ boolean b=true;
+
+ for(int x=0; x<3; x++)
+ {
+ for(int y=0; y<3; y++)
+ {
+ if( get(x, y, iState)==-1 ) b= false;
+ }
+ }
+
+ return b;
+ }
+
+ /**
+ * returns the player+1, who has all three fields on the line (x, y) - (x + dx*2, y + dy*2)
+ * and sets the <code>linePosArray</code> to the line, or returns 0.
+ */
+ private int getWinnerAt(int x, int y, int dx, int dy, int iState)
+ {
+ int winner=
+ ( get(x, y , iState) + 1 )
+ & ( get(x+dx , y+dy , iState) + 1 )
+ & ( get(x+dx*2, y+dy*2, iState) + 1 );
+
+ if(winner!=0 && winner!=3)
+ {
+ linePosArray[x ][y ]=
+ linePosArray[x+dx ][y+dy ]=
+ linePosArray[x+dx*2][y+dy*2]= true;
+ }
+ return winner;
+ }
+
+ /**
+ * Gets the player, who has 3 in a line and sets the <code>linePosArray</code> to it.
+ * @return The winner or -1 if no winner.
+ * @throws IllegalStateException if multiple winners
+ */
+ private int getWinner(int iState)
+ {
+ for(int x=0; x<3; x++)
+ {
+ for(int y=0; y<3; y++)
+ {
+ linePosArray[x][y]= false;
+ }
+ }
+
+ int r=
+ (
+ getWinnerAt(0, 0, 1, 0, iState)
+ | getWinnerAt(0, 1, 1, 0, iState)
+ | getWinnerAt(0, 2, 1, 0, iState)
+ | getWinnerAt(0, 0, 0, 1, iState)
+ | getWinnerAt(1, 0, 0, 1, iState)
+ | getWinnerAt(2, 0, 0, 1, iState)
+ | getWinnerAt(0, 0, 1, 1, iState)
+ | getWinnerAt(2, 0,-1, 1, iState)
+ ) - 1;
+
+ if(r==2) throw( new IllegalStateException() );
+
+ return r;
+ }
+
+ private boolean isLegal(int iState)
+ {
+ int [] n= {0,0};
+
+ for(int x=0; x<3; x++)
+ {
+ for(int y=0; y<3; y++)
+ {
+ int p=get(x, y, iState);
+ if(p != -1) n[p]++;
+ }
+ }
+
+ int diff= n[0] - n[1];
+ if( diff<-1 || diff>1 ) return false;
+ else return true;
+ }
+
+ /**
+ * Gets the player, who is on the Field (x, y), or -1 if the field is empty.
+ */
+ private int get(int x, int y, int iState)
+ {
+ if(x<0 || x>2) throw new IllegalArgumentException();
+ if(y<0 || y>2) throw new IllegalArgumentException();
+ if(iState<0 || iState>=STATES) throw new IllegalArgumentException();
+ return (iState / POW3[x+y*3] ) % 3 - 1;
+ }
+
+ /**
+ * Sets the player for the Field (x, y).
+ * @throws IllegalMoveException if the field is not empty.
+ */
+ private int set(int x, int y, int iState, int v) throws IllegalMoveException
+ {
+ v++;
+ if(x<0 || x>2) throw new IllegalArgumentException();
+ if(y<0 || y>2) throw new IllegalArgumentException();
+ if(v<1 || v>2) throw new IllegalArgumentException();
+ if(iState<0 || iState>=STATES) throw new IllegalArgumentException();
+
+ if( get(x, y, iState)!=-1 ) throw new IllegalMoveException();
+
+ int p= POW3[x+y*3];
+ return iState - (get(x, y, iState) + 1) * p + v*p;
+ }
+
+ /**
+ * Finds the Best Move for the Computer.
+ * @return x + y*3
+ * @throws IllegalArgumentException if no empty field left.
+ */
+ private int findBestMove(int iState)
+ {
+ double bestQ= Double.NEGATIVE_INFINITY;
+ int bestX=-1, bestY=-1;
+
+ for(int x=0; x<3; x++)
+ {
+ for(int y=0; y<3; y++)
+ {
+ if( get(x,y, iState)!=-1 ) continue;
+ int m=0;
+ try
+ {
+ m=set(x, y, iState, COMP);
+ }
+ catch(IllegalMoveException e)
+ {
+ throw new IllegalStateException();
+ }
+
+ double q;
+
+ if(score[m].nWins[ USER ][ USER ] > 0)
+ {
+ q= (double)( -score[m].nWins[ USER ][ USER ] )
+ / (double)( score[m].nTies[ USER ]
+ + score[m].nWins[ USER ][ COMP ] + EPSILON);
+ }
+ else
+ {
+ q= (double)(score[m].nWins[ USER ][ COMP ])
+ / (double)(score[m].nTies[ USER ] + EPSILON);
+ }
+
+ if(DO_RANDOMIZE)
+ {
+ if(q <= -0.9/EPSILON) q= -1.0/EPSILON;
+ else if(q < 0.0 ) q= -1.0;
+ else if(q < 0.9/EPSILON) q= 1.0;
+ else q= 1.0/EPSILON;
+
+ q*= 1 + Math.random();
+ }
+
+ if(q>=bestQ)
+ {
+ bestQ= q;
+ bestX= x;
+ bestY= y;
+ }
+ }
+ }
+
+ if(bestX<0) throw new IllegalArgumentException( "No empty field left" );
+ return bestX + bestY*3;
+ }
+
+ /**
+ * Gets the line on which one player has all three fields.
+ */
+ public boolean [][] getLine()
+ {
+ getWinner(current);
+ return linePosArray;
+ }
+
+ public void makeEmpty()
+ {
+ current=0;
+ }
+
+ public boolean isEnd()
+ {
+ if( !isLegal(current) ) throw new IllegalStateException();
+
+ if( isFull(current) ) return true;
+ if( getWinner(current) != -1 ) return true;
+
+ return false;
+ }
+
+ /**
+ * Gets the player, who is currently on the Field (x, y), or -1 if the field is empty.
+ */
+ public int get(int x, int y)
+ {
+ return get(x, y, current);
+ }
+
+ /**
+ * Sets the player for the Field (x, y).
+ * @throws IllegalMoveException if the field is not empty.
+ */
+ public void set(int x, int y, int v) throws IllegalMoveException
+ {
+ current= set(x, y, current, v);
+ }
+
+ public int getNTie(int nextPlayer)
+ {
+ return score[current].nTies[ nextPlayer ];
+ }
+
+ public int getNCOMPWin(int nextPlayer)
+ {
+ return score[current].nWins[ nextPlayer ][COMP];
+ }
+
+ public void makeMove()
+ {
+ int best= findBestMove(current);
+ try
+ {
+ set(best%3, best/3, COMP);
+ }
+ catch(IllegalMoveException e)
+ {
+ throw new IllegalStateException();
+ }
+/*
+ System.out.print( score[current].nTies[USER]+ " "
+ + score[current].nWins[USER][USER]+ " "
+ + score[current].nWins[USER][COMP]+ "\n");
+*/
+ }
+
+ public void setFirstPlayer(int firstPlayer)
+ {
+ this.firstPlayer= firstPlayer;
+ }
+
+ }
Added: trunk/TicTacToe/TicTacToe.java
==============================================================================
--- (empty file)
+++ trunk/TicTacToe/TicTacToe.java Mon May 7 02:30:29 2007
@@ -0,0 +1,151 @@
+//TicTacToe 1.0 Copyright (c) 1999 Michael Niedermayer
+
+import java.awt.*;
+import java.awt.event.*;
+import javax.swing.*;
+import java.net.*;
+import java.util.*;
+
+/**
+ * @author Michael Niedermayer
+ */
+public class TicTacToe extends JApplet implements ActionListener, KeyListener
+ {
+ protected static final int COMP=0;
+ protected static final int USER=1;
+ private int mouseX=-1, mouseY=-1;
+ protected JButton [][] aJButton= new JButton[3][];
+ protected ImageIcon [] icon= new ImageIcon[6];
+ protected int firstPlayer= 1;
+ protected State state= new State( firstPlayer );
+
+ private void initPicsFromState()
+ {
+ boolean [][] line= state.getLine();
+ for(int x=0; x<3; x++)
+ {
+ for(int y=0; y<3; y++)
+ {
+ int s= state.get(x, y) + 1;
+
+ aJButton[x][y].setRolloverIcon(icon[s+3]);
+// aJButton[x][y].setSelectedIcon(icon[s+3]);
+
+ if(line[x][y])
+ {
+ aJButton[x][y].setIcon(icon[s+3]);
+ }
+ else
+ {
+ aJButton[x][y].setIcon(icon[s]);
+ }
+ }
+ }
+ }
+
+ public void init()
+ {
+ try
+ {
+ icon[0]= new ImageIcon( new URL( getCodeBase(), "empty.jpg" ) );
+ icon[1]= new ImageIcon( new URL( getCodeBase(), "x.jpg" ) );
+ icon[2]= new ImageIcon( new URL( getCodeBase(), "o.jpg" ) );
+ icon[3]= new ImageIcon( new URL( getCodeBase(), "emptyL.jpg" ) );
+ icon[4]= new ImageIcon( new URL( getCodeBase(), "xL.jpg" ) );
+ icon[5]= new ImageIcon( new URL( getCodeBase(), "oL.jpg" ) );
+ }
+ catch( MalformedURLException e)
+ {
+ System.err.println("Cant load Image " + e.getMessage());
+ System.exit(1);
+ }
+
+ Container cp= getContentPane();
+
+ cp.setLayout( new GridLayout(3, 3) );
+
+ for(int x=0; x<3; x++)
+ {
+ aJButton[x]= new JButton[3];
+ }
+
+ for(int y=0; y<3; y++)
+ {
+ for(int x=0; x<3; x++)
+ {
+ JButton jb= new JButton(icon[0]);
+ aJButton[x][y]= jb;
+ jb.setBorder( BorderFactory.createRaisedBevelBorder() );
+ jb.setRolloverEnabled(true);
+ cp.add(jb);
+
+ jb.putClientProperty("xPos", new Integer(x));
+ jb.putClientProperty("yPos", new Integer(y));
+ jb.addActionListener(this);
+ jb.addKeyListener(this);
+ }
+ }
+
+ aJButton[1][1].requestFocus();
+ initPicsFromState();
+ }
+
+ public void actionPerformed(ActionEvent e)
+ {
+ JButton jButton= (JButton)e.getSource();
+
+ int x= ((Integer)jButton.getClientProperty("xPos")).intValue();
+ int y= ((Integer)jButton.getClientProperty("yPos")).intValue();
+
+ if(state.isEnd())
+ {
+ state.makeEmpty();
+
+ firstPlayer^= 1;
+ state.setFirstPlayer(firstPlayer);
+
+ if(firstPlayer==COMP)
+ state.makeMove();
+ }
+ else
+ {
+ try
+ {
+ state.set(x, y, USER);
+ }
+ catch(IllegalMoveException e2)
+ {
+ return;
+ }
+ if(!state.isEnd())
+ state.makeMove();
+ }
+
+ initPicsFromState();
+ }
+ public void keyTyped(KeyEvent e){}
+ public void keyPressed(KeyEvent e)
+ {
+ JButton jButton= (JButton)e.getSource();
+
+ int x= ((Integer)jButton.getClientProperty("xPos")).intValue();
+ int y= ((Integer)jButton.getClientProperty("yPos")).intValue();
+
+ if(e.getKeyCode() == e.VK_LEFT) x--;
+ if(e.getKeyCode() == e.VK_RIGHT) x++;
+ if(e.getKeyCode() == e.VK_DOWN) y++;
+ if(e.getKeyCode() == e.VK_UP) y--;
+
+ x+=3;
+ y+=3;
+ x%=3;
+ y%=3;
+
+ aJButton[x][y].requestFocus();
+ }
+ public void keyReleased(KeyEvent e){}
+ public String getAppletInfo()
+ {
+ return "TicTacToe 1.0 Copyright (c) 1999 Michael Niedermayer\n";
+ }
+ }
Added: trunk/TicTacToe/empty.jpg
==============================================================================
Binary file. No diff available.
Added: trunk/TicTacToe/emptyL.jpg
==============================================================================
Binary file. No diff available.
Added: trunk/TicTacToe/o.jpg
==============================================================================
Binary file. No diff available.
Added: trunk/TicTacToe/oL.jpg
==============================================================================
Binary file. No diff available.
Added: trunk/TicTacToe/ttt.htm
==============================================================================
--- (empty file)
+++ trunk/TicTacToe/ttt.htm Mon May 7 02:30:29 2007
@@ -0,0 +1,18 @@
+<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
+
+<HTML>
+
+<HEAD>
+<TITLE>TicTacToe</TITLE>
+<META NAME="GENERATOR" CONTENT="Arachnophilia 3.9">
+<META NAME="FORMATTER" CONTENT="Arachnophilia 3.9">
+</HEAD>
+
+<BODY style="text-align: center">
+
+ <APPLET code="TicTacToe.class" width=320 height=320>
+ </APPLET>
+
+</BODY>
+
+</HTML>
Added: trunk/TicTacToe/x.jpg
==============================================================================
Binary file. No diff available.
Added: trunk/TicTacToe/xL.jpg
==============================================================================
Binary file. No diff available.
