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

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...

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]

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.

Not sure if this has been mentioned, but check for pins and forks.

Also remember that in chess controlling the middle of the board is important.

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)

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

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.

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]