Turn Based Strategy Games

[Fred Hamilton]

Gurudas Bhandarkar wrote:@Fred

I took a look.
I will work it out as you said, alpha-beta should work the same in any game no matter its chess, connect4 or any other.
So just a query, why can't we just copy paste your code that you used for chess(of course if you permit).
Also please provide me with the suggestions so as to how can I transform this into a gomoku, or I can modify the grid and the shape into gomoku variant so that even I would learn.
and then you can correct me if I go wrong, would this be alright?

because I did not write my alphaBeta formula for chess to be interchangeable. I could have, but I didn't. Don't put too much emphasis on my claims of interoperability. The main point is that the recursion function, be it mini-max or negamax or negamax + alphabeta, should be separate from the move generation and evaluation functions.

what I'm gonna do for tic tac toe is get it working with just nega-max, and take my time with the alpha beta pruning.

[Kabir Shah]

It was just a query from my side, never tried to emphasize i apologize if I may have sounded
that way.

Coming back to themain game called gomoku,
I modified your GameBoard class

  package gomuko;

import java.io.*;
import javax.swing.*;
import java.awt.*;
import javax.imageio.*;
import java.awt.image.*;

public class GameBoard extends JPanel {

    private int width, height, ss, inset;
    private StringBuilder posn;

    public GameBoard(int width, int height) {

        this.width = width;
        this.height = height;
        ss = width / 13;
        inset = ss / 5;

        setPreferredSize(new Dimension(width, height));
        setBackground(Color.GREEN);

        posn = new StringBuilder(169);
    }

    public void reset(String posn) {
        this.posn = new StringBuilder(posn);
        repaint();
    }

    public void paintComponent(Graphics g) {

        int piece;
        int x, y, row, col;

        super.paintComponent(g);

        // draw the grid
        g.drawLine(ss, 0, ss, height);
        g.drawLine(2 * ss, 0, 2 * ss, height);
        g.drawLine(3 * ss, 0, 3 * ss, height);
        g.drawLine(4 * ss, 0, 4 * ss, height);
        g.drawLine(5 * ss, 0, 5 * ss, height);
        g.drawLine(6 * ss, 0, 6 * ss, height);
        g.drawLine(7 * ss, 0, 7 * ss, height);
        g.drawLine(8 * ss, 0, 8 * ss, height);
        g.drawLine(9 * ss, 0, 9 * ss, height);
        g.drawLine(10 * ss, 0, 10 * ss, height);
        g.drawLine(11 * ss, 0, 11 * ss, height);
        g.drawLine(12 * ss, 0, 12 * ss, height);
        g.drawLine(13 * ss, 0, 13 * ss, height);
        g.drawLine(0, ss, width, ss);
        g.drawLine(0, 2 * ss, width, 2 * ss);
        g.drawLine(0, 3 * ss, width, 3 * ss);
        g.drawLine(0, 4 * ss, width, 4 * ss);
        g.drawLine(0, 5 * ss, width, 5 * ss);
        g.drawLine(0, 6 * ss, width, 6 * ss);
        g.drawLine(0, 7 * ss, width, 7 * ss);
        g.drawLine(0, 8 * ss, width, 8 * ss);
        g.drawLine(0, 9 * ss, width, 9 * ss);
        g.drawLine(0, 10 * ss, width, 10 * ss);
        g.drawLine(0, 11 * ss, width, 11 * ss);
        g.drawLine(0, 12 * ss, width, 12 * ss);
        g.drawLine(0, 13 * ss, width, 13 * ss);


        [color=darkred]// draw the pieces
        for (int i = 0; i < 169; i++) {
            row = i / 13;
            col = i % 13;
            x = col * ss;
            y = row * ss;
            drawPiece(g, posn.charAt(i), x, y);
        }
    }[/color]
// This is again not working so I went to class of GameTable.


    private void drawPiece(Graphics g, char piece, int x, int y) {

        switch (piece) {

            case 'x':




                g.drawLine(x + inset, y + inset, x + ss - inset, y + ss - inset);
                g.drawLine(x + ss - inset, y + inset, x + inset, y + ss - inset);


                break;

            case 'o':
                g.drawOval(x + inset, y + inset, ss - 2 * inset, ss - 2 * inset);
                break;
        }
    }
}
  

    
package gomuko;

import javax.swing.*;
import java.awt.*;
import java.awt.event.*;
import java.util.*;

public class GameTable extends JPanel implements ActionListener, ItemListener,
        MouseListener, MouseMotionListener {

    [color=blue]static final String startPosn = "111111111";[/color] 
    // I guess its not practical to
    //type 1's 169 times so i tried with String buffers and other 
    // methods. like setLength(), ensure Capacity(), but it didn't help
    // What did I miss?
    GameBoard gBoard;
    JTextArea tArea;
    Engine comp;
    JButton resetB;
    JButton moveB;
    JButton testB, test1B;
    StringBuilder posn;
    Boolean xTurn;
    boolean gameOver = false;
    int width = 300;
    int height = 400;

    public GameTable() {

        setPreferredSize(new Dimension(width, height));
        createGUI();
        reset();
    }

    private void createGUI() {

        setLayout(new BorderLayout());

        gBoard = new GameBoard(width, width);	// the board is square
        gBoard.addMouseListener(this);
        add(gBoard, BorderLayout.NORTH);

        JPanel controlPanel = new JPanel();
        add(controlPanel, BorderLayout.CENTER);

        resetB = new JButton("reset");
        resetB.addActionListener(this);
        controlPanel.add(resetB);

        moveB = new JButton("move");
//		moveB.addActionListener(this);
//		controlPanel.add( moveB );

        testB = new JButton("evaluate");
        testB.addActionListener(this);
        controlPanel.add(testB);

        test1B = new JButton("getMoves");
        test1B.addActionListener(this);
        controlPanel.add(test1B);



        tArea = new JTextArea();
        tArea.setPreferredSize(new Dimension(width, 50));
        add(tArea, BorderLayout.SOUTH);

    }

    private void makeMove() {

        tArea.setText("Move being made");
    }

    private void reset() {

        posn = new StringBuilder(startPosn);
        gBoard.reset(startPosn);
        comp = new Engine();
        gameOver = false;
        xTurn = true;
        tArea.setText("");
    }

    public void actionPerformed(ActionEvent e) {

        Object o = e.getSource();

        if (o == resetB) {
            reset();
            return;
        }

        if (o == moveB) {
            if (gameOver) {
                tArea.setText("Game is Over");
            } else {
                makeMove();
            }
            return;
        }

        if (o == testB) {

            String pStr = posn.toString();
            int eval = comp.evaluate(pStr);

            switch (eval) {

                case 0:
                    if (!pStr.contains("1")) {
                        gameOver = true;
                        tArea.setText("The game is a draw.");
                    } else {
                        tArea.setText("Game not over.");
                    }
                    break;

                case -1:
                    tArea.setText("o wins");
                    gameOver = true;
                    break;

                case 1:
                    tArea.setText("x wins");
                    gameOver = true;
                    break;

            }

            return;
        }

        if (o == test1B) {
            if (!gameOver) {
                String pStr = posn.toString();
                int[] moves = comp.possibleMoves(pStr);
                String s = "";
                for (int m : moves) {
                    s += m;
                }
                tArea.setText(s);
            } else {
                tArea.setText("The game is over");
            }
            return;
        }
    }

    public void itemStateChanged(ItemEvent e) {
    }

    public void mousePressed(MouseEvent e) {

        if (gameOver) {
            tArea.setText("game is over");
            return;
        }

        int x = e.getX();
        int y = e.getY();

        int row = y / (width / 3);
        int col = x / (width / 3);

        int index = 3 * row + col;

        if (posn.charAt(index) == '1') {
            posn.setCharAt(index, xTurn ? 'x' : 'o');
            tArea.setText("" + posn.charAt(index) + " is played.");
            xTurn = xTurn ? false : true;
            gBoard.reset(posn.toString());
        } else {
            tArea.setText("That square is occupied");
        }
    }

    public void mouseReleased(MouseEvent e) {
    }

    public void mouseClicked(MouseEvent e) {
    }

    public void mouseEntered(MouseEvent e) {
    }

    public void mouseExited(MouseEvent e) {
    }

    public void mouseMoved(MouseEvent e) {
    }

    public void mouseDragged(MouseEvent e) {
    }
}

    

