Questions for the Stockfish team

[bob]

Here is the ply-1 move list as it is sorted, with the scores returned by quiesce():
move score
e5 -2
Nf6 -9
e6 -11
d6 -12
a6 -16
f5 -21
f6 -28
c5 -30
Na6 -35
c6 -41
g6 -47
d5 -51
b5 -60
a5 -64
Nc6 -66
b6 -66
h5 -78
Nh6 -82
g5 -88
h6 -98

Something seems wrong here because all the moves have a negative score.

If I understand correctly it means that if there is a move that force repetition during the search it is going to be at the top of the list because it is going to have evaluation of 0 that is better than -2 and with deep search it may encourage winning material because often the side with the advantage can force repetition.

It is more logical to have random scores of -50<eval<50 and maybe the playing strength is going to be weaker with random evaluation in the right range.

Uri

Re-read my post. In root.c, I generate the list of moves, make them one at a time, and after each move I advance to ply=2 and then do the usual:

value = -Quiesce(tree, -MATE, MATE, Flip(wtm), 2);

Quiesce() in this case finds no captures and simply returns static eval which will be between 0 and 99. But notice that "-" above which negates. So all the numbers end up negative. They don't mean a thing in this case anyway, they are simply random numbers between 0 and 99 with a minus sign in front.

I displayed that to show that there is no "logic" to the values. I played e4, and for f5, which loses a pawn+, the sort score is a random -21.

There will be no repetition moves at the top of the list because Quiesce() does not check for repetitions at all. Would make no sense since we only do captures there which can't cause a repetition. The moves are ordered completely randomly.

[bob]

> It would be frustrating to spend a lot of time writing a program and have it lose to a program with a random evaluation.

Well, I've never had a random eval. But I did have a sign error in eval - so it was scoring something + when it should be -. That is a pretty big deal.

--Jon

In 1979 we played in a human tournament in Jackson, MS. I was working on the program right up to the tournament and a last minute change caused, in a oddball case, for the score that popped back to the root to have the wrong sign. We were playing an 1800 player and uncorked one of those "Nxg6" moves with him castled kingside. He looked, and looked, and refused the recapture. We showed him after the game that taking it would have led to an easy win for him, there was no tactics. He was simply afraid of the computer. Perhaps the first "bluff move" ever played against a human by a computer. We fixed it before the next round.

[bhlangonijr]

Look at the margin array, and then remember that for skill 1 the score range is only 0-99. That dumps the futility pruning. LMR and such get their reduction plies set to zero in option.c when you enter "skill=1".

The pruning will _always_ be mistaken in lower skill levels, because alpha and beta are going to be in the range 0-100 at most, so if it did make a decision to prune or not prune (it will choose not because the pruning margins are wider than max alpha/beta values) the decision would be purely random anyway.

This is one of the most interesting threads I've ever read here.
I've found this interesting article based on the findings of Beal and Smith about "Random minimaxing":

http://www.sciencedirect.com/science?_o ... 5b467f63a0

I'll post the abstract here for those who are not really interested reading the entire article:

The effect of mobility on minimaxing of game trees with random leaf values
Abstract
Random minimaxing, introduced by Beal and Smith [ICCA J. 17 (1994) 3–9], is the process of using a random static evaluation function for scoring the leaf nodes of a full width game tree and then computing the best move using the standard minimax procedure. The experiments carried out by Beal and Smith, using random minimaxing in Chess, showed that the strength of play increases as the depth of the lookahead is increased. We investigate random minimaxing from a combinatorial point of view in an attempt to gain a better understanding of the utility of the minimax procedure and a theoretical justification for the results of Beal and Smith's experiments. The concept of domination is central to our theory. Intuitively, one move by white dominates another move when choosing the former move would give less choice for black when it is black's turn to move, and subsequently more choice for white when it is white's turn to move. We view domination as a measure of mobility and show that when one move dominates another then its probability of being chosen is higher.

