glo

Hi everyone

Me trying to code a simple backgammon game that will feature computer player/s.
The program stores the current board+dice status, and all legal move sets for them.
It is about where the program has to choose which one is the best move set to carry out.

Thing is I suck really bad at board games that require a bit of strategy, right about every common chimp should be able to humiliate my gaming skills.

So I figured Ill ask here about what backgammon strategies the AI part should be directed by, and ultimately decide how to implement them together.

Here are a few I can come up with:

• Eatting opponent soldiers
• Advancing towards the home quarter
• Creating 2soldiers blocks
• Low risk to be eaten

So please, any ideas are welcome and appreciated,
Thanks.

Happy_Reaper

You're looking at simply doing alpha-beta pruning with some heuristics, there, friend.

__________________
Teacher: "You connect with Internet Explorer, but what is your browser? You know, Yahoo, Webcrawler...?" It's great to see the educational system moving in the right direction

Nodtveidt

I have no idea what Happy_Reaper just said. But I was working on a backgammon AI at one point in time and came up with some rather effective priorities. It does, of course, depend on how intelligent you want the AI to be. There are many ways of playing the game...you can be a defensive player (putting priority on safe moves rather than conquering), an aggressive player (conquering at all possible opportunities at the expense of progression), or any range in between. The way I implemented my backgammon AI was to have a RNG that determined the type of move the CPU would play next in terms of aggressiveness, then after the die roll, use the value to determine which pieces to move to accomplish it...say if it rolled a 4 and a 5 for dice and a 90 for aggressiveness (highly aggressive), it would look to see if any opposing pieces were within 4 or 5 moves, and if so, conquer them, otherwise move pieces towards home that are closest. If the value had been in favor of a defensive move, it would look for any of its own blots and try to pair them if possible. It was a relatively simple AI but it was effective and could beat quite a few players because of its unpredictability. There's better ways of doing it, and google turns up a few good links so give it a looksee.

__________________

Happy_Reaper

Alpha-Beta Pruning

__________________
Teacher: "You connect with Internet Explorer, but what is your browser? You know, Yahoo, Webcrawler...?" It's great to see the educational system moving in the right direction

glo

Thank you both for sharing your experience.
Another method I ran into while surfing the net this week is Temporal Difference Learning which is used in TDgammon.
There appear to be several ways to achieve what I am looking for, but I am not sure which one is simple enough, yet still useful?

IfYouSaySo

Not sure if Alpha Beta is the correct algorithm for Backgammon. Because isn't alpha beta for turn-taking perfect information games? Backgammon is turn-taking, but it is not a perfect information game. Since dice are involved, you can't predict with certainty what will happen on future moves. Not sure what the correct algorithm is; but probably it will involve probabilities. I'll have to look into my AI book tonight and see what it says about this...

__________________
The crows maintain that a single crow could destroy the heavens. Doubtless this is so. But it proves nothing against the heavens, for the heavens signify simply: the impossibility of crows.

Happy_Reaper

You can do a probabilistic Alpha-Beta tree. Nevertheless, I still believe TD learning is a very solid way to make a Backgammon opponent, especially due to the fact that the sample space is so large.

__________________
Teacher: "You connect with Internet Explorer, but what is your browser? You know, Yahoo, Webcrawler...?" It's great to see the educational system moving in the right direction