say we have a game of checkers, how can we define a heuristic function for a "weak" opponent and one for a "strong" opponent?

I would love to help but I don't know the rules really!
I know it's aweful but true...
I am sure that you want to contiue on to code alpha, beta right? But
sorry... ;-)

If you are looking to evaluate how strong a given board position is for one side. Start of simple with :

[weight] = how many checkrs they have on the board (maybe apply some scalar to the weight of king pieces)

Then to get more complex check the value of [weight] given different combonations of moves from each team. The more ways you can get [weight] to increase, the better.

[Edited by - theJuckett on April 5, 2005 3:10:51 PM]

Maybe it's me who's misunderstood you, but it sounds like the OP wants a way to judge if a player is a good player or not - for something like evolving a good player using a genetic algorithm.

There are a couple of heuristics that jump out immediately. For example:

Proportion of wins
Number of moves taken on average when winning (lower = better)
Number of moves taken on average when losing (higher = better)
Average number of pieces left at time of win (higher = better)
Average number of opponents pieces left at time of loss (lower = better)
Number of pieces promoted
Maximum chain of pieces taken (checkers is where you can jump several pieces in succession, yeah?)

The problem is, these are going to vary with the quality of the opponent. So, for example, a player with a win/loss record of 50% who only plays other strong opponents has to be interpreted very differently to a player with a win/loss record of 50%, but who only plays against weaker opponents.

So - maybe a matrix of heuristics? Something like a hidden markov chain or a fuzzy logic system could be used to categorise other players (obviously, everyone starts off as unknown strength), and contributes factors to the heuristic dependent upon strength of opposition.

For example : if you eventually boil all these down to a singular heuristic function H, then:

If I win a game:
Add 3 to the heuristic if the other player was 'Strong'
Add 2 to the heuristic if the other player was 'Average' or 'unknown'
Add 1 to the heuristic if the other player was 'Weak'

Hope that's given you some ideas.
Jim.

Well, to the best of my knowledge, it seems that a champion level checker playing program was devised as early as the 60s or 70s, can't remember exactly, but the problem seems to be a lot easier than chess that's for sure.

Now, if you have no pre-existing data to go on, then the best way is to make decisions in game. A game as simple as checkers have what can be seen as "advantageous" formations or board layout. I do believe there are quite a few methods out there or you can simply devise one that looks at the layout of the pieces and determine who seems to have the upper hand within the next few moves. Based on this, players that put themselves into "advantageous" positions more often during a game can be seen as being better, or at least is playing a better game right now.

Judging the opponents strength is not usually good if you want to win games, but can be nice to make it seem like an even match and keep players interested.

thanks for that guys, i was thinking of adding specific weights to the normal pieces and the kings as well and was trying to think of other factors to consider to make up the heuristic. im not much of a checkers player but when we play, what should we take into account before makng our move?

I've done a kind of self learning checkers program long time ago on the Amiga (*dreams of good old times).

It was the usual alpha-beta search with the heuristic taking following into calculation (this is what I still remember):
- number of pieces on the field
- number of "kings" (that's right? the special ones that can move backward too) on the field
- distance of normal pieces from the end line
- distance of pieces from the center
- number of possible moves for actual player
- number of pieces with "backup" (pieces that can't be beaten, so two or more in a row)

I wanted the AI find the propper weights for these for its own. This was done by following:
The computer did a regular game against itself on a given search deep and saved all moves. At the end I did for the loosing side the following:
- Repeat all moves and do for each move an additional search with a very high deep (say regular search deep is maximum 6, and for this we do a search on deep 10).
- Take the move from the additional search (10 moves) as "the perfect move".
- do the same search deep 1.
- comepare those two moves, if same, continue with next move of original match. if they differ:
- try to find what weight prevented the computer from making the "perfect" move and adjust the weight some. -> done.


well... It didn't play fast and not perfect, but I was pleased with the results :)

i hope this helped you some or at least was fun reading ;)

Move = Minimaxwithalphabeta(Evaluationfunction, min, max, game, numplies)

From,
Nice coder

If your looking for a function:

Beginner:
Number of men + Number of kings * x

X is some int that seems to do the best for you.

You can also do a very simple heuristic map. (ie. You make a grid which shows how good it is to be at that square).

Advanced:
You have pattern matching, which will find things like the impossible to block piece, good offencive/defencive patterns, ect.

This can be very fast. (can you say bitboards).

From,
Nice coder.