[chess engine programming] minimax and alpha-beta. 3-4 plies. Normal?

Hi,
I have being writing a chess engine and has just began the AI part (finished move generation and implemented all the rules). What I have implemented so far is a simple minimax with alpha-beta prunning (random ordering). The evaluation function only takes material balance into account. Boards are implemented using bitboards (simple ray-through for sliding pieces, no rotated bitboards). Currently, on ~10 seconds per move, I get 5 plies at the beginning, 3-4 in middlegame and endgame (without opening book and endgame database). Does that seem normal? To me the numbers seem pretty low, but I have no prior experience in chess programming.

Thank you very much

Quote:

Originally Posted by cyberfish

Hi,
I have being writing a chess engine and has just began the AI part (finished move generation and implemented all the rules). What I have implemented so far is a simple minimax with alpha-beta prunning (random ordering). The evaluation function only takes material balance into account. Boards are implemented using bitboards (simple ray-through for sliding pieces, no rotated bitboards). Currently, on ~10 seconds per move, I get 5 plies at the beginning, 3-4 in middlegame and endgame (without opening book and endgame database). Does that seem normal? To me the numbers seem pretty low, but I have no prior experience in chess programming.

How good or bad that depth is depends on your game playing performance. If you're only looking to 5 ply but you're kicking butt, it doesn't really matter much.

There's a complex interaction going on here. If your evaluation function is complex, then evaluating each move takes longer. But if the values are BETTER, this leads to better play, because you maximize the benefits of move ordering for alpha-beta, and you don't have to search as deep to get a reasonable estimate of the board evaluation. If your evaluation function is braindead, you should be able to search a few ply deeper -- if you're not, there's something wrong with logic elsewhere in the program.

Even a poor evaluation function can perform well, if you are able to search deep enough.

Can you give any more details about your evaluation function? Are you using a transposition table? Are you using incremental move ordering? Are you using iterative deepening?

Thank you for your reply.

Quote:

How good or bad that depth is depends on your game playing performance. If you're only looking to 5 ply but you're kicking butt, it doesn't really matter much.

Doesn't seems like that is the case. I can beat it very easily and I have a rating of ~1000 on FICS =)

Quote:

If your evaluation function is braindead, you should be able to search a few ply deeper -- if you're not, there's something wrong with logic elsewhere in the program.

That is what I thought, too, but I don't see what is wrong. The evaluation is braindead.

Quote:

Can you give any more details about your evaluation function? Are you using a transposition table? Are you using incremental move ordering? Are you using iterative deepening?

I am using iterative deepening, but results from previous depths are discarded (for now). There is currently no transposition table, or incremental move order (except I search the captures first).

here is my evaluation function -

Code:

int staticEvaluate(Board &board) { int result = 0; //BEGIN: material balance int sum = 0; for (int i = 0; i != 64; ++i) { PieceType at_type = board.getType(i); if (at_type != EMPTY) { sum += BaseValues[at_type]; } } result += sum; //END: material balance return result; }

Thank you

based on the result of gprof, it appears that my engine evaluates about 1.2 million moves per second. I guess I will just move on to implement other algorithms and optimizations.

Quote:

Originally Posted by cyberfish

based on the result of gprof, it appears that my engine evaluates about 1.2 million moves per second. I guess I will just move on to implement other algorithms and optimizations.

Move ordering, move ordering, move ordering! :) Start taking advantage of your iterative deepening. Usually this is implemented with a transposition table, but you can do it without one as well.

Quote:

Move ordering, move ordering, move ordering! Start taking advantage of your iterative deepening. Usually this is implemented with a transposition table, but you can do it without one as well.

Thank you for your suggestion =). I understand the importance of move ordering, but I just wanted to make sure that my basic implementations of minimax and alpha-beta are fine before I move on to things like transposition table. The depth it currently reaches scares me a bit though (3-4 plies in midgame with an extremely simple evaluation function).

Thank you

Quote:

about 1.2 million moves per second