[Fred Hamilton]

Gurudas Bhandarkar wrote:It was just a query from my side, never tried to emphasize i apologize if I may have sounded
that way.

Coming back to themain game called gomoku,
I modified your GameBoard class
...

No need to apologize, there is no problem here. I was just saying the reason why I can't just copy the alphabeta from my chess program. It's the way I wrote my chess Engine class, it is not as modular as it might have been. Don't worry about asking any questions, that's the purpose of the thread.

I'm not gonna comment on the goMoku, right now, I have to much to do, maybe later.

[Kabir Shah]

@Fred
Thank you very much for helping me out, though the game is not completed as of now I am getting into the swing components I have successfully modified the code for gomoku but small chink(at least I think so,) The evaluate function is not working properly now. As you said you are busy now, so I request you that whenever you get time, please take a look at the modified code.

Engine.java
GameTable.java
GameBoard.java

[Fred Hamilton]

OK Gurudas, here is what I have so far. The program works, but the computer is not making the best move.
I think something is wrong with my negaMax method. It will be a good experience for both of us to find the problem.

Once we get the negamax working properly, Then we add in the alphaBeta.

Notice the program is kind of slow. There are many thousands of ways to play a game of tictactoe.
Right now the engine looks at all of them. Once we get the negaMax working, then alphabeta will speed things up.
Also, the way I have used objects slows things down. The way I did it may be correct
from an Object Oriented Programming(OOP) point of view, but full-fledged OOP and game tree analysis
are not necessarily compatible.

If you want the computer to make a move in any position, click the move button. Note that way I have set things up
allows us to test out the individual components of the engine better. Once all the components are working.

Anyways, have a look and see if you can figure out how it works and what the problem with my negaMax is.
I probably won't be able to spend much time on this until tomorrow. But if you have any questions
about how this works, let me know.

import javax.swing.*;

public class GameFrame extends JFrame {

	GameTable gTable;

	public GameFrame( String title ) {
	
		super( title );
		gTable = new GameTable();
		add( gTable );
	}
	
	public static void main( String[] args ) {
	
		GameFrame gFrame = new GameFrame("TestFrame");
		gFrame.setDefaultCloseOperation(EXIT_ON_CLOSE);
		gFrame.pack();
		gFrame.setVisible(true);
	}
}

import javax.swing.*;
import java.awt.*;
import java.awt.event.*;
import java.util.*;

public class GameTable extends JPanel implements ActionListener, ItemListener,
								MouseListener, MouseMotionListener {

	static final String startPosn = "111111111";

	GameBoard gBoard;
	JTextArea tArea;
	Engine comp;
	JButton resetB;
	JButton moveB;
	JButton testB, test1B;
	StringBuilder posn;
	Boolean xTurn;
	
	boolean gameOver = false;
	
	int width = 300;
	int height = 400;

	public GameTable() {
	
		setPreferredSize( new Dimension(width, height) );
		createGUI();
		reset();
	}
	
	private void createGUI() {
	
		setLayout( new BorderLayout() );
		
		gBoard = new GameBoard( width, width );	// the board is square
		gBoard.addMouseListener(this);
		add( gBoard, BorderLayout.NORTH );
		
		JPanel controlPanel = new JPanel();
		controlPanel.setLayout( new GridLayout(1,0) );
		add( controlPanel, BorderLayout.CENTER );
		
		resetB = new JButton("reset");
		resetB.setMargin( new Insets(5,3,5,3) );
		resetB.addActionListener(this);
		controlPanel.add( resetB );
		
		moveB = new JButton("move");
		moveB.setMargin( new Insets(5,3,5,3) );
		moveB.addActionListener(this);
		controlPanel.add( moveB );
		
		testB = new JButton("evaluate");
		testB.setMargin( new Insets(5,3,5,3) );
		testB.addActionListener(this);
		controlPanel.add(testB);
		
		test1B = new JButton("getMoves");
		test1B.setMargin( new Insets(5,3,5,3) );
		test1B.addActionListener(this);
		controlPanel.add(test1B);
		
		tArea = new JTextArea();
		tArea.setPreferredSize( new Dimension( width, 50 ) );
		add( tArea, BorderLayout.SOUTH );
		
	}
	
	private void update( Move m ) {
	
		posn.setCharAt(m.square, xTurn ? 'x' : 'o');
		xTurn = xTurn ? false : true;
		String pStr = posn.toString();
		gBoard.reset( pStr );
		
		int eval = comp.evaluate( pStr, xTurn );
		
		if( eval == 1 ) {
			tArea.setText(" X wins.");
			gameOver = true;
		}
		else if( eval == -1 ) {
			tArea.setText(" O wins.");
			gameOver = true;
		}
		else {
			if( !pStr.contains("1") ) {
				tArea.setText(" The game is a draw.");
				gameOver = true;
			}
			else tArea.setText( m.comment );
		}
	}
	
	private void makeMove() {
	
		if( gameOver ) {
			tArea.setText( "The game is over" );
			return;
		}
		
		long t1,t2;
		
		t1 = (new Date()).getTime();
		
		Move m = comp.getMove( posn.toString(), xTurn );
		
		t2 = (new Date()).getTime();
		
		m.comment = " " +(xTurn ? "x" : "o") +" is played. Time = " +(t2-t1) +" milliseconds.";
		
		update( m );
		
	}
	
	private void reset() {
	
		posn = new StringBuilder( startPosn );
		gBoard.reset( startPosn );
		comp = new Engine();
		gameOver = false;
		xTurn = true;
		tArea.setText("");
	}
	
	public void actionPerformed( ActionEvent e ) {

		Object o = e.getSource();
	
		if( o == resetB) {
			reset();
			return;
		}
		
		if( o == moveB ) {
			if( gameOver ) {
				tArea.setText("Game is Over");
			}
			else {
				makeMove();
			}
			return;
		}
		
		if( o == testB ) {
		
			String pStr = posn.toString();
			int eval = comp.evaluate( pStr, xTurn );
			
			switch( eval ) {
			
				case 0:
						if(!pStr.contains("1")) {
							gameOver = true;
							tArea.setText("The game is a draw.");
						}
						else {
							tArea.setText("Game not over.");
						}
						break;
						
				case -1:
						tArea.setText("o wins");
						gameOver = true;
						break;
						
				case 1:
						tArea.setText("x wins");
						gameOver = true;
						break;
				
			}
			
			return;
		}
		
		if( o == test1B ) {
			if( !gameOver ) {
				String pStr = posn.toString();
				Move[] moves = comp.possibleMoves(pStr); String s = "";
				for( Move m : moves ) {
					s += m.square;
				}
				tArea.setText(s);
			}
			else {
				tArea.setText("The game is over");
			}
			return;
		}
	}
	
	public void itemStateChanged( ItemEvent e ) {}
	
	public void mousePressed( MouseEvent e ) {
	
		if( gameOver ) {
			tArea.setText("game is over");
			return;
		}
	
		int x = e.getX();
		int y = e.getY();
		
		int row = y/(width/3);
		int col = x/(width/3);
		
		int square = 3*row + col;
		
		if( posn.charAt(square) == '1' ) {
			update( new Move(square,0) );
		}
		else {
			tArea.setText("That square is occupied");
		}
	}
	
	public void mouseReleased( MouseEvent e ) {}
	public void mouseClicked( MouseEvent e ) {}
	public void mouseEntered( MouseEvent e ) {}
	public void mouseExited( MouseEvent e ) {}
	public void mouseMoved( MouseEvent e ) {}
	public void mouseDragged( MouseEvent e ) {}
	
}

