Sign in to follow this  

chess AI

This topic is 4477 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I implemented a min max tree with alpha beta pruning for my chess game. Here is the source code (its not that organized):
//AlphaBetaTree.h

#include <cstdlib>
#include <ctime>
#include <utility>
#include <vector>
#include <algorithm>
#include <iostream>
#include "coord.h"
#include "chessAuxFunctions.h"

typedef std::pair<coord, coord> move;
typedef std::pair<int, move> solution;


class alphaBetaTree
{
  public:
    alphaBetaTree(const int& gen): MAX_GENERATION(gen) {std::srand(std::time(0));}
    void generateTree(const chessBoard&);
    move getBestMove() const;
    enum {MAX, MIN};

  private:
    class chessNode
    {
      public:
        chessNode(const chessBoard&, const move&, bool);
        chessNode(const chessBoard&);
        const chessBoard& getBoard() const;
      private:
        chessNode();
        chessBoard board;
        move m;
    };
   
    alphaBetaTree();
    int maxNode(chessNode node, int alpha, int beta, int generation);
    int minNode(chessNode node, int alpha, int beta, int generation);
    int chessEvaluator(const chessBoard&, bool);
    int scorePiece(chessPiece*);
    std::vector<move> generateMoves(const chessBoard&, bool);
    
    const int MAX_GENERATION;
    move bestMove;
    int rootNodeBestScore;
};

inline move alphaBetaTree::getBestMove() const
{
  return bestMove;
}

inline alphaBetaTree::chessNode::chessNode(const chessBoard& b, const move& m, bool owner): board(b)
{
  board.movePiece(m.first, m.second, owner);
}

inline alphaBetaTree::chessNode::chessNode(const chessBoard& b): board(b) { }

const chessBoard& alphaBetaTree::chessNode::getBoard() const
{
  return board;
}

std::vector<move> alphaBetaTree::generateMoves(const chessBoard& b, bool owner)
{
  std::vector<move> ret;
  for(int i = 0; i < 8; ++i)
    for(int j = 0; j < 8; ++j)
      if(b.getPiece(coord(i, j)) != 0 && b.getPiece(coord(i, j))->getOwner() == owner)
        for(int k = 0; k < 8; ++k)
          for(int l = 0; l < 8; ++l)
            if(b.threaten(coord(i, j), coord(k, l)))
              ret.push_back(std::make_pair(coord(i, j), coord(k, l)));
  return ret;
}

inline int alphaBetaTree::maxNode(alphaBetaTree::chessNode node, int alpha, int beta, int generation)
{
  std::vector<move> moves = generateMoves(node.getBoard(), MAX);

  if(generation == MAX_GENERATION || moves.size() == 0)
    return chessEvaluator(node.getBoard(), MAX);
  
  else {
    for(std::vector<move>::iterator i = moves.begin(); i != moves.end(); ++i) {
      alpha = std::max(alpha, minNode(chessNode(node.getBoard(), *i, MIN), alpha, beta, generation + 1));
      if(generation == 0 && alpha >= rootNodeBestScore) {
        if(std::rand() % 2) {
          bestMove = *i;
          rootNodeBestScore = alpha;
        }
      }
      if(alpha > beta)
	    return beta;
    }
  }
  return alpha;
}


inline int alphaBetaTree::minNode(alphaBetaTree::chessNode node, int alpha, int beta, int generation)
{
  std::vector<move> moves = generateMoves(node.getBoard(), MIN);

  if(generation == MAX_GENERATION || moves.size() == 0) 
    return chessEvaluator(node.getBoard(), MIN);
  
  
  else {
    for(std::vector<move>::iterator i = moves.begin(); i != moves.end(); ++i) {
      beta = std::min(beta, maxNode(chessNode(node.getBoard(), *i, MAX), alpha, beta, generation + 1));
      if(alpha > beta)
	    return alpha;
    }
  }
  return beta;
}

inline void alphaBetaTree::generateTree(const chessBoard& b)
{
  rootNodeBestScore = -99999999;
  maxNode(chessNode(b), -99999999, 99999999, 0);
}

inline int alphaBetaTree::chessEvaluator(const chessBoard& b, bool who)
{
  //keep track of score
  int score = 0;

  //find a piece on the board
  //use an iterator to go through board
  for(int i = 0; i < 64; ++i){
    if(b[i] != 0 && b[i]->getOwner() == who) {
      //check to see what piece *i points to and increment score accordingly
      score += scorePiece(b[i]);
    }
  }
  //check to see if the piece that *j points to is a valid piece
  //and how many points its worth if *i threatens it
  if(b.check(!who))
    score += 10;

  //check to see if the opponents king is in checkmate
  if(b.checkMate(!who))
    score += 40;

  //return score according to who it is
  //negative for who == false
  //positive for who == true
  if(who)
    return score;
  else return score*-1;
}

