Sign in to follow this  

good chess hueristics

This topic is 4800 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hey i have an alpha beta search implemented but i'm trying to fugure out some good hueristics to base my board evatuation on. right now i do the following: just sum up the pieces on the board against the opponents pieces. pawns=10 knights=30 bishops=30 rooks = 50 queens=80 additionally i check for check check = 100 check mate = 200 so what else should i base board evatuation on? thanks for your help

Share this post


Link to post
Share on other sites
Add a filter to the board, with +1 Modifiers for squares you control, and a -1 Modifier for squares the opponent controls.

Try to detect squares occupied by your pieces which have a negative rating (are under attack by the opponent).

Add a filter to detect forked attacks, etc, etc, etc...

Share this post


Link to post
Share on other sites
1st. Check mate should = Infinity
2nd. You should modify use your move generator function for a few "extras", which work quite well.
Things like:
Attacks (when it could take another piece)- +Valueofpiecetobeattacked * locationmodifyer +Constant
Defends (when one of your pieces is "Attacking" of of your own pieces) - +Valueofpiecetobedefended * locationmodifyer + Constant
Mobility (How many moves does this piece have?) - +Constant * amountofmoves
Open files/open diagonals (files/diagonals that are fully open ot allow movement) - +Constant * ((numberofpiecesihavethatcanuseit - numberofpiecesopponanthasthatcanuseit) + constant)
Vonrablesides (like a rook beinga ttacked by a diagonal, that sort of thing) - -Constant * valueofpiece


+ the "normal" things like castlingrights, ect.

You should probably have two (or more) differemnt evaluation functions: One that is very fast (for the leaves), and other, slower ones for different parts of the tree (for culling, ect.)

Also, be shore to use bitboards, they make doing this stuff a lot faster. Hash tables also come in handy (esp. at endgames, they can speed up your search *a lot*)

Also remember that speed is not critical, if you can clip off a few extra leaves per node, then you will end up winning in the end. (remember, making your eval fast is good, but making a lot of cut-offs gives you expponential savings).

If your up to it, you might be able to recognise patterns in the pieces. alhough this isn't used widly, you could do this up to the 2nd-3rd ply without too many speed troubles...

Baybe do an influence map? (it would only have to be partially modified per turn, not tatally rebuilt). You could have an influence of attacking/defending squares. You could then single out your opponents "weak" squares, and increase the value of any attacks on them.

And, if you wanted to be real origional, you could add a tactical engine. in that you would have objectives (capture the king, capture the queen, take pieces, pin king in top half of the board,promote pawn, ect.), then you would (like in a rule-based system), expand outward.
For egsample:
Objective 1: capture the king.
Perform quick n' dirty search for any opossible moves which connect capturing the king to the current position.
if none, then move to objective 2
objective 2:
Do a quick search on how you could capture the queen, using transposition tables so you can use the same nodes used on objective 1.
ect.

Or: you could add an extra eval function for the objectives...