import javax.swing.*;
import java.awt.*;

public class GameBoard extends JPanel {

	private int width, height, ss, inset;
	private StringBuilder posn;

	public GameBoard( int width, int height ) {
	
		this.width = width;
		this.height = height;
		ss = width/3;
		inset = ss/5;
	
		setPreferredSize( new Dimension( width, height ) );
		setBackground( Color.GREEN );
		
		posn = new StringBuilder("111111111");
	}
	
	public void reset( String posn ) {
		this.posn = new StringBuilder( posn );
		repaint();
	}	
	
	public void paintComponent( Graphics g ) {
	
		int piece;
		int x, y, row, col;
	
		super.paintComponent( g );
		
		// draw the grid
		g.drawLine( ss, 0, ss, height );
		g.drawLine( 2*ss, 0, 2*ss, height);
		g.drawLine( 0, ss, width, ss );
		g.drawLine( 0, 2*ss, width, 2*ss);
		
		// draw the pieces
		for( int i=0; i<9; i++ ) {
			row = i/3; col = i%3;
			x = col*ss; y = row*ss;
			drawPiece( g, posn.charAt(i), x, y );
		}
	}
	
	private void drawPiece( Graphics g, char piece, int x, int y ) {
	
		switch(piece) {
		
			case 'x':
				g.drawLine( x+inset, y+inset, x+ss-inset, y+ss-inset);
				g.drawLine( x+ss-inset, y+inset, x+inset, y+ss-inset);
				break;
			
			case 'o':
				g.drawOval( x+inset, y+inset, ss-2*inset, ss-2*inset);
				break;
		}
	}
		
}

public class Engine {

public Move getMove( String pStr, boolean xTurn ) {

	String p1Str;
	int eval;
	int move = 99;

	Move[] mList = possibleMoves(pStr);

	for( int i = 0; i < mList.length; i++ ) {

		p1Str = pStr.substring(0, mList[i].square) + (xTurn ? 'x' : 'o') + pStr.substring( mList[i].square+1 );
		mList[i].eval = -negaMax( p1Str, !xTurn );
	}
	
	int index = findBestMove( mList );
	
	return mList[index];
}

/*********************************************************************************/

private int findBestMove( Move[] mList ) {

	int maxEval = mList[0].eval;
	int maxIndex = 0;
	Move m;
	
	for( int i=1; i<mList.length; i++ ) {
		
		if( mList[i].eval > maxEval ) {
			maxEval = mList[i].eval;
			maxIndex = i;
		}
	}
	
	return maxIndex;
}

/*********************************************************************************/

private int negaMax( String pStr, boolean xTurn ) {

	String p1Str;

	Move[] mList = possibleMoves( pStr );
	if( mList.length == 0 ) return evaluate( pStr, xTurn );
	
	for( int i = 0; i < mList.length; i++ ) {

		p1Str = pStr.substring(0, mList[i].square ) + (xTurn ? 'x' : 'o') + pStr.substring( mList[i].square+1 );
		mList[i].eval = -negaMax( p1Str, !xTurn );
	}
	
	int index = findBestMove( mList );
	
	return mList[index].eval;
}		

/*********************************************************************************/

public Move[] possibleMoves( String pStr ) {

	Move[] list1 = new Move[9];
	int count = 0;
	int row, col;
	
	for( int i=0; i<9; i++ ) {
		if( pStr.charAt(i) == '1' ) list1[count++] = new Move(i,0);
	}
	
	Move[] list2 = new Move[count];
	System.arraycopy( list1, 0, list2, 0, count );
	
	return list2;
}

/*********************************************************************************/

 public int evaluate( String pStr, boolean xTurn ) {

	String s;
	int eval = 0;

	for( int i=0; i<3; i++ ) {
		s = pStr.substring(3*i, 3*i+3);
		if( s.matches("x+") ) eval = 1;
		if( s.matches("o+") ) eval = 1;

		s = "" +pStr.charAt(i) + pStr.charAt(i+3) +pStr.charAt(i+6);
		if( s.matches("x+") ) eval = 1;
		if( s.matches("o+") ) eval = 1;
	}
	
	s = "" +pStr.charAt(0) + pStr.charAt(4) + pStr.charAt(8);
	if( s.matches("x+") ) eval = 1;
	if( s.matches("o+") ) eval = 1;
	
	s = "" +pStr.charAt(2) + pStr.charAt(4) + pStr.charAt(6);
	if( s.matches("x+") ) eval = 1;
	if( s.matches("o+") ) eval = 1;
	
	return eval;
}

/*********************************************************************************/

}

public class Move {

	int square;
	int eval;
	String comment = "";
	
	public Move( int square, int eval ) {
		this.square = square;
		this.eval = eval;
	}
}

[Kabir Shah]

The program plays but it does take lot of time.
More over if observed care fully, It plays in the sequence available like, if 0 is available(0,0) then it puts there or it moves to the next possible
square for 1.. and so on so the AI searches for a vacant place
rather than to look for a win and that too in serial manner
( I recognized it after playing 5-6 games and came to this conclusion after playing around 10-15 games.)
So I guess the error is in Engine class.

I think the statement

private int findBestMove(Move[] mList) {

        int maxEval = mList[0].eval; //  Here it will always compare with the mList[0] eval, 
//even when there is 1st or second iteration and so on. I don't know what exactly is to be 

//written but do think that this is what is causing problem.
        int maxIndex = 0;
        Move m;

        for (int i = 1; i < mList.length; i++) {

            if (mList[i].eval > maxEval) {
                maxEval = mList[i].eval;
                maxIndex = i;
            }
        }

        return maxIndex;
    }    

More over I didnot understand the meaning of this

    p1Str = pStr.substring(0, mList[i].square) 
+ (xTurn ? 'x' : 'o') + pStr.substring(mList[i].square + 1); 

is it to make copy or something?

Also after making negamax, the scores for both players are positive,
as far as I remember,
in connect four(though it was wrong implementation),
I made a condition as if there is winning condition,
if its computer then give a positive value or else negative value.
Also at the winning condition, eval is assigned to 1.
But I think
(which may be wrong as you are more experienced and better programmer ) eval should be very high.

this is sort of new coding style to me, so I might take a day or two to actually understand how this thing works. If at all there is any simpler style, please discuss it here.

right now these are the only things which I can come across.

i guess this is fine causing no troubles.

[Fred Hamilton]

Gurudas, please edit your posts to remove the long comments within code tags

This is messing up the page

[Kabir Shah]

Just help me out in locating the variable which is used to refer the maximum search depth and
also the depth counter.

[Fred Hamilton]

Gurudas Bhandarkar wrote:Just help me out in locating the variable which is used to refer the maximum search depth and
also the depth counter.