inline int alphaBetaTree::scorePiece(chessPiece* p)
{
  //make sure that *p is a valid piece
  if(p == 0)
    return 0;

  //get the ID of the piece
  int ID = p->getID();

  // IDs are as follows
  // 1 = pawn
  // 2 = rook
  // 3 = knight
  // 4 = bishop
  // 5 = queen
  // 6 = king

  switch(ID){
  case 1:
    return 1;
  case 2:
    return 2;
  case 3:
    return 2;
  case 4:
    return 2;
  case 5:
    return 5;
  case 6:
    return 6;
  default:
    return 0;
  }
}



Here are the times I've gotten so far with testing it:

Search Depth      Time in Seconds
1 move               0 sec
2 moves              0 sec
3 moves              11 sec
4 moves              353 sec

Are these bad times? I can't think of any move improvements to make to the algorithm. The thing I think that is slowing it down the most is all the copying it does (its copying a 64 element array of pointers and the underlying data). Does anyone have any suggestions? I will post more source code if it will be helpful.

Share this post


Link to post
Share on other sites
You could probably improve it by passing by reference and not making copies.
The generateMoves in particular could be coded to avoid instantiating a vector each time and making copies of it.

As for the times, I can't say if it is good or bad, what is your machine? Are you running it in a release or debug build?

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
One thing that I find odd in your code is the piece scoring. I'm not a chess expert, but according to a friend of mine that is fairly skilled at chess (Elo rating just over 1800), the scores should be pawn=1, rook=5, bishop=3, knight=3, and queen=9.

Share this post


Link to post
Share on other sites

Your times are bad. Of course you could be running on a 486, but I'm going to assume it's a PC running at 1.5+ GHz and your not in 'debug mode'. A three ply search should take less than 1 second.

These bad times may have nothing to do with your AlphaBeta search.

1. Try to sort your moves by captures before hand. This will increase the odds of a cut-off early on.

2. Add a killer-move heuristic. You will get a massive speed boost for 5 minutes of work.

3. What is board doing? Usually board generation is the slowest part of a chess program.

Cheers,
Will






Share this post


Link to post
Share on other sites
Quote:
Original post by RPGeezus


2. Add a killer-move heuristic. You will get a massive speed boost for 5 minutes of work.

3. What is board doing? Usually board generation is the slowest part of a chess program.

Cheers,
Will


2. Do you mean re-write my generateMoves function so it will get a list of moves quicker, or do you mean something else?
3. Thats what I think the biggest problem is. Every node of the tree has its own chessBoard to evaluate and to use to generate new moves off of.

Share this post


Link to post
Share on other sites
Generally speaking, optimizing code is not the best way to go to get a speed boost.

With Alpha-Beta, searching the 'best' move first will give you much faster results. Many optimizations are built around this.

Killer move works by trying a move that you suspect will cause a cutoff before you try any other move.

The killer move heuristic attempts to produce a cutoff by assuming that a move that produced a cutoff in another branch of the game tree at the same depth is likely to produce a cutoff in the present position, that is to say that a move that was a very good move from a different (but possibly similar) position might also be a good move in the present position. (copied from Wikipedia)

(i.e.: you move your knight to f3, I move my queen to a2, queen causes a cutoff. Similarly, if you moved a pawn d4, instead of the knight, moving my queen to f3 will likely still cause a cutoff).

It's a simple way of enhancing Alpha-beta.

There are many other techniques like this. Transposition tables, Principal Variation, etc.... There are also forward pruning techniques like Null-Move and Verified-Null-Move.

The problem with optimizing code and chess is that saving 1/2 second or a second in processing time will usually equate to 0 extra plys searched. This will not make your program any stronger.

The question you have to ask yourself is do you feel that the extra 1/2 second is worth the effort to get it...

-------

That said, if you really are concerned about your code: Don't use dynamically allocated memory, period.

If I recall correctly, at the most you will have 104 possible responses to a given move. Decide the maximum depth you want your program to search (i.e. 20 ply), and create a big array to store all of your moves. Board gBoard[20][104];



Will

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
inline int alphaBetaTree::scorePiece(chessPiece* p)
{
//make sure that *p is a valid piece
if(p == 0)
return 0;

//get the ID of the piece
int ID = p->getID();

// IDs are as follows
// 1 = pawn
// 2 = rook
// 3 = knight
// 4 = bishop
// 5 = queen
// 6 = king

switch(ID){
case 1:
return 1;
case 2:
return 2;
case 3:
return 2;
case 4:
return 2;
case 5:
return 5;
case 6:
return 6;
default:
return 0;
}
}


That can be replaced with this:

inline int alphaBetaTree::scorePiece(chessPiece* p)
{
//make sure that *p is a valid piece
if(p == 0)
return 0;

return p->getID();
}

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Ooops! Mis-read the original function, try this:
inline int alphaBetaTree::scorePiece(chessPiece* p)
{
if(p == 0)
return 0;

int ID = p->getID();

if(ID == 2 || ID == 3 || ID == 4)
return 2;
else return ID;
}

Share this post


Link to post
Share on other sites

This topic is 4477 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this