# Artificial intelligence

I'm trying to write a 1 player card game and I'm stumped on how to go about telling the computer what card to throw. I'm not very experienced in natural intelligence, never mind artificial intelligence(lol). Any clues on how to go about the Ai process would be appreciated. Is it just a matter of if this or if that, or is there more complex formulas involved. Where can I go to reference AI?? I have alot of points built up, so a helpful answer will get some good bonus points.Thanx, Karl
###### Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Commented:
What are the rules of the card game?
0
Commented:
do you mean 1 player, like solitaire, or one player versus the computer?
0
Commented:
I'm assuming it is one person against the computer.

Your problem is to make the computer decide which card to throw. This problem is similiar to the decision of the next step in chess or backgammon game.

One of the easiest way to do it, is the following:

For each possible card throw, the computer get a potential state.
The computer should has a set of rules that gives a score for each state (IE, in chess, if the move causes mate to the opponent, than the score of the state is higher than of a move that eats only knight).
Now the computer chooses (randomally) one of the states with the highest score and plays it.

The BIG problem is to write those rules correctly.
I don't know what is your cards game, so I cannot give you an example.
BTW, Deep Blue used a close approch in its game with Kasparov, but in this case, IBM got a chess master writing those rules...

After you have the rules, you can "fine tune" the scores by letting the prog1 play against prog2 (instead against person), when the scores are a bit changesd, and see which progams wins more times statistically.

Hope this is will help you for the first step,
Fuzzy.
0
Commented:
Agreed with FuzzyLogic. Most gameplaying programs follow that tactic even further out. For two player games (like chess) a tree is constructed. For each of your moves, and each your opponents possible moves after that, and each of your moves after that etc. etc. You go as deep as you can, and then evaluate the resulting board positions. This evaluation at the bottom of the tree is the crux of the programs "intelligence". Everything else is brute force. The deeper the tree, the better the program will tend to play.

In your case, the tree would presumably consist of all your own turns (if it is solitaire), but the sequences would be different. Again though, the program would be driven by the evaluation of the results at the bottom of the tree.
0
Commented:
Not to repeat other comments, but you need to draw out a flow chart, etc for card game play.  Then implement this flow chart in some sort of state machine.  You could use a:

switch(move)
{
case 0:
break;
case 1:
break:
...etc
}

sort of statement with all possible moves to start.
0
Author Commented:
The actual game is pitch (hi-lo-jack)
One player versus 3 computer opponents. Game play would consist of following suit or trumping in, etc . . .
Also, any help finding a place to research Ai would be helpful.
0
Commented:
Have a look at
Artificial Intelligence by E.Rich and K.Knight
or
Artificial Intelligence by Patrick H. Winston

(they're both books I read whilst I was doing AI at uni)

The specific algorithms you're looking for are called Minimax and Alpha-Beta Pruning.You should be able to find loads of examples on the Web without too much trouble...

http://yoda.cis.temple.edu:8080/UGAIWWW/lectures95/search/alpha-beta.html discusses both...

http://cindy.cis.nctu.edu.tw/AI/ai1/ai-6.htm also discusses both algorithms with reference to games...

They've both got their own strengths and weaknesses, but in general they have the same problem. In order to make any of these algorithms work you HAVE to have a way of evaluating the state of play. This is an absolute necessity because you have to be able to figure out what is a good move and what is a bad move.

The answers given above are accurate as far as they go except for a couple of things. Firstly, for a non-trivial game it's simply not possible to create a full state-machine/game tree. For something like tic-tac-toe it's fairly large, for anything more complex it rapidly spirals out of control.

The other thing is that in order to make a _good_ player of any game you have to consider further than just the current move. Both Minimax and A/B pruning build a tree where each level is a move in the game. Good AI generally builds trees as deep as possible given the time restraints...

What generally happens is that a full tree is constructed up to about 2 or 3 moves ahead then the best few moves are investigated to a much deeper level.

Incidentally, most algorithms generally consider 2 player adversarial games since they make the trees smaller, but I don't see any reason why the algorithms can't be extended to n-player games...

Cheers,

0
Design Monitoring & Evaluation ManagerCommented:
i have to agree with  AJfleming ,
u can use minmax or alph-beta , but don't try to use
switch(move)
{
case 0:
break;
case 1:
break:
...etc
}
because it's not efficicienc at all in thats kind of program.
0
Commented:
I must add that Alpha-Beta complexity
is sqrt(n) comparing the MinMax n nodes
to scan.

There is this problem with cards game
that you don't have all the information
to build a proper decision tree.

therefor, you should build and maintain
a database (array) with information about your oppnets cards.

the evalution of a node should include
how good is the new state AND the probabilty (the edge/arc) of getting there.

if you could write the rules of the game (hi-lo-jack ?) we could try and phrase something out...

Yair

0
Author Commented:
rules of the game, huh. well, I'll give basic rules. There are 4 points in each round of play. The high card of trump, the low card of trump, the jack of trump and total game points (a=4,k=3,q=2,j=1,10=10) Each player bids 2,3 or 4. figuring he can get that many points. (a 2 bid is jack low or high low or high game . . . ) The winner of the bid leads with trump,  and each player follows suit if he can. The highest card takes the trick. (trump takes non-trump). That player then throws a card etc... Each player follows suit if he can or trumps in if he wqants. play continues till all 6 tricks are played. Basically, you wouldn't want to throw point cards or game cards if you think the bidder will take the trick. If the bidder led with an ace and I had the 2 and the 3, since the 2 is low, I would want to throw the 3.
0
Author Commented:
Adjusted points to 400
0
Commented:
Karl,

depending on how sophisticated you want to get, you might want to consider a heuristic based system in this case. Your branching factor is likely to be very high so generating a tree is going to be very difficult/time-consuming. An alternative is to create a set of "rules of thumb" which are considered at each point in the game. For example

if player holds a card which can win the trick, then play it.
if player is bidding then bid according to what is the best outcome they can expect from their hand.

etc.

You'll have to do some careful tuning of your rules to get the system to work well, but in the short-term at least, you'll get a system which plays - albeit badly - very quickly. Then, if you get your heuristics right you can improve the standard of play very quickly and easily.

If you dig up some articles on the web on expert-systems or rule-based systems then you'll probably get an idea of how this sort of thing can be done, or I can probably outline a rough implementation if you like.

cheers,

0
Author Commented:
So am I basically back to, if else if else if else???
0
Commented:
To an extent. I guess it really depends on how smart you want the system to be. If you want it to be seriously intelligent then you *could* create a tree each time - but its going to be slow. Alternatively you can create a rules-base which is quick - but only as smart as the heuristics you put in it.

cheers,