New Chess Program in Pascal

Discussion of chess software programming and technical issues.

Moderators: Harvey Williamson, bob, hgm

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
lauriet
Posts: 197
Joined: Sun Nov 03, 2013 8:32 am
Contact:

New Chess Program in Pascal

Post by lauriet » Thu Nov 07, 2013 10:20 pm

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 :roll:) it demonstrates
the algorithms clearing.

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

Laurie Tunnicliffe :D

mar
Posts: 2185
Joined: Fri Nov 26, 2010 1:00 pm
Location: Czech Republic
Full name: Martin Sedlak

Re: New Chess Program in Pascal

Post by mar » Thu Nov 07, 2013 10:42 pm

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
Posts: 197
Joined: Sun Nov 03, 2013 8:32 am
Contact:

Re: New Chess Program in Pascal

Post by lauriet » Sun Nov 10, 2013 10:24 am

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
Posts: 2185
Joined: Fri Nov 26, 2010 1:00 pm
Location: Czech Republic
Full name: Martin Sedlak

Re: New Chess Program in Pascal

Post by mar » Sun Nov 10, 2013 10:49 am

lauriet wrote: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
Posts: 3225
Joined: Wed May 06, 2009 8:31 pm
Location: Fuquay-Varina, North Carolina

Re: New Chess Program in Pascal

Post by Adam Hair » Sun Nov 10, 2013 11:29 am

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
Posts: 197
Joined: Sun Nov 03, 2013 8:32 am
Contact:

Re: New Chess Program in Pascal

Post by lauriet » Sun Nov 10, 2013 9:03 pm

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
Posts: 2185
Joined: Fri Nov 26, 2010 1:00 pm
Location: Czech Republic
Full name: Martin Sedlak

Re: New Chess Program in Pascal

Post by mar » Sun Nov 10, 2013 10:10 pm

lauriet wrote: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 &#40;black's turn&#41;
a = 10, b = 50, minimize &#40;black's turn&#41;
best a = 20 &#40;say it comes from eval, from white's POV, qs depth 0, quiet position&#41;
return, we get 20
raise alpha to 20, continue with next move

now negamax&#58;
a = 10, b = 50
white's turn
do move
recurse &#40;black's turn&#41;
a = -50, b = -10, maximize &#40;independent of side to move&#41;
best a = -20 &#40;from eval from side to move POV &#91;=black now&#93;)
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 &#40;white's turn&#41;
a = -10, b = 20, maximize &#40;white's turn&#41;
best a = 13 &#40;comes from eval, from white's POV, qs depth 0, quiet position&#41;
return, we get 13
lower beta to 13, continue with next move
window is now -10, 13

now negamax&#58;
a = -20, b = 10
black's turn
do move
recurse &#40;white's turn&#41;
a = -10, b = 20, maximize &#40;independent of side to move&#41;
best a = 13 &#40;from eval from side to move POV &#91;=white now&#93;)
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
Posts: 197
Joined: Sun Nov 03, 2013 8:32 am
Contact:

Re: New Chess Program in Pascal

Post by lauriet » Sun Nov 10, 2013 11:19 pm

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
Posts: 2185
Joined: Fri Nov 26, 2010 1:00 pm
Location: Czech Republic
Full name: Martin Sedlak

Re: New Chess Program in Pascal

Post by mar » Tue Nov 12, 2013 8:29 am

lauriet wrote: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 :wink:

Martin

lauriet
Posts: 197
Joined: Sun Nov 03, 2013 8:32 am
Contact:

Re: New Chess Program in Pascal

Post by lauriet » Tue Nov 12, 2013 9:23 am

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

Post Reply