Next steps for my engine?

[Evert]

Under the old method, it was my search function that was dealing with checkmate. It did this by virtue of the fact that checkmate positions were being searched and finding no legal moves, therefore the initial seed value of best=-10000 was being undisturbed. Esthetically this appealed to me as a way of making extra use of my search function. The operative word here is efficiency. Now if we accept for the purpose of discussion that my old method of checkmate is ok, then the search function I posted a little earlier was incomplete because there was no mechanism to distinguish between checkmate and stalemate, a mechanism that would not have been necessary anyway if I had been dealing with mate in my eval().

I can't say exactly how, but intuitively I think proper alpha-beta cutoffs are interfering with this. By changing things so that checkmate is handled by my eval() function, and thus a score is explicitly assigned to mate, I feel the impasse we find ourselves at will be resolved.

make sense?

Not sure.
I detect checkmate and stalemate in my search function. I have a pseudo-legal move generator that doesn't filter out all moves that leave/put the own king in check (it filters out some of the obvious ones though), so I check whether each move is legal after making it.
Initially, I have

Code: Select all

   generate_moves(&movelist, game->board, player);
   legal_moves = movelist.num_moves;

Then when making a move

Code: Select all

      playmove(game, move );
      if (player_in_check(game, player)) { /* Illegal move! */
         legal_moves--;
         takeback(game);
         continue;
      }

and after going through the move list, I do

Code: Select all

   if (legal_moves == 0) {
      if (game->board->in_check) {
         best_score = -CHECKMATE;
      } else {
         best_score = 0;
      }
   }

and I return best_score.

If you're doing something similar in your search, then you should be fine (beware: I have some extra code (one or two lines) to distinguish between different mate values in the search; with only the code posted here the engine cannot tell mate-in-one from mate-in-ten, say, which looks sloppy at best and leads to draw by 50-moves rule at worst).

[Fguy64]

duly noted Evert. I am not sure either. I can't say that my algorithm is equivalent to yours in the way mate is identified.

I can tell you that there is no pseudo in my move generation. By that I mean that any node that gets searched arises from a legal move, and all legal moves get searched to some extent, except for those that come after a move that leads to mate.

My code doesn't distinguish between mate in 5 or mate in 1. If a node that leads to mate in 5 comes before a node that leads to mate in 1, then the mate in 5 move gets played. That will probably change in the future, but for the moment it's good enough. But anyways, I think that is not relevant to the issue I raised.

Anyways, I'm just gonna try it. It's small thing to put a mate check in my eval() function. If it solves the problem then I at least know I am on the right track

[Evert]

I can tell you that there is no pseudo in my move generation. By that I mean that any node that gets searched arises from a legal move,

Of course, but you don't need a legal move generator for that.
If you have one though, that's cool. Mine still generates some moves that are illegal (moves that expose the king to check mainly; I don't keep track of pinned pieces), so I have to filter those out before searching a position. I know some people just search each node and return a mate score for capturing the king (meaning the last move was illegal) but I don't (I'd imagine that's quite a bit slower than explicitly checking for check [no pun intended]).
But if your move generator takes care of all of this already, then it becomes a lot easier to detect mate, of course.

and all legal moves get searched to some extent, except for those that come after a move that leads to mate.

Ah. Unless you're trying to make a mate-solver, you're probably wasting quite a bit of time doing this. Most good moves don't lead to mate, at least not in the foreseeable future. They just win material (usually a more tenable short-term goal).
Well, I guess that's what the discussion on search algorithms is about.

My code doesn't distinguish between mate in 5 or mate in 1. If a node that leads to mate in 5 comes before a node that leads to mate in 1, then the mate in 5 move gets played. That will probably change in the future, but for the moment it's good enough.

Sure. One step at a time.

But anyways, I think that is not relevant to the issue I raised.

It's not. Just pointing out what would might seem like an obvious flaw in the code I posted.

Anyways, I'm just gonna try it. It's small thing to put a mate check in my eval() function. If it solves the problem then I at least know I am on the right track

Ok. Good luck!

[Fguy64]

...

and all legal moves get searched to some extent, except for those that come after a move that leads to mate.

Ah. Unless you're trying to make a mate-solver, you're probably wasting quite a bit of time doing this. Most good moves don't lead to mate, at least not in the foreseeable future. They just win material (usually a more tenable short-term goal).
Well, I guess that's what the discussion on search algorithms is about.

...

I'm aware of some of those kinds of issues. I'll just add that I'm not really an advanced programmer. I started this project a year or two ago just as a way to make learning java fun. So in order to make progress I had to make some compromises that a real chess programmer would never make, just to make things a little more intuitive for a guy whose chess is a lot better than his programming.