hmm I think I made a mistake in interpreting gprof result. My engine is actually only searching ~30000 positions per second. I guess something is seriously wrong...

Quote:

Originally Posted by cyberfish

hmm I think I made a mistake in interpreting gprof result. My engine is actually only searching ~30000 positions per second. I guess something is seriously wrong...

Can you post the function coverage profile -- not the entire thing, just the first level table?

Quote:

Can you post the function coverage profile -- not the entire thing, just the first level table?

Thank you for your help, it's much appreciated. I am not sure what is the function coverage profile. Is it the same as the "flat profile"? Here is the flat profile section:

Code:

Flat profile: Each sample counts as 0.01 seconds. % cumulative self self total time seconds seconds calls s/call s/call name 42.55 1.29 1.29 7837472 0.00 0.00 Board::canCapture(unsigned long long) 17.88 1.83 0.54 277323 0.00 0.00 Board::generateLazyMoves() 16.72 2.33 0.51 7837494 0.00 0.00 Board::Board(Board&, Move) 11.26 2.67 0.34 80 0.00 0.04 MiniMax(Board&, int, int, int, int&) 4.64 2.81 0.14 1723099 0.00 0.00 std::vector<Move, std::allocator<Move> >::_M_insert_aux(__gnu_cxx::__normal_iterator<Move*, std::vector<Move, std::allocator<Move> > >, Move const&) 3.31 2.91 0.10 277204 0.00 0.00 Board::validateMoves_rtnBoard(std::vector<Move, std::allocator<Move> >*) 2.98 3.00 0.09 1672405 0.00 0.00 std::vector<Board, std::allocator<Board> >::_M_insert_aux(__gnu_cxx::__normal_iterator<Board*, std::vector<Board, std::allocator<Board> > >, Board const&) 0.50 3.02 0.02 17786 0.00 0.00 Board::underAtk(unsigned long long) 0.17 3.02 0.01 Board::getTypeAsArray(int*) const 0.00 3.02 0.00 131 0.00 0.00 beginsWith(char*, std::string&) 0.00 3.02 0.00 119 0.00 0.00 Board::generateMoves() 0.00 3.02 0.00 119 0.00 0.00 Board::validateMoves(std::vector<Move, std::allocator<Move> >*) 0.00 3.02 0.00 117 0.00 0.00 Board::getGameState() 0.00 3.02 0.00 8 0.00 0.00 std::vector<int, std::allocator<int> >::_M_insert_aux(__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, int const&) 0.00 3.02 0.00 2 0.00 0.00 checkClaimDraw(std::vector<Board, std::allocator<Board> >&, Move&, bool) 0.00 3.02 0.00 1 0.00 0.00 global constructors keyed to kingAtk 0.00 3.02 0.00 1 0.00 0.00 algeToMove(std::string, Board*, signed char) 0.00 3.02 0.00 1 0.00 0.00 moveToAlge(Move) 0.00 3.02 0.00 1 0.00 0.00 computeConst() 0.00 3.02 0.00 1 0.00 3.02 findBestMove(Board, int&, unsigned long, int, bool) 0.00 3.02 0.00 1 0.00 0.00 __static_initialization_and_destruction_0(int, int) 0.00 3.02 0.00 1 0.00 0.00 char* std::string::_S_construct<char*>(char*, char*, std::allocator<char> const&, std::forward_iterator_tag)

and in case it is of any use, here is the full output -
http://cyberfish.wecheer.com/gprof_out.txt

the Board::canCapture() function is a function used to determine whether the moving side can capture a particular piece. Currently, the only use of this function is in move validation (making moving into check or leaving the king in check impossible).

the Board::generateLazyMoves() function generates all legal moves but does not check whether the moves will leave the king in check.

the Board::Board(Board&, Move) constructor constructs a new board by copying an old board and applying a move.

in the profiled run, I started a new game and set the engine to play black with a time control of 5 minutes per move, and I typed in the move "e2e4", and then quit.

or, in xboard protocol:

Code:

xboard protover 2 level 40 5 0 new random usermove e2e4 quit

