New Chess Program in Pascal

[lauriet]

Hi everyone,

Please check out my chess program source at ltchess.weebly.com.
Written in Pascal to show the main principles of a chess program.
Hopefully a good start for a newby. Its well documented and of course
being written in Pascal (the original teaching language ) it demonstrates
the algorithms clearing.

Thanks for looking. I hope it is as helpfull as it was fun and challenging to write

Laurie Tunnicliffe

[mar]

Hi and welcome to talkchess.

Just a remark: your hashtable implementation cannot work.
Also having copy-pasted code for side to move asks for bugs (have you considered negamax?).

Martin

[lauriet]

I'm all ears, please explain about the hash table stuff ?

Yes negamax is for the next program, its a little bit harder to understand because you need to do the negation and the swapping around stuff.

Regards
Laurie.

[mar]

I'm all ears, please explain about the hash table stuff ?

Yes negamax is for the next program, its a little bit harder to understand because you need to do the negation and the swapping around stuff.

Regards
Laurie.

Well you don't store bounds (or bound). This will be a problem once you switch to PVS.
Consider this: store best value (if any), also store bound type (upper, exact, lower) if score is <= alpha, > alpha and < beta and >= beta. Then when probing you can discard whole subtrees:

Code: Select all

Probe hashtable, depth >= current depth?
no => don't cutoff
yes => extract score from TT
exact bound => cutoff, return score from TT
upper bound => cutoff if TT score <= alpha, return score from TT &#40;if you use fail-soft&#41; or alpha if fail-hard&#41;
lower bound => cutoff if TT score >= beta, return score from TT &#40;if you use fail-soft&#41; or beta if fail-hard&#41;

Note that you have to be careful with mate scores from TT (usually one stores relative mate scores in TT, like add sign(score)*ply before storing and do the opposite when fetching.
Also you only do TT cutoff at depth 0 (qsearch). So your TT is basically just qsearch cache.
You could improve move ordering too by trying TT moves before others.

As for negamax, what's difficult about -search(-beta, -alpha)?

Hope it helps

[Adam Hair]

Hi Laurie,

Welcome to TalkChess. Thanks for the link to the notes about alpha/beta! However, there is a typo in the link. 'html' is spelled 'htnl' in your link.

Good luck with developing your engine.

[lauriet]

Hi Martin,
Yes of course you are correct, and my TT is a cache for the evaluation function. Thats all I wanted at this stage. It gives a student some idea of whats the TT is doing without complicating the main issue of the search.

Whats so hard about negamax.......maybe Im not too clever but when you start to draw out a sample tree and have to swap alpha and beta and negate scores I kind of loose track of what all the variables mean. Maybe if you just except it on faith that it works and dont think too hard about it, but being my first try I really wanted to understand the basic ideas, which I found easier with the mutual recursive version of the code. Its not as though the finally exe size is a problem.

Thanks for your comments, I will include them in my next program

Regards
Laurie

[mar]

Hi Martin,
Whats so hard about negamax.......maybe Im not too clever but when you start to draw out a sample tree and have to swap alpha and beta and negate scores I kind of loose track of what all the variables mean. Maybe if you just except it on faith that it works and dont think too hard about it, but being my first try I really wanted to understand the basic ideas, which I found easier with the mutual recursive version of the code. Its not as though the finally exe size is a problem.

The point is that you get much simpler code (much more readable and less error prone, easier to maintain), size of binary is not the problem here but complexity of code.
It's that you are always maximizing for the side to move, that's why you have to negate and swap bounds. I don't think it's rocket science.
Just don't forget to negate eval when it's black's turn.

Code: Select all

a = 10, b = 50
white's turn
do move
recurse (black's turn)
a = 10, b = 50, minimize (black's turn)
best a = 20 (say it comes from eval, from white's POV, qs depth 0, quiet position)
return, we get 20
raise alpha to 20, continue with next move

now negamax:
a = 10, b = 50
white's turn
do move
recurse (black's turn)
a = -50, b = -10, maximize (independent of side to move)
best a = -20 (from eval from side to move POV [=black now])
return
negate, we get 20
raise alpha to 20, continue with next move

now for black to move:

Code: Select all

a = -10, b = 20
black's turn
do move
recurse (white's turn)
a = -10, b = 20, maximize (white's turn)
best a = 13 (comes from eval, from white's POV, qs depth 0, quiet position)
return, we get 13
lower beta to 13, continue with next move
window is now -10, 13

now negamax:
a = -20, b = 10
black's turn
do move
recurse (white's turn)
a = -10, b = 20, maximize (independent of side to move)
best a = 13 (from eval from side to move POV [=white now])
return
negate, we get -13
raise alpha to -13, continue with next move
window is now -13, 10

This shows that these are equivalent but the latter doesn't require special code for white/black (unless there's a typo somewhere).

[lauriet]

Hi Martin,
Thanks for that, ill definitely do it in my next program (64 bit, bit boards etc, etc).

Maybe you could modify the search unit and we can add it to the code base.

Regards
Laurie.

[mar]

Maybe you could modify the search unit and we can add it to the code base.

Oh c'mon Laurie, it's your baby, you can do it I'm too busy with mine

Martin

[lauriet]

Well, I did mention I wasn't too bright didn't I
And you could get co-authorship cheques when the money starts to roll in.