those things don't exist it is supposed to search till gameOver

[Kabir Shah]

But in that case, this logic could not be applied in games where search space is very huge,
like chess or checkers and in this case its gomoku( later on trying to modify tic tac toe).
even if its played on 13x13 board, the complexity is of 10^70.
and tic-tac-toe is of 9!.
So I guess a universal strategy of implementing this for any game would be better.
I don't know if I have explained properly, but changing this every time for new game seems to be difficult.

[Fred Hamilton]

private int findBestMove(Move[] mList) {

int maxEval = mList[0].eval; // Here it will always compare with the mList[0] eval,
//even when there is 1st or second iteration and so on. I don't know what exactly is to be

//written but do think that this is what is causing problem.
int maxIndex = 0;
Move m;

for (int i = 1; i < mList.length; i++) {

if (mList[i].eval > maxEval) {
maxEval = mList[i].eval;
maxIndex = i;
}
}

return maxIndex;
}

maxEval = mList[0].eval is just the initial eval. It is supposed to gt updated within the loop whenever there is a move value that is
higher. This part of the kode is ok, but your answer does suggest that the values being assigned to each move are incorrect.

[Fred Hamilton]

Gurudas Bhandarkar wrote:But in that case, this logic could not be applied in games where search space is very huge,
like chess or checkers and in this case its gomoku( later on trying to modify tic tac toe).
even if its played on 13x13 board, the complexity is of 10^70.
and tic-tac-toe is of 9!.
So I guess a universal strategy of implementing this for any game would be better.
I don't know if I have explained properly, but changing this every time for new game seems to be difficult.

yes you are correct. But the game isn't finished. Once we get it to work,
then we create a generalized version.

[Kabir Shah]

Also the eval signs had to be changed ass for X it is 1 and for O it is -1.
But in engine class it is declared 1 for both x and o.
So what should be done now?
Anyways just a question, in what field you have done your education?
I started liking Java after doing introductory course in it. But I am undergraduate student of electronics. If I have to make career in Java, what should I do?

[Fred Hamilton]

Gurudas Bhandarkar wrote:
Also the eval signs had to be changed ass for X it is 1 and for O it is -1.
But in engine class it is declared 1 for both x and o.
So what should be done now?
Anyways just a question, in what field you have done your education?
I started liking Java after doing introductory course in it.
But I am undergraduate student of electronics. If I have to make career in Java, what should I do?

That's a good guess, but it doesn't have to be that way.
As a matter of fact, whether it is x or o to move, the last line
in evaluate method should be return -eval; Can you see why?


also, the following two lines of code should be added to the very
beginning of the negamax method. Cause we did not have a test
for the game being won before all the squares were filled.

int eval = evaluate( pStr, xTurn );
if( Math.abs( eval ) == 1 ) return eval;

also, there is a small error in the GameTable class, where it always says
o has won, even when x has won, but that is just a reporting error.

I have a degree in mathematics, a long time ago. I'm not a professional
programmer, but I'd like to be, I have a few more things to learn.

p.s. there is still one small problem that depends on move order. If the
engine can win in one move, it might instead play a move that takes longer
to win. But it will always find a win if one is there, it just might not be
the quickest win. Any idea how we might fix that?

Anyways, I've updated the website. I'm gonna tidy up the code a bit and make
a revised version available

http://fchess.uuuq.com/test1/tictactoe.htm

[Kabir Shah]

I have just the idea for it,
maybe we can increase the value for eval on the next move.
the program, finds the winning move in 3, and in 1 now it can win in 1 or in 3, still it prefers the win in 3.
so something like eval=(maxdepth-currdepth) so eval for 3 will be less than that of eval for 1.
so it will take the value when there is win for one.
I don't know how to code this.

Also do you mind to repost all the classes which were modified?
also let me know how did you learn program basic in java and then programing AI in java, which books did you refer to.

[Fred Hamilton]

Gurudas Bhandarkar wrote:I have just the idea for it,
maybe we can increase the value for eval on the next move.
the program, finds the winning move in 3, and in 1 now it can win in 1 or in 3, still it prefers the win in 3.
so something like eval=(maxdepth-currdepth) so eval for 3 will be less than that of eval for 1.
so it will take the value when there is win for one.
I don't know how to code this.

Also do you mind to repost all the classes which were modified?
also let me know how did you learn program basic in java and then programing AI in java, which books did you refer to.

That's a pretty good idea, more or less what I had in mind. In negamax instead of returning evaluate(),
we return evaluate() - depth, or something like that. It all depends how we define the term 'depth'. It means
different things to different people. However, before we do that, can you explain why this happens that the
computer might choose a longer win over a shorter one?

For java I am pretty much self taught, with a little help from the people at JavaRanch.
I started my chess project a couple of years ago, and used that as my learning project. When I needed information,
I would look on the internet. Good tutorials are hard to find, but the following was especially good, I suggest you work
throughh the entire course, it is straightforward and you wil learn a lot. And it will make it easier to deal with
the Sun java tutorial.

http://chortle.ccsu.edu/CS151/cs151java.html

The project we are just starting now, which is a general framework for strategy board games, will take
a long time and you will learn a lot.

[Kabir Shah]

i guess the computer is taking long route to win because in the above program,
it searches for the entire game tree. So at a time its taking only one way to win
(need not be the immediate win).
It will search through the entire game tree and as of now, depth now is maximum.
i.e 9 so it will search first for win in 9 then after the first move,
depth reduces to 8 and then to 7 and so on.
so if it finds win in 3(after 6 moves),
then it will not bother to see immediate win,
because it knows that its going to win in next 3 moves by force.
Now the AI calculates step by step. So as it sees first if there is win for opponent,
it will block it.
Suppose human has win in 1, then it will block the square ,
if human has chance in 2, then blocking the required squares.
So coming back to why AI doesn't go for immediate win,
my reason would be that if it is sure that it has win on final move,
it will still follow the same path ignoring even if there is win is 1.

[Fred Hamilton]

Gurudas Bhandarkar wrote:i guess the computer is taking long route to win because in the above program,
it searches for the entire game tree. So at a time its taking only one way to win
(need not be the immediate win).
It will search through the entire game tree and as of now, depth now is maximum.
i.e 9 so it will search first for win in 9 then after the first move,
depth reduces to 8 and then to 7 and so on.
so if it finds win in 3(after 6 moves),
then it will not bother to see immediate win,
because it knows that its going to win in next 3 moves by force.
Now the AI calculates step by step. So as it sees first if there is win for opponent,
it will block it.
Suppose human has win in 1, then it will block the square ,
if human has chance in 2, then blocking the required squares.
So coming back to why AI doesn't go for immediate win,
my reason would be that if it is sure that it has win on final move,
it will still follow the same path ignoring even if there is win is 1.

That is close enough.
We are doing what is called a depth first search, which means the program searches
to the very end of the first variation before going to the next variation. Also, a winning move gets
the same value regardless of how long it takes to win. Finally the method findBestMove assigns
to maxIndex the index of a winning move, then looks for a better move. But there are no better moves
because a move either wins or it doesn't, we don't care how long it takes. So it plays the first winning move
it finds, regardless of how deep the win is. So you can see there is room here top speed up the play, although we
cannot really improve the strngth of the play any more.

It is worth pointing out that in TicTacToe, this approach is fine, because the number of possible moves dwindles
to zero. But this does not happen with chess. In chess, if you do not assign a higher value to a quicker checkmate,
then it is possible that at each turn the computer will choose a move that leads to checkmate in two over a move that
leads to checkmate in one. So even though the computer "sees the win", it is unable to play the move that actually gives
checkmate right away, because it always finds a slower checkmate sooner.