We then investigate when the probability of a “good” move relative to the probability of a “bad” move increases with the depth of search. We show that there exist situations when increased depth of search is “beneficial” but that this is not always the case. Under the assumption that each move is either “good” or “bad”, we are able to state sufficient conditions to ensure that increasing the depth of search increases the strength of play of random minimaxing. If the semantics of the game under consideration match these assumptions then it is fair to say that random minimaxing appears to follow a reasonably “intelligent” strategy. In practice domination does not always occur, so it remains an open problem to find a more general measure of mobility in the absence of domination.

The article actually describes the approach used by Beal and Smith, so it may be useful for people here who couldn't access the original paper by Beal and Smith.

I've tested the idea using my own chess engine by evaluating the leaf nodes as 0.1 * MATERIAL_BALANCE + RANDOM([0..99]) which permited my chess engine not to play really bad. However using purely random numbers was a complete disaster. I have turned off every kind of pruning and reductions.

Dr Bob, doesn't it require a full-width search tree to actually occur any "Beal effect"? You are still using alpha beta in your dumbed down Crafty, right? I guess the original experiment conducted by Don Beal requires full width search trees, by using the minmax in its "pure form" - correct me if I am mistaken - which completely makes sense if we consider the stochastic nature of the approach. Otherwise, I think we are not getting any Beal effect at all...

Am I missing something?

[bob]

Look at the margin array, and then remember that for skill 1 the score range is only 0-99. That dumps the futility pruning. LMR and such get their reduction plies set to zero in option.c when you enter "skill=1".

The pruning will _always_ be mistaken in lower skill levels, because alpha and beta are going to be in the range 0-100 at most, so if it did make a decision to prune or not prune (it will choose not because the pruning margins are wider than max alpha/beta values) the decision would be purely random anyway.

This is one of the most interesting threads I've ever read here.
I've found this interesting article based on the findings of Beal and Smith about "Random minimaxing":

http://www.sciencedirect.com/science?_o ... 5b467f63a0

I'll post the abstract here for those who are not really interested reading the entire article:

The effect of mobility on minimaxing of game trees with random leaf values
Abstract
Random minimaxing, introduced by Beal and Smith [ICCA J. 17 (1994) 3–9], is the process of using a random static evaluation function for scoring the leaf nodes of a full width game tree and then computing the best move using the standard minimax procedure. The experiments carried out by Beal and Smith, using random minimaxing in Chess, showed that the strength of play increases as the depth of the lookahead is increased. We investigate random minimaxing from a combinatorial point of view in an attempt to gain a better understanding of the utility of the minimax procedure and a theoretical justification for the results of Beal and Smith's experiments. The concept of domination is central to our theory. Intuitively, one move by white dominates another move when choosing the former move would give less choice for black when it is black's turn to move, and subsequently more choice for white when it is white's turn to move. We view domination as a measure of mobility and show that when one move dominates another then its probability of being chosen is higher.

We then investigate when the probability of a “good” move relative to the probability of a “bad” move increases with the depth of search. We show that there exist situations when increased depth of search is “beneficial” but that this is not always the case. Under the assumption that each move is either “good” or “bad”, we are able to state sufficient conditions to ensure that increasing the depth of search increases the strength of play of random minimaxing. If the semantics of the game under consideration match these assumptions then it is fair to say that random minimaxing appears to follow a reasonably “intelligent” strategy. In practice domination does not always occur, so it remains an open problem to find a more general measure of mobility in the absence of domination.

The article actually describes the approach used by Beal and Smith, so it may be useful for people here who couldn't access the original paper by Beal and Smith.

I've tested the idea using my own chess engine by evaluating the leaf nodes as 0.1 * MATERIAL_BALANCE + RANDOM([0..99]) which permited my chess engine not to play really bad. However using purely random numbers was a complete disaster. I have turned off every kind of pruning and reductions.

Dr Bob, doesn't it require a full-width search tree to actually occur any "Beal effect"? You are still using alpha beta in your dumbed down Crafty, right? I guess the original experiment conducted by Don Beal requires full width search trees, by using the minmax in its "pure form" - correct me if I am mistaken - which completely makes sense if we consider the stochastic nature of the approach. Otherwise, I think we are not getting any Beal effect at all...