Thank you very much

I'm a little surprised that your board constructor(copying) takes so much time - yes it's called 8 million times, and that's certainly a lot. Are you using a loop to copy the content of the board or something like memcpy()?

--
Mats

Quote:

I'm a little surprised that your board constructor(copying) takes so much time - yes it's called 8 million times, and that's certainly a lot. Are you using a loop to copy the content of the board or something like memcpy()?

thank you for your help. I am using memcpy to copy the board (~180 bytes). My wild guess would be because the constructor is full of branching (checking for castling, en passant, promotion, see if castling availability changed etc).

[edit]
Just had a look at the constructor code, it looks pretty ugly with all the if's. I will try rewriting it and see what happens.
[/edit]

Branches are bad for modern processors, so if you can make them go away (or make them more predictable) then that's a good thing.

Copying 180 bytes * 8 million times = 1.4GB, so it will take a little bit of time... Of course, it's presumably not copying to a new location every time, so hopefully the processor cache will help some of the time at least - I take it you're not building and keeping 8 million boards, but rather creating one, checking the move and then destroying the board after evaluating the result of the move, yes?

--
Mats

Thank you for your reply.

I am currently rewriting this constructor to minimize branches, but can you please explain what do you mean by "making them more predictable"?

And I am destroying boards once they are done with. There are no more than 500 boards in memory at any time.

Well, if branches are "predictable", in other words, the branch is taken in one direction every time (or nearly all the time) then the processor will be able to "predict" the correct path to take. Unpredictable would be something like this:

Code:

char str[] = "aAbDeEcDDeCaarE"; int i, uc = 0, lc = 0; int len = strlen(str) for(i = 0; i < len; i++) { if (isupper(str[i]) uc++; else lc++; }

Since the upper/lower case letters are all scrambled in different order, the processor wouldn't be able to predict one from the other. If you sorted the string, it would have all the lower-case at one end and the upper case at the other, and thus prediction would work except for the first and the "split-point".

Not sure if you can do anything about that, tho'.

By the way, if the compiler is clever, it can do the above code without branches at all, and when I tested it, it was about 4x faster with branches eliminated compared to branches - I sent the suggestion to someone in the GCC group about 4 years back, and I has pleasantly surprised when I saw some of the suggested code when looking at the output of a gcc compiled code-snippet. I also think MS compilers do the same thing if it's feasible.

--
Mats

I see, thank you for the explanation, but I don't think I can do anything about that in my code =)

by the way, I am using gcc 4.1.3 on Linux, so I guess I am benefited by your suggestion.

Quote:

Originally Posted by cyberfish

I see, thank you for the explanation, but I don't think I can do anything about that in my code =)

by the way, I am using gcc 4.1.3 on Linux, so I guess I am benefited by your suggestion.

Quite possibly not (at least not at this point in time).

--
Mats

i have now rewritten my board constructor (and move applier) to minimize a lot of branching and be generally more efficient. Here is the new gprof data -

Code:

Flat profile: Each sample counts as 0.01 seconds. % cumulative self self total time seconds seconds calls s/call s/call name 49.43 1.29 1.29 7990387 0.00 0.00 Board::canCapture(unsigned long long) 20.31 1.82 0.53 281725 0.00 0.00 Board::generateLazyMoves() 10.73 2.10 0.28 80 0.00 0.03 MiniMax(Board&, int, int, int, int&) 7.66 2.30 0.20 7990409 0.00 0.00 Board::Board(Board&, Move&) 5.36 2.44 0.14 1752236 0.00 0.00 std::vector<Move, std::allocator<Move> >::_M_insert_aux(__gnu_cxx::__normal_iterator<Move*, std::vector<Move, std::allocator<Move> > >, Move const&) 2.68 2.51 0.07 1700863 0.00 0.00 std::vector<Board, std::allocator<Board> >::_M_insert_aux(__gnu_cxx::__normal_iterator<Board*, std::vector<Board, std::allocator<Board> > >, Board const&) 2.30 2.57 0.06 281606 0.00 0.00 Board::validateMoves_rtnBoard(std::vector<Move, std::allocator<Move> >*) 0.77 2.59 0.02 18210 0.00 0.00 Board::underAtk(unsigned long long) 0.77 2.61 0.02 Move::DEBUG_printMove() 0.00 2.61 0.00 131 0.00 0.00 beginsWith(char*, std::string&) 0.00 2.61 0.00 119 0.00 0.00 Board::generateMoves() 0.00 2.61 0.00 119 0.00 0.00 Board::validateMoves(std::vector<Move, std::allocator<Move> >*) 0.00 2.61 0.00 117 0.00 0.00 Board::getGameState() 0.00 2.61 0.00 8 0.00 0.00 std::vector<int, std::allocator<int> >::_M_insert_aux(__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, int const&) 0.00 2.61 0.00 2 0.00 0.00 checkClaimDraw(std::vector<Board, std::allocator<Board> >&, Move&, bool) 0.00 2.61 0.00 1 0.00 0.00 global constructors keyed to kingAtk 0.00 2.61 0.00 1 0.00 0.00 algeToMove(std::string, Board*, signed char) 0.00 2.61 0.00 1 0.00 0.00 moveToAlge(Move) 0.00 2.61 0.00 1 0.00 0.00 computeConst() 0.00 2.61 0.00 1 0.00 2.59 findBestMove(Board, int&, unsigned long, int, bool) 0.00 2.61 0.00 1 0.00 0.00 __static_initialization_and_destruction_0(int, int) 0.00 2.61 0.00 1 0.00 0.00 char* std::string::_S_construct<char*>(char*, char*, std::allocator<char> const&, std::forward_iterator_tag)

now the constructor is much more efficient (a little bit more than 2.5 times as fast).

the number of nodes evaluated per second now is ~43000, which roughly translates to a 4 ply search both with and without quiescent extension at the beginning in 15 seconds.

Does that number seems normal for basic minimax/alpha-beta with random ordering? I have no prior experience in chess programming so I don't know what is normal. I don't want to move on to implement other things like the transposition table and null move heuristics and then later realize that there is something fundamentally wrong in my program.

Thank you very much for all your help

I have DEEP alpha beta up to 7

hi
I write a chess program in alpha beta with c++ that go to depth 7 easily
at 2 second and the positions are completly complex
now I am trying to go to deep 8 by alpha beta
but it take so long time.
by system that os=windows xp & cpu=E2180(2G) ram=2G
It takes 105 second to go deep 8 in complex chess position's
but in usual positions it takes 30 second to go deep 8.

I just want tell that the program that you write absoltly is not optimized

tank

I just want to tell you that you are about 3 years late to the party and I have already finished and abandoned this project, about 2 years ago :).

Brainless

I am sure that your program did not go to more than 6 plies depth
by alpha beta

It's ok.

I am sure it does.

Enlighten us?

Although it's been a couple of years since you wrapped up your chess program, can you recall what was the main issue with your shallow search depth?

I'm writing a program for a different 2-player combinatorial game and getting depth 5 with minimax, alpha-beta pruning, random move order, in about 8 secs. This game has roughly 40-80 legal moves per ply, so something around 200,000 positions per sec are evaluated with a fairly complex evaluator (the evaluator is 60% of running time on a profiler).

This is in interpreted Java as well.

I'm guessing move ordering will be the next most-important optimization.

With that high a branching factor (is that real branching factor or effective branching factor?), 5 plies in 8 seconds sounds pretty good.

Move ordering is VERY important. With bad move ordering, alpha-beta won't perform much better than minimax. With perfect ordering, it will search twice as deep (square roots the branching factor). But of course, if you know the perfect ordering already, why would you need the search?

So in reality it would be something in between. You'll probably get something like 1.5x the plies you get with just minimax, if you have pretty good move ordering.

After that, at least for chess, it's mostly heuristics ("guessing" that a move will not be relevant and reduce its depth or kill it completely). There are many heuristics that can be applied, but I'm not sure if they apply to your game. Eg. in chess, if you move twice in a row, and still gets a beta cut-off (from a shallow search), we assume the move is more or less useless. Or, if you have good move ordering, you can search moves closer to the front of the list (more likely good moves) to greater depth than rest of the moves.

Basically boils down to making the tree uneven. Search less likely (to be important) nodes to shallower depth, and use the time saved to search the more promising nodes to greater depth.

Then the ply count is not so important anymore.

If you prune too much, you can get very high ply counts, but that doesn't mean anything, and can be very dangerous.

On the other hand, if you extend too much, you'll get low ply counts, but it can potentially play better.

Quote:

Originally Posted by cyberfish

With that high a branching factor (is that real branching factor or effective branching factor?), 5 plies in 8 seconds sounds pretty good.

Thanks for the reply cyberfish! I'm not sure what the difference is between real branching factor and effective. There are about 40-80 legal moves in a given early-game position. This goes down a little until move 10, after which there are 200-400 legal moves. Often games end before then, however.

My 5 plies in 8 secs is an average. With my current (poor) move ordering, I can search up to 6 million nodes to get 5 ply, and that can take as long as 30 secs.

Quote:

Move ordering is VERY important. With bad move ordering, alpha-beta won't perform much better than minimax. With perfect ordering, it will search twice as deep (square roots the branching factor). But of course, if you know the perfect ordering already, why would you need the search?

I just read Francois-Dominic Laramee's excellent tutorial on chess programming over on GameDev.net and it's motivated me to add all the basic bells and whistles used by chess programs: history table, transposition table, iterative deepening, etc. I wish I had a way to make evaluation faster, however. It's killing me.

Basically to even check for a win you have to find all paths in a sparse graph. This problem isn't even in NP. But there may be tricks I haven't thought of yet...

Quote:

After that, at least for chess, it's mostly heuristics ("guessing" that a move will not be relevant and reduce its depth or kill it completely).

Yeah, the nice thing about chess is that it's well-understood. I have good intuition (I've been rated as high as 2450 blitz, 2280 USCF... 20 years ago). Opening books are all over.

With this new game, I don't even know what a "good" position is. It's all guess-work. I may have to use some machine-learning techniques (many Othello programs do this to develop their opening books).

Quote:

Then the ply count is not so important anymore.

Since my game often ends in less than 20-24 ply, if I could get to (say) 8-10 ply I'd imagine the game would be almost unbeatable.

Anyway, thanks again for the quick and informative reply. I've just stumbled upon a wealth of resource online, so I'm going to go feed this obsession for a few days.

Btw, I'm a professor of computer science and I'll be assigning this as homework next semester. I won't expect 2nd yr C.S. students to do much beyond simple minimax with alpha-beta however. Even that is going to be very hard for them I fear.

Quote:

Thanks for the reply cyberfish! I'm not sure what the difference is between real branching factor and effective. There are about 40-80 legal moves in a given early-game position. This goes down a little until move 10, after which there are 200-400 legal moves. Often games end before then, however.

Effective branching factor is just a misnomer some people use for log(number_of_nodes_searched) / log(ply_reached). For good chess programs, it's usually 2-3, after all kinds of reductions. Meaning they search very deep and narrow.

Bad programs can't afford to do that because they have bad heuristics that will make them miss important things.

If the branching factor is that high, maybe minimax is not the best way? Another game with high branching factor is Go, and apparently minimax is pretty useless there, because it would only be able to search 2-3 plies, and will be beaten by even beginners.

Quote:

Btw, I'm a professor of computer science and I'll be assigning this as homework next semester. I won't expect 2nd yr C.S. students to do much beyond simple minimax with alpha-beta however. Even that is going to be very hard for them I fear.

Well, I wrote most of my chess program when I was in high school, without any formal training in computer science (or even programming), so I would think it's possible if students are motivated enough :). It's not incredibly strong (~2300 blitz), but that's probably due to my almost non-existent chess knowledge (I am about 1500).