Hi, I am implementing chess AI. The one I am doing is AlphaBeta pruning. The problem I am having is that it takes the computer too long time to generate a move. The searching depth is now only 4. If I change it to 5, it takes more than 10 minutes to give me a move. Then I try to profile my code and the profiler says that the evaluate function is using about 70% of the total execution time. Here is my code,

int Beginner::Evaluate()
{
static short v[] [ ROWS ] [ COLS ] = 
{
// EMPTY
{
	{0,0,0, 0,0,0, 0,0,0},
	{0,0,0, 0,0,0, 0,0,0},
	{0,0,0, 0,0,0, 0,0,0},
	{0,0,0, 0,0,0, 0,0,0},
	{0,0,0, 0,0,0, 0,0,0},

	{0,0,0, 0,0,0, 0,0,0},
	{0,0,0, 0,0,0, 0,0,0},
	{0,0,0, 0,0,0, 0,0,0},
	{0,0,0, 0,0,0, 0,0,0},
	{0,0,0, 0,0,0, 0,0,0}
},

// R_JIANG
{
	{0,0,0,	30000,30000,30000, 0,0,0},
	{0,0,0, 30000,30000,30000, 0,0,0},
	{0,0,0, 30000,30000,30000, 0,0,0},
	{0,0,0, 0,0,0, 0,0,0},
	{0,0,0, 0,0,0, 0,0,0},

	{0,0,0, 0,0,0, 0,0,0},
	{0,0,0, 0,0,0, 0,0,0},
	{0,0,0, 30000,30000,30000, 0,0,0},
	{0,0,0, 30000,30000,30000, 0,0,0},
	{0,0,0, 30000,30000,30000, 0,0,0}
},

// R_JU
{
	{1500,1560,1000, 1000,1000,1000, 1000,1560,1500},
	{1000,1000,1000, 1000,1000,1000, 1000,1000,1000},
	{1000,1000,1000, 1000,1000,1000, 1000,1000,1000},
	{1000,1000,1000, 1000,1000,1000, 1000,1000,1000},
	{2000,2200,2000, 2000,2000,2000, 2000,2200,2000},

	{1000,2100,1000, 2000,1000,2000, 1000,2100,1000},
	{2100,1000,2100, 1000,2100,1000, 2100,1000,2100},
	{1000,2200,1000, 1000,1000,1000, 1000,2200,1000},
	{1000,2200,1000, 2300,1000,2300, 1000,2200,1000},
	{1000,1000,1000, 2200,1000,2200, 1000,1000,1000}
},

// R_MA
{
	{500,550,500, 500,500,500, 500,550,500},
	{500,500,500, 500,500,500, 500,500,500},
	{620,500,630, 500,500,500, 630,500,620},
	{500,500,500, 500,630,500, 500,500,500},
	{500,500,500, 640,500,640, 500,500,500},

	{500,500,500, 500,500,500, 500,500,500},
	{500,500,650, 500,500,500, 650,500,500},
	{500,500,500, 655,500,655, 500,500,500},
	{500,655,500, 500,500,500, 500,655,500},
	{500,500,500, 500,500,500, 500,500,500}
},

// R_PAO
{
	{500,500,500, 500,500,500, 500,500,500},
	{500,500,500, 500,500,500, 500,500,500},
	{500,550,500, 500,650,500, 500,550,500},
	{500,500,500, 500,500,500, 500,500,500},
	{500,560,500, 560,500,560, 500,560,500},

	{500,500,500, 500,500,500, 500,500,500},
	{500,565,500, 500,660,500, 500,565,500},
	{500,500,500, 500,500,500, 500,500,500},
	{500,500,500, 500,500,500, 500,500,500},
	{650,500,500, 500,500,500, 500,500,650}
},

// R_SHI
{
	{0,0,0,	250,0,250, 0,0,0},
	{0,0,0,   0,240,0, 0,0,0},
	{0,0,0, 200,0,200, 0,0,0},
	{0,0,0, 0,0,0, 0,0,0},
	{0,0,0, 0,0,0, 0,0,0},

	{0,0,0, 0,0,0, 0,0,0},
	{0,0,0, 0,0,0, 0,0,0},
	{0,0,0, 0,0,0, 0,0,0},
	{0,0,0, 0,0,0, 0,0,0},
	{0,0,0, 0,0,0, 0,0,0}
},

// R_XIANG
{
	{0,0,250, 0,0,0, 250,0,0},
	{0,0,0, 0,0,0, 0,0,0},
	{200,0,0, 0,240,0, 0,0,200},
	{0,0,0, 0,0,0, 0,0,0},
	{0,0,200, 0,0,0, 200,0,0},

	{0,0,0, 0,0,0, 0,0,0},
	{0,0,0, 0,0,0, 0,0,0},
	{0,0,0, 0,0,0, 0,0,0},
	{0,0,0, 0,0,0, 0,0,0},
	{0,0,0, 0,0,0, 0,0,0}
},

// R_ZU
{
	{0,0,0,	0,0,0, 0,0,0},
	{0,0,0, 0,0,0, 0,0,0},
	{0,0,0, 0,0,0, 0,0,0},
	{270,0,270, 0,270,0, 270,0,270},
	{250,0,250, 0,250,0, 250,0,250},

	{250,250,250, 250,250,250, 250,250,250},
	{250,250,250, 250,250,250, 250,250,250},
	{250,250,250, 250,250,250, 250,250,250},
	{250,250,250, 250,250,250, 250,250,250},
	{250,250,250, 250,250,250, 250,250,250}
},

// B_JIANG
{
	{0,0,0,	-30000,-30000,-30000, 0,0,0},
	{0,0,0, -30000,-30000,-30000, 0,0,0},
	{0,0,0, -30000,-30000,-30000, 0,0,0},
	{0,0,0, 0,0,0, 0,0,0},
	{0,0,0, 0,0,0, 0,0,0},

	{0,0,0, 0,0,0, 0,0,0},
	{0,0,0, 0,0,0, 0,0,0},
	{0,0,0, -30000,-30000,-30000, 0,0,0},
	{0,0,0, -30000,-30000,-30000, 0,0,0},
	{0,0,0, -30000,-30000,-30000, 0,0,0}
},

// B_JU
{
	{-1000,-1000,-1000, -2200,-1000,-2200, -1000,-1000,-1000},
	{-1000,-2200,-1000, -2300,-1000,-2300, -1000,-2200,-1000},
	{-1000,-2200,-1000, -1000,-1000,-1000, -1000,-2200,-1000},
	{-2100,-1000,-2100, -1000,-2100,-1000, -2100,-1000,-2100},
	{-1000,-2100,-1000, -2000,-1000,-2000, -1000,-2100,-1000},

	{-2000,-2200,-2000, -2000,-2000,-2000, -2000,-2200,-2000},
	{-1000,-1000,-1000, -1000,-1000,-1000, -1000,-1000,-1000},
	{-1000,-1000,-1000, -1000,-1000,-1000, -1000,-1000,-1000},
	{-1000,-1000,-1000, -1000,-1000,-1000, -1000,-1000,-1000},
	{-1500,-1560,-1000, -1000,-1000,-1000, -1000,-1000,-1560}
},

// B_MA
{
	{-500,-500,-500, -500,-500,-500, -500,-500,-500},
	{-500,-655,-500, -655,-500,-655, -500,-655,-500},
	{-500,-500,-500, -500,-655,-500, -500,-500,-500},
	{-500,-500,-650, -500,-500,-500, -650,-500,-500},
	{-500,-500,-500, -500,-500,-500, -500,-500,-500},

	{-500,-500,-500, -640,-500,-640, -500,-500,-500},
	{-500,-500,-500, -500,-500,-500, -500,-500,-500},
	{-620,-500,-630, -500,-500,-500, -630,-500,-620},
	{-500,-500,-500, -500,-500,-500, -500,-500,-500},
	{-500,-550,-500, -500,-500,-500, -500,-550,-500}
},

// B_PAO
{
	{-650,-500,-500, -500,-500,-500, -500,-500,-650},
	{-500,-500,-500, -500,-500,-500, -500,-500,-500},
	{-500,-500,-500, -500,-500,-500, -500,-500,-500},
	{-500,-565,-500, -500,-660,-500, -500,-565,-500},
	{-500,-560,-500, -500,-500,-500, -500,-560,-500},

	{-500,-500,-500, -500,-500,-500, -500,-500,-500},
	{-500,-500,-500, -500,-500,-500, -500,-500,-500},
	{-500,-550,-500, -500,-650,-500, -500,-550,-500},
	{-500,-500,-500, -500,-500,-500, -500,-500,-500},
	{-500,-500,-500, -500,-500,-500, -500,-500,-500}
},

// B_SHI
{
	{0,0,0,	0,0,0, 0,0,0},
	{0,0,0, 0,0,0, 0,0,0},
	{0,0,0, 0,0,0, 0,0,0},
	{0,0,0, 0,0,0, 0,0,0},
	{0,0,0, 0,0,0, 0,0,0},

	{0,0,0, 0,0,0, 0,0,0},
	{0,0,0, 0,0,0, 0,0,0},
	{0,0,0, -200,0,-200, 0,0,0},
	{0,0,0, 0,0,-240, 0,0,0},
	{0,0,0, -250,0,-250, 0,0,0}
},

// B_XIANG
{
	{0,0,0,	0,0,0, 0,0,0},
	{0,0,0, 0,0,0, 0,0,0},
	{0,0,0, 0,0,0, 0,0,0},
	{0,0,0, 0,0,0, 0,0,0},
	{0,0,0, 0,0,0, 0,0,0},

	{0,0,-200, 0,0,0, -200,0,0},
	{0,0,0, 0,0,0, 0,0,0},
	{-200,0,0, 0,-240,0, 0,0,-200},
	{0,0,0, 0,0,0, 0,0,0},
	{0,0,-250, 0,0,0, -250,0,0}
},

// B_ZU
{
	{-250,-250,-250, -250,-250,-250, -250,-250,-250},
	{-250,-250,-250, -250,-250,-250, -250,-250,-250},
	{-250,-250,-250, -250,-250,-250, -250,-250,-250},
	{-250,-250,-250, -250,-250,-250, -250,-250,-250},
	{-250,-250,-250, -250,-250,-250, -250,-250,-250},

	{-250,0,-250, 0,-250,0, -250,0,-250},
	{-270,0,-270, 0,-270,0, -270,0,-270},
	{0,0,0, 0,0,0, 0,0,0},
	{0,0,0, 0,0,0, 0,0,0},
	{0,0,0, 0,0,0, 0,0,0}
}
};

	int r=0;
	for( int j=0; j< ROWS; j++)
	for( int i=0; i< COLS; i++)
	{
		r += v[ b(i,j) ] [ j ] ;
	}
	return r;
}
   </pre>   