[Kabir Shah]

You are a very good teacher.

but then how to speed up the play here? using the idea similar to that of maxdepth-currdepth
or what else is there?

Also is there any way by which I can store these moves played and use it as opening book, for tictactoe its not required but for gomoku, I think that even having opening book speed up the game.
Do I really have know some things in database some thing like sql or JDBC?

[Fred Hamilton]

Hi Gurudas

Here is the most recent version of my code. All of the classes are here. I decided not to deal with the situation of not playing the fastest win, we would have to change a number of things to make it work, and it isn't worth it.

I have added the alphaBeta code. Notice how much faster the game is. When we are searching at a fixed depth, alphaBeta does not improve the strength of play, but it does speed things up. If were were playing a game where we were limiting the amount of time the engine had to think, then alphaBeta would indeed improve the playing strength.

Notice how evaluate() always returns -eval. The reason is that the eval is either 1 for a win, or 0 for no win. the variable xTurn is a boolean indicating side to move. If the game is a win, then it must be a loss for side to move, because the game is over side to move has no move. Therefore the evaluate is expressed in terms of the side to play, which in this game is the loser, so we return -eval.

I suggest you look over the code and decide how it can be modified to a general NxN tic tac toe, where the number of rows in the grid is decided by a single variable in the GUI, and the changes would apply to everywhere, especially in the evaluate() method.

The applet is updated also.

http://fchess.uuuq.com/test1/tictactoe.htm

p.s. now that we have added the alphabeta code, I am 99% sure we won't need the findBestMove() method in our Engine class.

import javax.swing.*;

public class GameFrame extends JFrame {

	GameTable gTable;

	public GameFrame( String title ) {
	
		super( title );
		gTable = new GameTable();
		add( gTable );
	}
	
	public static void main( String[] args ) {
	
		GameFrame gFrame = new GameFrame("TestFrame");
		gFrame.setDefaultCloseOperation(EXIT_ON_CLOSE);
		gFrame.pack();
		gFrame.setVisible(true);
	}
}

import javax.swing.*;
import java.awt.*;
import java.awt.event.*;
import java.util.*;

public class GameTable extends JPanel implements ActionListener, ItemListener,
								MouseListener, MouseMotionListener {

	static final String startPosn = "111111111";

	GameBoard gBoard;
	JTextArea tArea;
	Engine comp;
	JButton resetB;
	JButton moveB;
	JButton testB, test1B;
	StringBuilder posn;
	Boolean xTurn;
	
	boolean gameOver = false;
	
	int width = 300;
	int height = 400;

	public GameTable() {
	
		setPreferredSize( new Dimension(width, height) );
		createGUI();
		reset();
	}
	
	private void createGUI() {
	
		setLayout( new BorderLayout() );
		
		gBoard = new GameBoard( width, width );	// the board is square
		gBoard.addMouseListener(this);
		add( gBoard, BorderLayout.NORTH );
		
		JPanel controlPanel = new JPanel();
		controlPanel.setLayout( new GridLayout(1,0) );
		add( controlPanel, BorderLayout.CENTER );
		
		resetB = new JButton("reset");
		resetB.setMargin( new Insets(5,3,5,3) );
		resetB.addActionListener(this);
		controlPanel.add( resetB );
		
		moveB = new JButton("move");
		moveB.setMargin( new Insets(5,3,5,3) );
		moveB.addActionListener(this);
		controlPanel.add( moveB );
		
		testB = new JButton("evaluate");
		testB.setMargin( new Insets(5,3,5,3) );
		testB.addActionListener(this);
		controlPanel.add(testB);
		
		test1B = new JButton("getMoves");
		test1B.setMargin( new Insets(5,3,5,3) );
		test1B.addActionListener(this);
		controlPanel.add(test1B);
		
		tArea = new JTextArea();
		tArea.setPreferredSize( new Dimension( width, 50 ) );
		add( tArea, BorderLayout.SOUTH );
		
	}
	
	private void update( Move m ) {
	
		posn.setCharAt(m.square, xTurn ? 'x' : 'o');
		xTurn = xTurn ? false : true;
		String pStr = posn.toString();
		gBoard.reset( pStr );
		
		comp.posn = new StringBuilder(pStr);
		int eval = comp.evaluate();
		
		if( eval == -1 ) {
			tArea.setText( xTurn ? " O wins." : " x wins." );
			gameOver = true;
		}
		else {
			if( !pStr.contains("1") ) {
				tArea.setText(" The game is a draw.");
				gameOver = true;
			}
			else tArea.setText( m.comment );
		}
	}
	
	private void makeMove() {
	
		if( gameOver ) {
			tArea.setText( "The game is over" );
			return;
		}
		
		long t1,t2;
		
		t1 = (new Date()).getTime();
		
		Move m = comp.getMove( posn.toString(), xTurn );
		
		t2 = (new Date()).getTime();
		
		m.comment = " " +(xTurn ? "x" : "o") +" is played. Time = " +(t2-t1) +" milliseconds.";
		
		update( m );
		
	}
	
	private void reset() {
	
		posn = new StringBuilder( startPosn );
		gBoard.reset( startPosn );
		comp = new Engine();
		gameOver = false;
		xTurn = true;
		tArea.setText("");
	}
	
	public void actionPerformed( ActionEvent e ) {

		Object o = e.getSource();
	
		if( o == resetB) {
			reset();
			return;
		}
		
		if( o == moveB ) {
			if( gameOver ) {
				tArea.setText("Game is Over");
			}
			else {
				makeMove();
			}
			return;
		}
		
		if( o == testB ) {
		
			String pStr = posn.toString();
			comp.posn = new StringBuilder(pStr);
			int eval = comp.evaluate();
			
			switch( eval ) {
			
				case 0:
						if(!pStr.contains("1")) {
							gameOver = true;
							tArea.setText("The game is a draw.");
						}
						else {
							tArea.setText("Game not over.");
						}
						break;
						
				case -1:
						tArea.setText(" " +(xTurn ? "o" : "x") +" wins.");
						gameOver = true;
						break;
						
			}
			
			return;
		}
		
		if( o == test1B ) {
			if( !gameOver ) {
				String pStr = posn.toString();
				comp.posn = new StringBuilder(pStr);
				Move[] moves = comp.possibleMoves(); String s = "";
				for( Move m : moves ) {
					s += m.square;
				}
				tArea.setText(s);
			}
			else {
				tArea.setText("The game is over");
			}
			return;
		}
	}
	
	public void itemStateChanged( ItemEvent e ) {}
	
	public void mousePressed( MouseEvent e ) {
	
		if( gameOver ) {
			tArea.setText("game is over");
			return;
		}
	
		int x = e.getX();
		int y = e.getY();
		
		int row = y/(width/3);
		int col = x/(width/3);
		
		int square = 3*row + col;
		
		if( posn.charAt(square) == '1' ) {
			update( new Move(square,0) );
		}
		else {
			tArea.setText("That square is occupied");
		}
	}
	
	public void mouseReleased( MouseEvent e ) {}
	public void mouseClicked( MouseEvent e ) {}
	public void mouseEntered( MouseEvent e ) {}
	public void mouseExited( MouseEvent e ) {}
	public void mouseMoved( MouseEvent e ) {}
	public void mouseDragged( MouseEvent e ) {}
	
}

import javax.swing.*;
import java.awt.*;

public class GameBoard extends JPanel {

	private int width, height, ss, inset;
	private StringBuilder posn;