or you could add a tree of objectives, and eval the lowest ones. eg:
Capture the king:
Make king vonrable: [
take all pieces defending the king: Capture all of{getdefencivepieces("Blackking)}
Restrict king movement: lower {getmovementvalueof("Blackking") if not 1 ] [setflag("Blackkingvon")]
Attack king [{attack("Blackking", 100)} if isflag("Blackkingvon")

With this, you can program your program with some basic tactical thinking (with planing (by flags and objectives), ect.) But it hasn't been done before (so it would be hard, or it might just not work... You would probably use this to augment your usual eval(s) (perhaps only if triggers are met, such as a weakened square is taken, or a piece is taken, or something big happend the move before, ect.))

From,
Nice coder

[Edited by - Nice Coder on October 10, 2004 4:16:33 AM]

Share this post


Link to post
Share on other sites
If you haven't already put significant work into improving your move ordering, I would use a simple piece-square-table evaluation until you have very good move ordering. Otherwise the search depth won't be deep enough to make the evaluation improvements significant.

Share this post


Link to post
Share on other sites
Thought of a few more.

In the beginning of the game:
Grab control of the center (as just stated)
Develop pieces
Castle

In the middle of the game:
Develop more, and try to double up the rooks on a empty row or file.
If a certain player is winning, that player tries to trade down peices as fast as possible so the advantage is more distinct.
If the player is losing, he tries to not trade peices at all, and tries to win back the edge by forks and pins. (which are more likely to happen with more pieces on the board)

In the end of the game
Be sure the computer is well-versed in how to win in a King and pawn versus King scenario, which will in turn and to a King and Queen versus King scenario. (Also a King and rook versus King)

Share this post


Link to post
Share on other sites
1. Have a good endgame engine (which would be a trained eval function/search which kicks in at endgame. if you cannot do that, then make sure that your engine works well in the endgame).

2. If your ahead/not too far behind, take any and all oppertunities to trade off (computers are better with fewer pieces, because they can search further, while scanning the same amount of nodes. this improved playing would make up for the trade off, maybe up until there is only N number of pieces left?)

3. Find defencive/offencive "clusters" of pieces. something like:

p|p|p
.|k|R

Would be a defencive structure, it is defending these squares

D|D|D|D
p|p|p|*
.|k|R|D|D|D|D|D

But, the rook itself is vonrable on the diagonal where the * is
the pawn closest to the side of be board is also vonrable, because it can cause checkmate if two pieces are aligned on that file.

Replacing d's with a defencive margin (amount of possible attack vectors vs. defendinces), eq.

1|2|1|1
1|1|2|0
1|1|1|1|1|1|1|1|

now, if we were to move pwn a2-a3, then the layout would be this:

.|D
p|*
.|p|p
.|k|r|d|d|d|d

We now look at the resulting picture, to look at how the situation is summed up:

0|1
1|1
1|1|2
1|1|1|1|1|1|1

now, what if we were to go, a2-a4, b2-b3?

then it would be:

.|D
p|.|D
.|p|.|D
.|.|p
.|k|R

This would be
0|1
1|0|1
0|1|0|1
0|0|2
0|1|1

as such, the rook is still vonrable (no piece blocking a bishop coming in and taking it, this wouldn't matter much if that bishop was already taken though.)

so, we also need additional parameters for scoring, such as piece mobility, vonrability, defencive squares, offencive squares, value of defended squares, value of offended squares, structures in, value of structires in, and maybe a few more.

This is as much as i can think off at present.
From,
Nice coder

Share this post


Link to post
Share on other sites
Just my little share of advice, although not much into heuristics...

Try to use some sort of an oppening book. One thing that really anoyes me on some chess programs ppl make is to have to wait for 15 mins for the black pieces to respond to normal oppening moves like 1.d4 or 1.e5.

A check in wich the opponent *has* to move is king should, generally, be more rated than a normal check. More into it, a check in wich the opponent *has* to move is king and loose the previledge of castling should worth even more.

Avoid putting a knight on the edge of the board [this is vey famous] and a knight on the corner is a no-no.

The problem with most chess rules is that there are always cases of exception, being hard to discover a hammer that suits all nails. Planning strikes me as very appealing because in most of the times in "normal chess games", players are more concern with "small" objectives such as inflicting doubled pawns or putting a knight on a advanced square where it can't be chased by pawns or just simply "improving the position". Of course that implementing this is a different story.

Share this post


Link to post
Share on other sites
A few tidbits:

First and foremost: Unless you implement some form of quescence search your program will not play well-- adding every evalation under the sun will not change this. This is because your program will be constantly chasing, or evading, non existant captures (depending on it's search depth); Quescence will mostly fix this.

Secondly: The reason we implment these smaller rules is so the computer will have something intelligent to do when there are no zero-sum or advantageous captures present, which is most of the time.

Here are a few rules you might find useful.

1. Discourage early queen movment
Heavily penalize the computer for moving out it's queen early.
Do not penalize the human for moving out it's queen early.

By early I mean sometime within the first n moves, or before n pieces have been captured.

2. Make the two 'edge' pawns of the computer worth less than normal pawns, but NOT for the human-- keep his pawn values the same.

3. Early king movement
Penalize a king for moving early. (both human and computer)

4. Encourage advance pawns.

5. Know when you're in a winnable end game situation, and score it higher and/or switch to a different eval function. There are lists of winnable end games. You don't need to know how to win, just that you can.

6. Reward pieces for attacking the squares next to the enemy king.

7. Strongly encourage the computer to get it's knights and at least one bishop out early in the game. Do NOT penalize the human if they do not. After the first n moves, or a certain number of pieces have been captured, stop caring so much about having knights and bishops in key locations.

8. Encourage safe kings-- a safe king is one without open columns on it's neighbouring left and right squares, and of course the square it's on. Only turn this rule on after a certain number of moves so as not to discourage development. Turn this rule off in the end game. This rule applies for humans and computers.

9. Encourage positions where there are no queens. Queens eat processing power for computers, but not for humans.

10. Piece values should change during the course of the game. At the very beginning of the game (moves 1 through 5?) your knights and bishops should be of equal value. After that, bishops should be more valuable than the knights, but ONLY if you have both bishops, otherwise bishops are the same as knights. I had a link (somewhere) to a study of 200,000 GM games in which the author had statisically generated the piece values under many different cirumstances.. Unfortunately I can't find it anymore.

11. I don't see any good reason to encourage checks. If a check is usefull, the computer will see it anyway, otherwise why waste the move?

Some of you may be wondering why I've instructed the computer to not care about certain human situations. This is so that the computer will ALWAYS try to develop.

If the human and computer are in equally poor positions, then the evaluation's result could be identical to a situation where both players are in equally good positions. Humans are much better at long term planning, so rather than assume both situations are equal (since in reality they problaby are not), we always want the computer to go for the development that looks best for itself, not what looks best relative to the human opponent.

The queen rules in specific I've found to work well-- if a human brings out a queen early, they're unlikely to start chasing pieces all over the board. If a computer brings out a queen early, it's quite likely it will start chasing pieces all over the board.


Good luck,
Will

[Edited by - RPGeezus on October 18, 2004 12:54:38 PM]

Share this post


Link to post
Share on other sites
Try to have a bonus for protection of pieces (like a bishop-pawn combo).

You hsould also have a bonus for thnigs like attacking 2 or more pieces (bonus++ if they are pawns). Same goes for squares. Controlling the *other side* of the board is also quite nice to do (things like get a rook on 8, it makes things so much easier.)

Maybe some sort of "checkmate solver" could come in handy. Every time on of the marked pieces moves (or the king moves), the board is resolved, to figure out which pieces to kill to cause a checkmate.

It would be more advanced then that, maybe looking at which squares are vonrable and which squares (which may or may not be occupied) should be taken to cut down on the possible moves of the king (for eg. if you were to take pawn p5, then you would get ahead.

p1|p2|p3|p4|p5
..|..|.K|..|..

p1|p2|p3|p4|b1
..|.K|..|..|..

You have now trapped the king, another bishop on p4 would also be nice. a rook on p4 could prove fatal for your opponant. What yo uneed is some sort of coefficient to figure out how good that square is, compared to the effort of getting there.

Now if, in order to take that square (if it was a really good square, like the one right on top of the king, or a row which cannot be blocked by a piece (eg. you have one rook, and your opponant has none).),
you had to take a piece, you would do hte same thing with that piece, look for the vectores needed to take it.
check all avalible pieces, and compute the reward/effort coefficient in taking that piece. you would then multiply it with how much that piece is worth.
if in order to take that piece, you need to take another piece, repeat.

This might make a nice little side-project.

From,
Nice coder

Share this post


Link to post
Share on other sites
great thanks for the input guys! now i've implemented some of the rules u mentioned but when its near the end of the game the ai has a problem with sticking with a plan. For instance when only the white king is left and a black king, queen and rook are left, it's fighting between several different check mates (its selecting a different move seqence every time it makes a move (cause the white king shits positions at each move). any ideas? thanks

Share this post


Link to post
Share on other sites
How are you handling checkmates score? Make 'nearer' checkmates (checkmates that happen in fewer moves) more valuable than checkmates that happen in more moves.

This way it sould always stick to the same path to mate.

Will

Share this post


Link to post
Share on other sites
Perhaps have some sort of inersea, and distance to completion, change the persieved havue of a plan. the inersia would stop it from wanting to try a different plan every turn.

from,
Nice coder

Share this post


Link to post
Share on other sites
I had never coded any chess engine so far, but from my expirience as a chess player, where I tried to do lots of chess training, I would like to add some hints for your engine:

In middle and end games there is a rules that tells that healty games have ALL pieces moving from time to time. This rule is not meant to be used exactly, excludes pawns (mostly), but tells a lot about game quality. If only few pieces are moving within any time windows (# of plys), famous games show generally that there is already an advantage or poor play in progress. So if you have that situation and there is no advantage for any side, you might look more for other pieces first that could make usefull moves, than for the few pieces that have already moved a lot. In endgames there should not be any ONLY MOVING piece as long as there is not only the king left, or there is a great advantage (forced moves) for one side and this for perhaps no winning possiblility any more, because of lack of tempi.

Try to weight material dynamically. Pieces that moved in the very past have some temporary higher value and a lower exchange value (the might gain for piece exchange).

If there is only one bishop left for one side, DO NOT count it equal to a knight, since one knight can go any square, but a bishop only half the squares on the board for the rest of the game. Single bishops are often overestimated from chess engines at this point and lead to strategic fail. If material values is equal but one side has 2 bishops and the other only one, there is an potential advantage for the two bishops even with closed diagonal lines, since the opponent might open them for gaining the advantage in reality.

Do not forget to do not cut to early for pieces that have moved at the latest plys. They have a large dynimic value and might even exchange pieces with much less value (sacrifice) to gain advantage. So you should look more into deepth for all possible moves for them.
Below is a chess game played via email, where I had expected my oponent to use a chess engine (what was not forbidden at all). The oponents engine did not expect a queens sacrifice and for this did not search deep enough into this variant. I had checked this for the most common chess engines (fritz7/8, shredder6, nimzo, hiarcs8) and they all failed for expecting 18...Qd1+ in the 17. move and for realizing the resulting disadvantage from the kings little space left and the following forced moves.
This game shows very well the typical weakness of todays chess engines, ignoring dynamic value of a lately moved pieces:

[Event "CC-2003-0-00054"]
[Site "IECG"]
[Date "2003.01.26"]
[Round "1"]
[White "Delooz, Philippe"]
[Black "Gruber, Sebastian Andreas"]
[Result "0-1"]

1.e4 d5 2.exd5 Qxd5 3.Nc3 Qa5 4.d4 Nf6 5.Nf3 Bf5 6.Bc4 e6 7.Bd2 c6 8.Ne4 Qc7 9.Nxf6+ gxf6 10.Nh4 Bg6 11.f4 f5 12.Qf3 Nd7 13.Qc3 Be7 14.Nf3 Bh5 15.Ne5 0-0-0 16.Qh3 Nxe5 17.dxe5 Qd7 18.Bc3 Qd1+ 19.Rxd1 Rxd1+ 20.Kf2 Bc5+ 21.Kg3 Rg8+ 22.Kh4 Rxh1 23.Kxh5 Bg1 24.Kh6 Rxh2 25.Bf1 Rxh3+ 26.gxh3 Be3 27.Kxh7 Rg1 28.Be2 Bxf4 29.h4 Bxe5 30.Bxe5 Re1 31.Bc4 Rxe5 32.h5 f4 33.h6 Rg5 34.Bd3 f3 0-1

By the way, most engines rate the white play with little advantage, while white mostly moves repetitive 1 knight and the queen most the time... which is absolte crap!

But you should have a sacrifices search anyway, no matter of piece was moved or not...!!!

You might also have dynamic values for squares related to be being moved at or from within some time window (plys). Mostly those squares are very important for the upcoming moves, especially when located on the oponents side of the board of course. So all pieces that can claim such squares are becoming more important and should be searched heavier (deeper). This is much more important than simply building sums over controlled squares, because lots of them are unimportant to the strategic and tactic aspects of a game.

All in all the dynamic part of games is not solved very well even with the right now strongest chess engines. Even an average human player, like me, with support of a analytic chess engine, will always win against any of the so called strongest chess engines right now. And static evaluation functions will prevent from loosing pieces for nothing, but the make no good game play at all since chess is all about dynamic. ;-)

I also would advice you to play correspondence chess (where engines allowed and welcome for analysing) and check your engine development against playing such games... this might help a lot for enhancing your chess engines quality.

I'd advice to remember that an engine equal with other engines and world class players simply knows to prevent bad moves, but the good moves are still created only by human brain... ;-))

In this sense it is usefull to have good searching technic, but the most important is what you actually look for when searching

[Edited by - Sebastian Gruber on October 23, 2004 3:51:57 PM]

Share this post


Link to post
Share on other sites
Maybe you could try a multi-level gameplan?

You have a few levels (2,5,?)

on level1 you have your normal gamebord

Then for each level above that, you summerize the board at that level.

This would mean that you can search at heigher levels, and see very far into the future, because the amount of board states would be smaller. (and as such the amount of nodes which would be searched would also be much smaller).

HTH.
From,
Nice coder.

Share this post


Link to post
Share on other sites

This topic is 4800 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this