Any suggestions &#111;n how to improve?   

<SPAN CLASS=editedby>[edited by - Peter19852001 &#111;n September 12, 2003 9:01:34 AM]</SPAN>

<SPAN CLASS=editedby>[edited by - Peter19852001 &#111;n September 12, 2003 9:02:40 AM]</SPAN>   

Make your arrays global and initialize them once only.

You''re also calling a function b(i,j). Make this function inline or just retype it by hand in to your loop. You''ll save a few cycles that way.

Instead of using myArray[j] rework it so that you can say myArray[index]. Remember that myArray[j] is the equivilant to myArray. You should be able to rework that section of code so that you don''t use any multiplicatons.<br><br>Instead of saying "for i =0 to n; i++" say "for i=n to 0; i–". It''s faster to compare a value to 0. <br><br>Make sure your compiler is automatically optimizing your code. <br><br>That should speed things up a bit. <br><br>It''s normal for most of your time to be spent in evaluation and move generation. I''m not too familiar with Chinese Chess, but 10 minutes for a 5 ply search seems excessive. <br><br>You could also try using hash tables. I''ve never been able to get them to work in so far as causing a full cutoff, but I do use them to do move ordering, which can really speed things up. <br><br>On a 1.8GHz PC I can get ply 6 or 7 in under 20 seconds in regular chess, and my code isn''t even that fast (too much dynamic memory allocation).<br><br><br>Good luck,<br>Will </i>

Thanks for your reply.
The table is static, is it slower than global array?

b(i,j) is an inlined function and I hope the compiler has inlined it.

By the way, my cpu is now only 400 MHz, is 10 minutes still too slow? Any way, I will try out your suggestions.

Any other suggestions?

Having your tables as static local variables is just fine.

There are two things that you have to consider:
A=Number of nodes searched.
B=Nodes searched per second.

Of course, C=A/B is the number of seconds that the search takes. Your problem is that C is too large, and you are trying to increase B as a solution. In my experience, there is much more to be gained by decreasing A.

The most important factor is the order in which moves are considered. The performance of alpha-beta changes dramatically with move order. I have never programmed Chinese chess, but in western chess you get pretty good results by considering the move from the hash tables first (if you don''t have hash tables, ignore this), then using the killer heuristic, then all captures (capturing the largest pieces first, capturing with the smallest pieces in case of equality), then history heuristic.

You should probably look up "killer heuristic" and "history heuristic" in Google.

One more thing:

For such a simple evaluation function, you can easily consider the value of the evaluation to be part of the board description, and update it incrementally as you make/unmake moves. That should speed things up quite a bit. Also, using 16 numbers per row might make accesses to the tables faster (multiplying by 16 is easier for the processor than multiplying by 9).

Alvaro: That''s an excellent idea. I wish I had thought of it. I wouldn''t actually do the evaluation in the move generation though.

Instead of checking the approriate table(s) in your move generation phase you can set flags to determine which parts of the evaluation are neccesary to redo. The reason for this is that you may get a cutoff before evaluating every board, and you would only have wasted cycles updating a flag, and not on looping through an array.

Peter: If you get the time you should look in to using hash tables. They can be used for all kinds of different things, and can be used to speed up your search.

If you do implement any of these suggestions would you be able to post the results of your speed testing?

Best of luck,
Will

quote: Original post by RPGeezus
Alvaro: That's an excellent idea. I wish I had thought of it. I wouldn't actually do the evaluation in the move generation though.

Instead of checking the approriate table(s) in your move generation phase you can set flags to determine which parts of the evaluation are neccesary to redo. The reason for this is that you may get a cutoff before evaluating every board, and you would only have wasted cycles updating a flag, and not on looping through an array.

That's not right. The type of evaluation that he is doing is what I call a piece-square table. If you move a piece of type T from square A to square B, then

new_evaluation = old_evaluation - value[T][A] + value[T][B];

If there is a capture, substract the value of the captured piece. In any case, no looping involved.



[edited by - Alvaro on September 16, 2003 11:19:19 AM]

I see what you mean.

I ''ve changed the 2d array to 1d array and use pointer to access it linearly, but there is no great speed difference.

Also, I have changed the Evaluate() function to use pointer, now it is no longer the function using the most time. Instead, my AlphaBeta function uses the most time.

I have thought of changing the way I generate moves. The way I am using is to check each element in the 1d array and see if it is the color being considered. If it is, generate all possible moves of that piece using GenerateMove(). Then for each possible move, move it and call recursively AlphaBeta() then unmove it.

Since there are at most 16 pieces for a player, yet there are 90 possible positions on which pieces can be put, going through the array to find the pieces of one player may be a bit slow. Besides, I cannot be sure which pieces is considered first. So I am going to store pairs (piece, location on board) of pieces of a player in addition to the 1d array. In this way, I can put the frequently moved pieces in the front of this list of pairs.

What do you think of this approach?

Keeping a list of all pieces (so you don''t have to go through the entire board looking for them) is a good idea. Usually, I would implement that as separate lists for each type of piece.

int number_of_pieces_of_each_type[15];
int location_of_pieces_of_each_type[15][10]; // Adjust `10'' to the maximum number of pieces of the same type in chinese chess, which I ignore

In western chess (and I imagine the same will be true in chinese chess), it is a good idea to consider all captures first and then all non-captures. Also, at the leaves of the main alpha-beta search you want to make a capture search (or, more generally, quiescence search) to reduce horizon effects, so it is convinient to have separate functions to generate captures and non-captures.

Have you looked up "killer heuristic" and "history heuristic"?