	public GameBoard( int width, int height ) {
	
		this.width = width;
		this.height = height;
		ss = width/3;
		inset = ss/5;
	
		setPreferredSize( new Dimension( width, height ) );
		setBackground( Color.GREEN );
		
		posn = new StringBuilder("111111111");
	}
	
	public void reset( String posn ) {
		this.posn = new StringBuilder( posn );
		repaint();
	}	
	
	public void paintComponent( Graphics g ) {
	
		int piece;
		int x, y, row, col;
	
		super.paintComponent( g );
		
		// draw the grid
		g.drawLine( ss, 0, ss, height );
		g.drawLine( 2*ss, 0, 2*ss, height);
		g.drawLine( 0, ss, width, ss );
		g.drawLine( 0, 2*ss, width, 2*ss);
		
		// draw the pieces
		for( int i=0; i<9; i++ ) {
			row = i/3; col = i%3;
			x = col*ss; y = row*ss;
			drawPiece( g, posn.charAt(i), x, y );
		}
	}
	
	private void drawPiece( Graphics g, char piece, int x, int y ) {
	
		switch(piece) {
		
			case 'x':
				g.drawLine( x+inset, y+inset, x+ss-inset, y+ss-inset);
				g.drawLine( x+ss-inset, y+inset, x+inset, y+ss-inset);
				break;
			
			case 'o':
				g.drawOval( x+inset, y+inset, ss-2*inset, ss-2*inset);
				break;
		}
	}
		
}

public class Engine {

int maxDepth = 9;
StringBuilder posn;

public Move getMove( String pStr, boolean xTurn ) {

	String p1Str;
	int eval;
	int index = 0;
	
	
	int alpha = -2;
	int beta = 2;
	
	posn = new StringBuilder( pStr );

	Move[] mList = possibleMoves();

	for( int i = 0; i < mList.length; i++ ) {

		posn.setCharAt( mList[i].square, xTurn ? 'x' : 'o' );
		mList[i].eval = -negaMax( !xTurn, maxDepth-1, -beta, -alpha  );
		posn.setCharAt( mList[i].square, '1' );
		
		if( mList[i].eval > alpha ) {
			alpha = mList[i].eval;
			index = i;
		}
	}
	
	return mList[index];
}

/*********************************************************************************/

private int findBestMove( Move[] mList ) {

	int maxEval = mList[0].eval;
	int maxIndex = 0;
	Move m;
	
	for( int i=1; i<mList.length; i++ ) {
		
		if( mList[i].eval > maxEval ) {
			maxEval = mList[i].eval;
			maxIndex = i;
		}
	}
	
	return maxIndex;
}

/*********************************************************************************/

private int negaMax( boolean xTurn, int depth, int alpha, int beta ) {

	int eval = evaluate();
	
	if( (eval == -1) || (depth==0) ) return eval;

	Move[] mList = possibleMoves();
	if( mList.length == 0 ) return evaluate();
	
	for( int i = 0; i < mList.length; i++ ) {

		posn.setCharAt(mList[i].square, xTurn ? 'x' : 'o');
		mList[i].eval = -negaMax( !xTurn, depth-1, -beta, -alpha );
		posn.setCharAt(mList[i].square, '1');

		if( mList[i].eval >= beta ) return beta;
		if( mList[i].eval > alpha ) alpha = mList[i].eval;
	}
	
	return alpha;
}		

/*********************************************************************************/

public Move[] possibleMoves() {

	Move[] list1 = new Move[9];
	int count = 0;
	int row, col;
	
	for( int i=0; i<posn.length(); i++ ) {
		if( posn.charAt(i) == '1' ) list1[count++] = new Move(i,0);
	}
	
	Move[] list2 = new Move[count];
	System.arraycopy( list1, 0, list2, 0, count );
	
	return list2;
}

/*********************************************************************************/

 public int evaluate() {

	String s;
	int eval = 0;

	for( int i=0; i><3; i++ ) {
		s = posn.substring(3*i, 3*i+3);
		if( s.matches("x+") ) eval = -1;
		if( s.matches("o+") ) eval = -1;

		s = "" +posn.charAt(i) + posn.charAt(i+3) +posn.charAt(i+6);
		if( s.matches("x+") ) eval = -1;
		if( s.matches("o+") ) eval = -1;
	}
	
	s = "" +posn.charAt(0) + posn.charAt(4) + posn.charAt(8);
	if( s.matches("x+") ) eval = -1;
	if( s.matches("o+") ) eval = -1;
	
	s = "" +posn.charAt(2) + posn.charAt(4) + posn.charAt(6);
	if( s.matches("x+") ) eval = -1;
	if( s.matches("o+") ) eval = -1;
	
	return eval;
}

/*********************************************************************************/

}

public class Move {

	int square;
	int eval;
	String comment = "";
	
	public Move( int square, int eval ) {
		this.square = square;
		this.eval = eval;
	}
}

[Kabir Shah]

@ Fred
Thanks a million.
But I guess that I can approach you for any help required for gomuko, only if you permit.

[Fred Hamilton]

Gurudas Bhandarkar wrote:@ Fred
Thanks a million.
But I guess that I can approach you for any help required for gomuko, only if you permit.

Sure, GoMoku sounds interesting, I'd like to try that myself. It would be easy enough to write an engine class that played the game by the rules, but very difficult to write an evaluate() function to properly evaluate intermediate positions.

I think Othello (Reversi) would be a little easier that GoMoko, you might want to try that first.

So count me in, although it will be a little while before I can deal with a new game. We can keep this thread going though.

Do you know a game called Pig in The Fence?

[Kabir Shah]

No I don't know, can you describe it a bit.

[Kabir Shah]

@Fred

I am having a hard time in writing evaluation function of gomuko.
I thought that othello and reversi might be more difficult to write.
well do you any idea how can write the evaluate function? (ofcourse I cant ask for more as you have done a lot for me, but if you find time then I would like to discuss this with you.)

[Fred Hamilton]

Gurudas Bhandarkar wrote:@Fred

I am having a hard time in writing evaluation function of gomuko.
I thought that othello and reversi might be more difficult to write.
well do you any idea how can write the evaluate function? (ofcourse I cant ask for more as you have done a lot for me, but if you find time then I would like to discuss this with you.)

I'm not surprised yo have a problem. An evaluate() function for GoMoku would not be easy. I have to disagree with you. An evaluate() function for Reversi would be easier. As a starting point for Reversi evaluate(), all you have to do as add up the black and white disks. Then you can slowly improve your evaluate.

But before you write an evaluate function, you need to design your internal position array, and how to represent that graphically. Then, you need to define what constitutes a legal move. Then you have to figure out how to update the position array. Once you do all that then it will become much easier to experiment with different evaluate() functions.

Anyways, here is a little GUI I just wrote that would be a good starting point. for Othello or GoMOku. Pay close attention to my internal position array which is in the GameBoard class. And think about how this array might help you write an evaluate() function for Reversi.

Anyways, I can't help you with goMoku right now. I'm going to do Reversi first, cause it is easier. Trust me it is..

http://fchess.uuuq.com/test1/Grid.htm

import javax.swing.*;

public class Grid extends JFrame {

	GameTable gTable;

	public Grid( String title ) {
	
		super( title );
		gTable = new GameTable();
		add( gTable );
	}
	
	public static void main( String[] args ) {
	
		Grid gFrame = new Grid("TestFrame");
		gFrame.setDefaultCloseOperation(EXIT_ON_CLOSE);
		gFrame.pack();
		gFrame.setVisible(true);
	}
}

