Recommend
 
 Thumb up
 Hide
11 Posts

BoardGameGeek» Forums » Gaming Related » Computer Based Board Gaming

Subject: programming a card game rss

Your Tags: Add tags
Popular Tags: [View All]
benny Margalit
Israel
Unspecified
Unspecified
flag msg tools
Hi all, my name is benny and i'm a student of computer engineering.
i work on a project now that implement artificial intelligence in card game called whist. it's 4 player trick taken game.
i need some help please at the part of the game tree building.
how should i build the tree if it's 4 player and only 2 like tic tac too or chess ???
i write in c++.
thanks a lot
benny
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Jim Cote
United States
Maine
flag msg tools
badge
Avatar
mbmbmbmbmb
I don't see why you would need a tree structure for a whist AI. You can't do alpha-beta pruning logic when you don't know all the info (like chess). What you can do is keep track of what you know (played cards), and what you can infer (from what wasn't played), etc. This should only require a simple array.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Jorge Montero
United States
St Louis
Missouri
flag msg tools
badge
I'll take Manhattan in a garbage bag. With Latin written on it that says "It's hard to give a shit these days"
Avatar
mbmbmbmbmb
ekted wrote:
I don't see why you would need a tree structure for a whist AI. You can't do alpha-beta pruning logic when you don't know all the info (like chess). What you can do is keep track of what you know (played cards), and what you can infer (from what wasn't played), etc. This should only require a simple array.


You could complicate things a little more by trying to figure out who has ran out/running out of which suit, the expected highest card each player has on each suit, and a bunch of other stuff humans think of when playing trick taking games.

Aside of card counting, the most important thing to this kind of simulation is to write the basic decision rules for a partnership game like this: If I can't win the hand, play a low card. If my partner is winning and can't be beat, play a low card. If I'm trumping, play low or high based on my guesses on the other player's hand.

In conclusion, this AI would have nothing to do with a tic tac toe AI.

 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
benny Margalit
Israel
Unspecified
Unspecified
flag msg tools
i realy in shock now
dont the computer have to build a tree to look ahead few moves ???
if i understand what both of you said you suggest to make every round independent the other rounds !!! ???
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Jim Cote
United States
Maine
flag msg tools
badge
Avatar
mbmbmbmbmb
Of course they are independent. You keep track of what you "know" from previous plays, and you evaluate what to do from there. There's no real look-ahead per se, other than what you can estimate from what you already know. Pure look-ahead usually requires much more knowledge than you can get from a trick-taking card game. For exmaple, you can't say, "If I play the Queen and he plays the 7 and he plays the 3, etc." because you don't know what cards are where. You could execute all possible plays, but 99.9999% of them are invalid since the cards aren't where you think. I would approach the AI using a static state evaluation design.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Stephen Tavener
United Kingdom
London
England
flag msg tools
designer
The overtext below is true.
badge
The overtext above is false.
Avatar
mbmbmbmbmb
I'd say a mixed strategy is in order; in the end game, it should be simple enough to generate all possible hands and make the optimal moves; no pruning, just try each available play against each possible combination of hands.

In the early stages, you can try generating a few probably hands based on the information available and general probabilities, then search accordingly if you like, but I'd just try to encode some basic principles, with maybe some searching based on a single suit/two suits.

I'm sure there must be some documents out there on bridge programming techniques which should give you some pointers; a little background reading may be in order.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
benny Margalit
Israel
Unspecified
Unspecified
flag msg tools
i read a lot and that is why i so confuse.
i have some files on bridge card game and anyone who would like to read them can mail me to : benny74@netvision.net.il
they talk about somthing called partition search.
another answer i got here was :
The way i would approach it, is to seperate all of the possible positions the AI will find itself in into different decision trees:

1. I am leading from my hand.
2. I am 2nd or 3rd following a lead.
3. I am the 4th playing in this lead.

Then you can look at each tree in isolation. The most complex is going second or third and the easiest is going 4th, so perhaps you should start with that.

Going 4th would go along the lines of:

1. I have a card of the suit laid:
A: A trump has been played, therefore i will lay my lowest of the suit laid.
B: I cannot beat the highest card of the suit laid, therefore i will lay my lowest of the suit laid.
C: I can beat the highest card of the suit laid, therefore i will lay my lowest card that beats the highest of the suit laid.
2. I do not have a card of the suit laid:
A: I have a higher trump card than any trump cards that have been played. Trump with my lowest trump higher than any trump played.
B: I do not have a higher trump card than any trump cards that have been played. Play my lowest non-trump card. (Working out which card this is is very difficult in itself, some cards will be useful to guard Kings, others may be high but other players may be trumping that suit, you can make this as complex as you want.)

That is the basics of going last in a single round of 4 cards. Going first would involve looking at your hand and working out which cards were possible winners, and trying to clear the cards above them, or emptying a suit to trump. Going second or third involves weighting different decisions of how high to trump, whether to try and win the trick (e.g. with a queen) when there are still players to go after you.

so ??? i dont know

beside is anyone have a c++ code of suce a tree building ???

 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Richard Pardoe
United States
flag msg tools
badge
Avatar
You might want to take a look at http://boardgamegeek.com/article/74358 which describes efforts to make a simulation of another card game Modern Art

Granted this development used neural networks, but it might have some ideas for you. In particular, you might want to see if you can find one of the references listed at the end of the article: AI Techniques for Game Programmers by Mat Buckland

This might answer some of the questions you are considering as you go forward on this project.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Jorge Montero
United States
St Louis
Missouri
flag msg tools
badge
I'll take Manhattan in a garbage bag. With Latin written on it that says "It's hard to give a shit these days"
Avatar
mbmbmbmbmb
Ah, I see why you want a tree.

I thought you were talking about building a 'dumb' tree, like in tic-tac-toe, and pick the right choice by sheer probability. Obviously, that is a pretty bad way of doing AI.

What you describe as the 4th player is not a tree of all the positions, like you'd see in a brute-force solution of a game. But a set of rules that delegate into each other: If A, then consider a b and c. If B, then look at d,e and f. node a would have its own set of sub-decisions, until a leaf node decides the optimal move.

If that's what you mean, I have bad news for you: there is no easy way of creating all of those rules automatically: You'll probably end up creating the nodes and dependencies by hand.

The program needs to obtain the information on how to play somehow. You either write it by hand in the code, or use machine learning techniques to teach the program how to win the game. The problem is that most of those techniques seem to be way above what your current level of expertise is. For an example, look at that modern art program. Learning how any of those techniques work will take much, much longer than writing the couple dozen rules that you'd need to make a rules-based AI.





 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
benny Margalit
Israel
Unspecified
Unspecified
flag msg tools
i want to try programming in open mode.
what i mean is that the computer will see all the players cards and build the tree with this knowledge.
how can i write such a tree building ????
after that and when i see that it's work good i only have to add some probabilities function to generate player hands.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Ricco van Prooijen
Netherlands
Nieuw-Vennep
Unspecified
flag msg tools
You basically want a Whist version of Deep finesse:
http://www.deepfinesse.com/description.html

This is a bridge analyzer that solves any deal with all hands open. It's no freeware unfortunately, but you can always try to talk to the designer.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Front Page | Welcome | Contact | Privacy Policy | Terms of Service | Advertise | Support BGG | Feeds RSS
Geekdo, BoardGameGeek, the Geekdo logo, and the BoardGameGeek logo are trademarks of BoardGameGeek, LLC.