Am I missing something?

I am doing a normal alpha/beta search, just with no forward pruning, LMR or null-move. But when you think about purely random evaluations, this can't be a "strongly ordered game tree" because the move ordering is effectively completely random since the endpoints get random scores. I don't think you need a pure minimax although it might play a bit better since it would more closely approximate mobility.

But try crafty 22.2, skill=1 and see how it plays, it was amazing to me. 23.3 is far weaker due to the changes I made to try to fix this.

[BubbaTough]

Dr Bob, doesn't it require a full-width search tree to actually occur any "Beal effect"? You are still using alpha beta in your dumbed down Crafty, right? I guess the original experiment conducted by Don Beal requires full width search trees, by using the minmax in its "pure form" - correct me if I am mistaken - which completely makes sense if we consider the stochastic nature of the approach. Otherwise, I think we are not getting any Beal effect at all...

Am I missing something?

Alpha-beta is equivalent to mini-max in terms of the move chosen regardless of what evaluation function you use (random or otherwise). The only effect of using Alpha-beta instead of mini-max is that it calculates faster.

-Sam

[Uri Blass]

I think that the evaluation is not really random
The static evaluation is always or almost always a positive number.

If it means positive for the side to move then the program prefers white to move and not black to move.

If it means positive for white then it means that the search may encourage black to force a draw in case of seeing no mate but seeing a forced draw.

I think that if you want to test really random evaluation you need
static eval which will be between -50 and 50 and not static evaluation which will be between 0 and 99.

Uri

[AlvaroBegue]

If it means positive for white then it means that the search may encourage black to force a draw in case of seeing no mate but seeing a forced draw.

I already pointed this out, but I am afraid nobody was listening.

[Gerd Isenberg]

Dr Bob, doesn't it require a full-width search tree to actually occur any "Beal effect"? You are still using alpha beta in your dumbed down Crafty, right? I guess the original experiment conducted by Don Beal requires full width search trees, by using the minmax in its "pure form" - correct me if I am mistaken - which completely makes sense if we consider the stochastic nature of the approach. Otherwise, I think we are not getting any Beal effect at all...

Am I missing something?

Alpha-beta is equivalent to mini-max in terms of the move chosen regardless of what evaluation function you use (random or otherwise). The only effect of using Alpha-beta instead of mini-max is that it calculates faster.

-Sam

I guess not, with position independent random eval.

http://www.talkchess.com/forum/viewtopi ... 95&t=35455

[Gerd Isenberg]

If it means positive for white then it means that the search may encourage black to force a draw in case of seeing no mate but seeing a forced draw.

I already pointed this out, but I am afraid nobody was listening.

It was not only you, but Daniel, me and others as well. As Bob elaborated somewhere in this enormous thread, and "proved" by Daniel empirically, symmetric eval seems not that important as we originally thought.

I mean even without random eval search appears often counter intuitive

[Desperado]

Hi,

i just setup a plain alphaBeta searcher with the following functions.
Then i began to examine some positions of my perft collection.

"rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1",
"r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R KQkq -0 1"

it doesnt take long to realize that the qsSearch is very sensible on the
4 different types of evaluation (added the testcode at the end of my post)

a: evaltype 1 function
================

- has a average cut rate(standpat) of 50% +-10%, so moving around the 50%

b: evaltype 2 function
================

- has a very hi average cut rate(standpat) of 90%+ moving direction towards 100%

c: evaltype 3 function
================

- the worst cut rate(standpat) 10(35)% moving direction towards 0

first impressions
================

1.
well i know that making conclusions right now is not very scientific approach,
_but_ due to the effects which presents _significant_
results,differences (described above) the type "2" random evaluation seems
to have the most similar behaviour in comparison with a _normal_
evaluation concept. ("normal"=like given here as material evalution term).

2.
each of the functions should (not tested yet), have a different
_playing strength_ because they will reach _totally_ different depths
at the same time available. At the end the _sampled_ mobility
will be more accurate the deeper we go (right?), and further
will give more strength.