Anyways, to the rest of the people who have helped me, I think I have as much information as I can deal with for now. Like I said, It's time for me to try to put into practice some of the ideas here. So I'm gonna put the cart before the horse for a while and see how it goes. For sure I'll let you know when I have more questions, or a solution.

[Fguy64]

The beat goes on. Sigh. I appreciate everyone's patience. OK, I'm trying this from a slightly different angle. I've written another engine class, as small as possible. This is it in its entirety, except for move generation, which is in another class. I've tried to follow Bruce Moreland's model as closely as possible. I've been focusing on the WAC positions, and Reinfeld's 1001 checkmates.
The algorithm works with checkmaye combinations very nicely, but is out to lunch on material advantage,

Only one question, and I think I have it covered. Moreland's alphaBeta function returns an eval (alpha), so it must be there there is another non-recursive "root-search" which determines available moves, then iterates through the list evaluating each move recursively by calling alphaBeta for each possible engine move.

anyways, I have not attempted to deal with what happens if the engine loses. This is just for WAC positions, as long as they don't involve the possibility of stalemate or promotion. Like I say, forced mate is handled fine, material advantage is mishandled, and I really have no idea why. If need be, I can provide for test positions a list of legal moves along with the eval for each. Once I get this part working, then I'll deal with promotion and computer losing.

anyways, here's Moreland's alphabeta page
http://web.archive.org/web/200404200223 ... habeta.htm

and here's my engine class. I'm led to understand it is an example of "fail-hard" alphabeta.

Code: Select all

import java.util.*;

public class Engine4 {

	private static Random rand = new Random();

	Output output;
	int ply;
	boolean think = false;
	boolean diagnostics = false;
	
	public Engine4( int ply ) {
		this.ply = ply;
	}

	public Engine4( Output output, int ply ) {
		this.output = output;
		this.ply = ply;
	}
	
/*********************************************************************************/
	
	public Move getBestMove( String pStr ) {
	
		CMove[] list1 = possibleMoves(pStr);
		
		int alpha = -10000;
		int beta = 10000;
		
		for( CMove cm : list1 ) {
		
			if( diagnostics ) output.append( Utils.longAlg( cm.i, cm.j ) );

			cm.eval = -alphaBeta( cm.pStr, ply-1, -beta, -alpha );
			if( cm.eval > alpha ) alpha = cm.eval;
			
			if( diagnostics ) output.append( "  " +cm.eval +"\n" );
			
			if( cm.eval == 10000 ) {
				ply -=2;
				return new Move( pStr.charAt(cm.i), cm, "forced mate");
			}
		}
		
		ArrayList<CMove> list2 = new ArrayList<CMove>();
		
		// extract the moves whose eval == maximum
		for( CMove cm : list1 ) {
			if( cm.eval == alpha ) list2.add(cm);
		}
			
		// select randomly from the list of moves that have the maximum eval.
		int select = rand.nextInt( list2.size() );
		CMove cm = list2.get(select);
		Move m = new Move( pStr.charAt(cm.i), cm, "normal");

		return m;
	}
	
/*********************************************************************************/
	
	private int alphaBeta( String pStr, int depth, int alpha, int beta ) {
	
		if( depth == 0 ) return evaluate( pStr );
	
		int best = -10000;
		int val;
		int i,j;
		String p1Str;

		boolean white = pStr.charAt(64) == 'w';
		int[][] candidates = Utils.getCandidates( pStr );
		
		for( int m=0; m<candidates.length; m++ ) {

			i = candidates[m][0];
			j = candidates[m][1];
			
			p1Str = Utils.checkMove( pStr, i, j );
			if( p1Str.equals("false") ) continue;
			
			val = -alphaBeta( p1Str, depth-1, -beta, -alpha );
			if( val >= beta ) return beta;
			if( val > alpha ) alpha = val;
		}
		
		return alpha;
	}

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

// a non-recursive method which returns a list of legal CMove objects.

CMove[] possibleMoves( String pStr ) {

	ArrayList<CMove> mList = new ArrayList<CMove>(40);
	CMove cm;
	String p1Str;
	int i, j;
	boolean promoFlag;
	
	boolean white = ( pStr.charAt(64) == 'w' );
	int[][] cand = Utils.getCandidates( pStr );
	
	for( int m=0; m<cand.length; m++ ) {
	
		i = cand[m][0];
		j = cand[m][1];
		
		p1Str = Utils.checkMove( pStr, i, j );
		if( p1Str.equals("false") ) continue;

		mList.add( new CMove(i, j, p1Str) );

	}
	
	return mList.toArray( new CMove[mList.size()] );
}

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

// the method for material evaluation of the position.
public int evaluate( String pStr ) {

	int wmat = 0, bmat = 0;
	char p;
	
	for( int i=0; i<64; i++ ) {
	
		p = pStr.charAt(i);
		if( p == '1' ) continue;
		
		switch(p) {

			case 'p':	bmat += 10; break;
			case 'P':	wmat += 10;	break;
			case 'r':	bmat += 50;	break;
			case 'R':	wmat += 50;	break;
			case 'n':	bmat += 25; break;
			case 'N':	wmat += 25; break;
			case 'b':	bmat += 30; break;
			case 'B':	wmat += 30; break;
			case 'q':	bmat += 90; break;
			case 'Q':	wmat += 90; break;
		}
	}
	
	return ( pStr.charAt(64) == 'w' ) ? ( bmat - wmat ) : ( wmat - bmat );
}

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

}