import javax.swing.*;
import javax.swing.event.*;
import java.awt.*;
import java.awt.event.*;

public class GameTable extends JPanel implements ActionListener, ItemListener,
								MouseListener, MouseMotionListener, ChangeListener {

	GameBoard gBoard;
	JTextArea tArea;
	JSpinner spinner;
	JButton resetB;
	SpinnerNumberModel snm;
	
	int width = 400;
	int height = 500;
	int N = 3;
	
	int piece = -1;

	public GameTable() {
	
		setPreferredSize( new Dimension(width, height) );
		createGUI();
	}
	
	private void createGUI() {
	
		setLayout( new BorderLayout() );
		
		gBoard = new GameBoard( width, width, N );	// the board is square
		gBoard.addMouseListener(this);
		add( gBoard, BorderLayout.NORTH );
		
		JPanel controlPanel = new JPanel();
		add( controlPanel, BorderLayout.CENTER );
		
		resetB = new JButton("reset");
		resetB.addActionListener(this);
		controlPanel.add( resetB );
		
		Integer min = new Integer(3);
		Integer max = new Integer(13);
		Integer step = new Integer(1);
		Integer def = new Integer(3);
		snm = new SpinnerNumberModel(def, min, max, step);
		spinner = new JSpinner( snm );
		spinner.addChangeListener(this);
		controlPanel.add(spinner);
		
		
		tArea = new JTextArea();
		tArea.setPreferredSize( new Dimension( width, 50 ) );
		add( tArea, BorderLayout.SOUTH );
		
	}
	
	public void actionPerformed( ActionEvent e ) {
		Object o = e.getSource();
	
		if( o == resetB ) {
			gBoard.posn = new int[N][N];
			gBoard.repaint();
			tArea.setText("");
			piece = -1;
			return;
		}
	}
	
	public void stateChanged( ChangeEvent e ) {
	
		Object o = e.getSource();
		
		if( o == spinner ) {
		
			N = ((Integer) snm.getNumber()).intValue();
			gBoard.reset(N);
			tArea.setText("");
		}
	
	}
	
	public void itemStateChanged( ItemEvent e ) {}
	
	public void mousePressed( MouseEvent e ) {
	
	
		int x = e.getX();
		int y = e.getY();
		
		int ss = width/N;
		
		int row = y/ss;
		int col = x/ss;
		
		if( gBoard.posn[row][col] != 0 ) return;
		
		int index = N*row + col;
		
		gBoard.addPiece( row, col, piece *= -1 );
		
		tArea.setText( "row = " +row +", col = " +col +", index = " +index );
	}
	
	public void mouseReleased( MouseEvent e ) {}
	public void mouseClicked( MouseEvent e ) {}
	public void mouseEntered( MouseEvent e ) {}
	public void mouseExited( MouseEvent e ) {}
	public void mouseMoved( MouseEvent e ) {}
	public void mouseDragged( MouseEvent e ) {}
	
}

import javax.swing.*;
import java.awt.*;

public class GameBoard extends JPanel {

	int width, height;
	int[][] posn;
	int N, ss;
	int offset;

	public GameBoard( int width, int height, int numRows ) {
	
		this.width = width;
		this.height = height;
		this.N = numRows;
		this.ss = width/N;
		this.offset = ss/5;
		
		this.posn = new int[N][N];
	
		setPreferredSize( new Dimension( width, height ) );
		setBackground( Color.GREEN );
	}
	
	public void reset( int N ) {
	
		this.N = N;
		posn = new int[N][N];
		this.ss = width/N;
		this.offset = ss/5;
		repaint();
	}
	
	public void addPiece( int row, int col, int piece ) {
	
		posn[row][col] = piece;
		repaint();
	}
	
	public void paintComponent( Graphics g ) {
	
		super.paintComponent( g );
		
		int piece;
		int x,y,d;
		
		for( int i=0; i<N; i++ ) {
			g.drawLine( i*ss, 0, i*ss, height );
			g.drawLine( 0, i*ss, width, i*ss );
		}
		
		for( int i=0; i<N; i++ ) {
			for( int j=0; j<N; j++ ) {
				x = j*ss + offset;
				y = i*ss + offset;
				d = ss - 2*offset;
				piece = posn[i][j];
				if( piece == 0 ) continue;
				g.setColor( (piece==1) ? Color.BLACK : Color.WHITE );
				g.fillOval( x, y, d, d );
			}
		}
	}
}

[Kabir Shah]

@Fred
I would really like to be with you in this project. Would you allow me to be with you and share your updates?
Also for reversi, as I have read the rules, There are 2 pieces of each color in middle of the board.

[Kabir Shah]

Mean while I would also like to build a Gomoku, before 15th October.(After that my exams begin from 20th October so will have to study electronics) so can I ask you the doubts for Gomoku its only the evaluate method I guess.

[Fred Hamilton]

Well, I have a lot of different projects I am working on, and GoMoku isn't part of my plans right now. As for Reversi, well don't hold your breath waiting for updates from me.

This last program is something for you to work with, but it is only a GUI, there is some work to do before it becomes reversi or GoMoku, but it is a good starting point. It allows you to dynamically set the number of rows and columns, and the internal position array is set up automatically. Also you should take not of the particular values that get added to the position array. Make sure you understand exactly how it is that the black and white disks appear exactly where you click the mouse. So you see there is a lot for you to learn.

You also have a good example of negamax alphaBeta, with the tictactoe program.

I suggest as you work on your project, that you not try to do too much at once. Set your self small goals, and do lots of testing to make sure your small changes work before you move on to the next step. Good Luck

[Kabir Shah]

KK I will surely follow your advice.

[Kabir Shah]

Also it is not using much abp. So wanted it to be a gomoku game as tictactoe is solved,even a boy of 5 years can play it perfectly.. anyways as gomoku is not one of your projects, I cannot ask much. But i request you to inform me if you take up gomuko as your project.

[Kabir Shah]

Engine
GameBoard
GameTable

[Fred Hamilton]

Gurudas Bhandarkar wrote:Engine
GameBoard
GameTable

Please say the problem again, specifying eactly what game you are playing, and what you are trying to evaluate. I'm no longer sure what game you are playing

[Kabir Shah]

I am trying to expand the grid (I don't know how to change the change from string to arrays as in te tictactoe, the pStr is defined as String and then in multipurpose board, its defined in array.
so I am having difficulty in writing the engine class.)
So tried to make all the winning conditions physically available to program(i know this is not the way to program).
So as of now its to play connect 3 on 7x7board.
I kept it on for 72 mins and 18 sec, but of no use so then I stopped it.

[Fred Hamilton]

OK, as I see it, you are trying to test for a condition of N in a row. Sort of a generalized NxN tictactoe. So even though you call the program GoMoku, it is not Go Moku. Am I correct?

I think my original board representation is not the best. You will see in my Grid program I used an NxN integer array. With 1 for Black and -1 for white. Really, I think that is better than a string of x's and o's. Since you are testing for N in a row, you should be able to add up the integers for each row and column and main diagonal. and if the sum is N or -N for any of them , then it is a win.

That should not tke more than a few milliseconds to compute.

Like I said, forget my old tictactoe. Use my Grid program, the last one I posted, IMO it is a better design. You will have to add in the engine components yourself, but you can use the priginal tictactoe engine components with some modifiations, just copy them over.

see what I mean.

[Kabir Shah]

Exactly I tried to do the same but I am stuck up with the String methods.

[Fred Hamilton]

Gurudas Bhandarkar wrote:Exactly I tried to do the same but I am stuck up with the String methods.