3.
we do not sample mobility, we are sampling "tactical_mobility" if
we use quiesence search, or not ?
maybe there is a strong correlation
between mobility and tacticalmobility. i simply dont know.
but more important then to differentiate between minimax(mm)
and alphabeta(ab), maybe to differetiate between (mm,ab) and a selective and unlimited search like qsSearch.
Or in other words, what role does qsSearch has in Beals experiments?!

so that were just confusing thoughts
and now the code...

Code: Select all

static value_t test_eval(position_t *pos)
	{
	 // 1: (-50,50)
	 return(rand()%101-50);
 
	 // 2: (0,100)
	 //return(rand()%101);

	 // 3: (-100,0)
	 //return(-(rand()%101)); //(-100,0)

	 // 4: material()
	 value_t v = valueBalanced;

	 v += pos->pieceCount[wpEnum] * 100;
	 v += pos->pieceCount[wnEnum] * 300;
	 v += pos->pieceCount[wbEnum] * 300;
	 v += pos->pieceCount[wrEnum] * 500;
	 v += pos->pieceCount[wqEnum] * 1000;
	 v -= pos->pieceCount[bpEnum] * 100;
	 v -= pos->pieceCount[bnEnum] * 300;
	 v -= pos->pieceCount[bbEnum] * 300;
	 v -= pos->pieceCount[brEnum] * 500;
	 v -= pos->pieceCount[bqEnum] * 1000;

	 return(pos->ctm==white ? v : -v);
	}

Code: Select all

static value_t test_ab(position_t *pos,
					   value_t		alpha,
					   value_t		beta,
					   ply_t		rdp,
					   ply_t		cdp)
	{
	 undo_t undo[1];
	 movestack_t mst[1];
	 move_t move;
	 int nb_legal = 0;
	 int value = valueNone;

	 //horizon
	 if(rdp < onePly) {return(test_qs(pos,alpha,beta,rdp,cdp));}

     nodes++
	 //generate all moves
	 movestack_clr(mst);
	 generate_tactic[pos->ctm](pos,mst);
	 generate_quiet[pos->ctm](pos,mst);

	 //just needed to verify legal moves
	 pos->incheck = inCheck(pos);
	 pos->pinned  = pinned(pos,pos->ctm);

	 while((move=movestack_pick(mst))!=moveNone && alpha<beta)
		{
		 if(!pseudo_is_legal(pos,move)) continue;

		 nb_legal++;
		 move_do(pos,undo,move);
		 value = -test_ab(pos,-beta,-alpha,rdp-onePly,cdp+1);
		 if(value > alpha) alpha = value;
		 move_undo(pos,undo,move);

		}

	 // mate,stalemate
	 if(nb_legal == 0)
		{
		 if(pos->incheck) return(lBound+cdp);
		 else			  return(0);
		}

	 return(alpha);
	}

Code: Select all

static value_t test_qs(position_t *pos,
					   value_t	   alpha,
					   value_t	   beta,
					   ply_t	   rdp,
					   ply_t	   cdp)
	{
	 undo_t undo[1];
	 movestack_t mst[1];
	 move_t move;
	 int value = valueNone;

	 nodes++;

	 // standpat
	 value = test_eval(pos);
	 if(value >= beta) return(beta);
	 if(value > alpha) alpha = value;

	 // generate captures,promotions
	 movestack_clr(mst);
	 generate_tactic[pos->ctm](pos,mst);

	 //just needed to verify legal moves
	 pos->incheck = inCheck(pos);
	 pos->pinned  = pinned(pos,pos->ctm);

	 while((move=movestack_pick(mst))!=moveNone && alpha<beta)
		{
		 if(!pseudo_is_legal(pos,move)) continue;

		 move_do(pos,undo,move);
		 value = -test_ab(pos,-beta,-alpha,rdp-onePly,cdp+1);
		 if(value > alpha) alpha = value;
		 move_undo(pos,undo,move);

		}

	 return(alpha);
	}

if i have missed sth. totally, pls let me know.

Michael