[plattyaj]

One problem, though I don't see why it causes your "material gain" problem is that you aren't handling the case of 0 legal moves. In fact I don't know how you are finding mate at all unless I missed something.

Code: Select all

if  (m<cand.length == 0)
{
   // Must be mate or stalemate. See if we're in check and return
   // a MATE score or 0
}

Andy.

[Fguy64]

One problem, though I don't see why it causes your "material gain" problem is that you aren't handling the case of 0 legal moves. In fact I don't know how you are finding mate at all unless I missed something.

Code: Select all

if  (m<cand.length == 0)
{
   // Must be mate or stalemate. See if we're in check and return
   // a MATE score or 0
}

Andy.

As I see it, in alphaBeta(), if candidates.length ==0, then the loop is bypassed and alpha gets returned undisturbed. Now I thought there might be a problem with returning the same variable that was passed, so I added a line alpha1=alpha; then changed all occurrences of alpha to alpha1 within the alphaBeta method, but it made no difference.

for example, in this position from WAC, my engine would not play Rg3

5rk1/1ppb3p/p1pb4/6q1/3P1p1r/2P1R2P/PP1BQ1P1/5RKN w - -

Anyways, I don't really understand exactly what I did. Did you compare it to the algorithm in the link I provided? I don't know what to say except that it solved at least half a dozen forced mates with no failures. If you PM me your email, I'll send you the entire source and you can see for yourself, if you have a java 6 compiler that is.

p.s. I described in my original post that the code won't distinguish between mate and stalemate.

[Evert]

I don't really understand your code... in your alpha-beta, where do you unmake a move after the recursive call?

for example, in this position from WAC, my engine would not play Rg3

5rk1/1ppb3p/p1pb4/6q1/3P1p1r/2P1R2P/PP1BQ1P1/5RKN w - -

One obvious thing to check is whether your evaluation function is working correctly. Try loading in a position where you know the score (white is a piece down, say), then print out the evaluation score and see whether it agrees with what you think it should be doing (I didn't look at your code in enough detail to see what's going on in your evaluation function; I also don't know Java specifically). Then see whether your program will correctly capture undefended pieces using another test position, whether it will make the best capture if there are more to choose from, etc. A two-three ply search in a simple position is easy enough to follow by eye.
When writing a chess program, you want to test every component very carefully and thoroughly. If one of them has a small bug, it'll throw everything else off too.

I don't know what to say except that it solved at least half a dozen forced mates with no failures.

Forced mates are actually bad test positions, I'm afraid. It's very cool when your engine finds its first mate-in-N, but they don't really help you test things like the evaluation or even the search algorithm very well.

[Fguy64]

I don't really understand your code... in your alpha-beta, where do you unmake a move after the recursive call?
....

It's late, I'll just respond to this point.

I have my getBestMove() function which is like a root search. It builds a list of move objects, each objects stores it's own position. alphabeta is called for ach move in the list

in the alphaBeta(), when checkMove() is called, if the move is legal it returns the new position (p1Str). without overwriting the old one(pStr). p1Str is sent up the tree, the old position is still stored, to be used to check the next candidate in the loop

So there is no need to undo move, cause what I am doing i essentially making a copy of the old one using it, then discarding it

perhaps it's a little odd, but it does work, my original algorithm which worked perfectly used the exact same idea. Of course the old algorithm, which was negamax, was not expressed conventionally at all, and the pruning wasn't really full alpha-beta, which is why I am going through all this.

anyways, I'm missing something fundamental, just not sure what. Don't break your head on this last post unless you really want to, I'm gonna step back and re-evaluate, again.

[nevatre]

in your static eval you have

return ( pStr.charAt(64) == 'w' ) ? ( bmat - wmat ) : ( wmat - bmat );

if the condition "pStr.charAt(64) == 'w'" means white is to move in that position then you should return the score from whites point of view, that is "wmat - bmat" not "bmat - wmat".