There are no string methods in Grid. I just finished explaining why you don't need them. I saw your evaluate() method. You're doing it the hard way. I just did an evaluate on a 13x13 board using Grid, testing for the existence of 13 black or white disks in a row, It took maybe a few milliseconds to test for all possible winning conditions, and I used no string methods at all.

[Kabir Shah]

I think I didn't explain you properly in my previous post.
The thing is that I am taking some things from your engine class but then facing errors when modifying it. like how to copy the board and other things

[Fred Hamilton]

Actually your explanation is fine. The problem is you are not listening. I'll tell you one more time. Use the Grid code. I wrote the stuff, and i am telling you you are not using the Grid Code. You are using the old position representation. i can tell by looking at your evaluate method.

here it is again. there is an evaluate method in the GameTableClass. It evaluates a 13x13 board in milliseconds.

import javax.swing.*;

public class Grid extends JFrame {

	GameTable gTable;

	public Grid( String title ) {
	
		super( title );
		gTable = new GameTable();
		add( gTable );
	}
	
	public static void main( String[] args ) {
	
		Grid gFrame = new Grid("TestFrame");
		gFrame.setDefaultCloseOperation(EXIT_ON_CLOSE);
		gFrame.pack();
		gFrame.setVisible(true);
	}
}

import java.util.*;

import javax.swing.*;
import javax.swing.event.*;
import java.awt.*;
import java.awt.event.*;

public class GameTable extends JPanel implements ActionListener, ItemListener,
								MouseListener, MouseMotionListener, ChangeListener {

	GameBoard gBoard;
	JTextArea tArea;
	JSpinner spinner;
	JButton resetB, evalB;
	SpinnerNumberModel snm;
	
	int width = 400;
	int height = 500;
	int N = 3;
	
	int piece = -1;

	public GameTable() {
	
		setPreferredSize( new Dimension(width, height) );
		createGUI();
	}
	
	private void createGUI() {
	
		setLayout( new BorderLayout() );
		
		gBoard = new GameBoard( width, width, N );	// the board is square
		gBoard.addMouseListener(this);
		add( gBoard, BorderLayout.NORTH );
		
		JPanel controlPanel = new JPanel();
		add( controlPanel, BorderLayout.CENTER );
		
		resetB = new JButton("reset");
		resetB.addActionListener(this);
		controlPanel.add( resetB );
		
		evalB = new JButton("eval");
		evalB.addActionListener(this);
		controlPanel.add( evalB );
		
		Integer min = new Integer(3);
		Integer max = new Integer(13);
		Integer step = new Integer(1);
		Integer def = new Integer(3);
		snm = new SpinnerNumberModel(def, min, max, step);
		spinner = new JSpinner( snm );
		spinner.addChangeListener(this);
		controlPanel.add(spinner);
		
		
		tArea = new JTextArea();
		tArea.setPreferredSize( new Dimension( width, 50 ) );
		add( tArea, BorderLayout.SOUTH );
		
	}
	
	private int evaluate() {
	
		int sum1 = 0, sum2 = 0, sum3 = 0, sum4 = 0;
	
		for( int i=0; i<N; i++ ) {
			for( int j=0; j<N; j++ ) {
				sum1 += gBoard.posn[i][j];
				sum2 += gBoard.posn[j][i];
			}
			sum3 += gBoard.posn[i][i];
			sum4 += gBoard.posn[i][(N-1)-i];
			if( (sum1 == N) || (sum2 == N) ) return 1;
			if( (sum1 == -N) || (sum2 == -N) ) return -1;
			sum1 = 0;
			sum2 = 0;
		}
		if( (sum3 == N) || (sum4 == N) )  return 1;
		if( (sum3 == -N) || (sum4 == -N) )  return -1;
		return 0;
	}
	
	public void actionPerformed( ActionEvent e ) {
		Object o = e.getSource();
	
		if( o == resetB ) {
			gBoard.posn = new int[N][N];
			gBoard.repaint();
			tArea.setText("");
			piece = -1;
			return;
		}
		
		if( o == evalB ) {
			long t1, t2;
			t1 = (new Date()).getTime();
			int eval = evaluate();
			t2 = (new Date()).getTime();
			
			tArea.setText(" eval = " +eval +", time = " +(t2-t1) +"ms");
			return;
		}
	}
	
	public void stateChanged( ChangeEvent e ) {
	
		Object o = e.getSource();
		
		if( o == spinner ) {
		
			N = ((Integer) snm.getNumber()).intValue();
			gBoard.reset(N);
			tArea.setText("");
		}
	
	}
	
	public void itemStateChanged( ItemEvent e ) {}
	
	public void mousePressed( MouseEvent e ) {
	
	
		int x = e.getX();
		int y = e.getY();
		
		int ss = width/N;
		
		int row = y/ss;
		int col = x/ss;
		
		if( gBoard.posn[row][col] != 0 ) return;
		
		int index = N*row + col;
		
		gBoard.addPiece( row, col, piece *= -1 );
		
		tArea.setText( "row = " +row +", col = " +col +", index = " +index );
	}
	
	public void mouseReleased( MouseEvent e ) {}
	public void mouseClicked( MouseEvent e ) {}
	public void mouseEntered( MouseEvent e ) {}
	public void mouseExited( MouseEvent e ) {}
	public void mouseMoved( MouseEvent e ) {}
	public void mouseDragged( MouseEvent e ) {}
	
}

import javax.swing.*;
import java.awt.*;

public class GameBoard extends JPanel {

	int width, height;
	int[][] posn;
	int N, ss;
	int offset;

	public GameBoard( int width, int height, int numRows ) {
	
		this.width = width;
		this.height = height;
		this.N = numRows;
		this.ss = width/N;
		this.offset = ss/5;
		
		this.posn = new int[N][N];
	
		setPreferredSize( new Dimension( width, height ) );
		setBackground( Color.GREEN );
	}
	
	public void reset( int N ) {
	
		this.N = N;
		posn = new int[N][N];
		this.ss = width/N;
		this.offset = ss/5;
		repaint();
	}
	
	public void addPiece( int row, int col, int piece ) {
	
		posn[row][col] = piece;
		repaint();
	}
	
	public void paintComponent( Graphics g ) {
	
		super.paintComponent( g );
		
		int piece;
		int x,y,d;
		
		for( int i=0; i<N; i++ ) {
			g.drawLine( i*ss, 0, i*ss, height );
			g.drawLine( 0, i*ss, width, i*ss );
		}
		
		for( int i=0; i<N; i++ ) {
			for( int j=0; j<N; j++ ) {
				x = j*ss + offset;
				y = i*ss + offset;
				d = ss - 2*offset;
				piece = posn[i][j];
				if( piece == 0 ) continue;
				g.setColor( (piece==1) ? Color.BLACK : Color.WHITE );
				g.fillOval( x, y, d, d );
			}
		}
	}
}

[Kabir Shah]

Hey it was a mistake on my part as I posted the wrong code.
Actually I implemented you Grid code but the thing is I sent you the wrong code.
I am really sorry for that and hope you are not angry off by my foolish mistake.

[Fred Hamilton]

Gurudas Bhandarkar wrote:Hey it was a mistake on my part as I posted the wrong code.
Actually I implemented you Grid code but the thing is I sent you the wrong code.
I am really sorry for that and hope you are not angry off by my foolish mistake.

OK mistakes happen. I suggest you start from scratch. Using the grid code I just posted. Your next step, now that we have a proper evaluate method, is to write a possible moves method, and add a button to the GUI so you can test it. Make sure your possible moves works perfectly, before you think about negamax and alphabeta.