//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 != 0 && b->getOwner() == who) {
//check to see what piece *i points to and increment score accordingly
score += scorePiece(b);
}
}
//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
chess AI
Author
I implemented a min max tree with alpha beta pruning for my chess game. Here is the source code (its not that organized):
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.
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?
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?
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.
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
Author
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.
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
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
Take a look here.
It's just one of hundreds of pages on the subject.
Don't copy the board every time: DO the move and UNDO the move upon return.
Hope it helps.
It's just one of hundreds of pages on the subject.
Don't copy the board every time: DO the move and UNDO the move upon return.
Hope it helps.
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();}
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;}This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement