Link to home
Start Free TrialLog in
Avatar of kag0
kag0

asked on

AI for card games

I'm trying to write a card game in c++. The game is pitch (hi-lo-jack).
I'd like some sort of kick start to the ai portion of the program. Like how to represent the cards and how to tell the computer what to throw. Thanks, Karl
Avatar of Sage020999
Sage020999

I am working on the first Pedro game right now.  You can use the Cards.Dll for windows to create the cards and keep track of them numerically.  The cards are represented from 1-54 for the first deck and 54 - 106 for the second deck.  The logic shouldn't be two difficult after you know what the number of the cards should be.  If you explain the game for me, I can help right the code for you.
Avatar of kag0

ASKER

OK. Rules, huh?? Well game play can be tricky since I want 1 player vs. 3 computer opponents. There are 4 points in each round of play. The high trump, the low trump, the jack of trump and any game points (game points are a=4, k=3,q=2,j=1, 10=10). Each player is dealt 6 cards then bids 2-4. (A 2 bid could be high low, or high jack, or low game . . .) Highest bidder leads trump. you must follow suit unless you can trump in. Play till 11 points.
Those are the basics of the rules, but game play can get more involved when using strategies.
Question, How would I use cards.dll in my program??
Avatar of kag0

ASKER

I Haven't had a response in over a week, so I'll open up this Q to someone else. Sorry
Not much can be said beyond using the rules. Prioritize different cards, get it to look for certain combinations in it's hand, look for incomplete combinations, reject 'oddballs'. I've never played this card game before, so I don't know much in the way of details.

-Dan
Oh, btw, check out www.gamedev.net's forums for help. Believe me, you won't go back. (I only come back to expert's exchange for help after gamedev.net has failed).
Sorry, I don't think I recived notification of your post.  If you are still interested in the Cards.Dll the following should help:



Here is an example of my Cards.Bas file:



Option Explicit

Declare Function WinHelp Lib "user32" Alias "WinHelpA" (ByVal hwnd As Long, ByVal lpHelpFile As String, ByVal wCommand As Long, ByVal dwData As Long) As Long

' Some useful constants
Global Const FACEDOWN = 0
Global Const FACEUP = 1
Global Const CARDWIDTH = 71
Global Const CARDHEIGHT = 96
Global Const OFFSET = 16


' Required in Form Load to use dll
Declare Function InitializeDeck Lib "qcard32.dll" (ByVal hwnd As Long) As Long
' Reset all card values to defaults
Declare Sub SetDefaultValues Lib "qcard32.dll" ()
' Set the currently used card back design for cards 105 to 109
Declare Sub SetCurrentBack Lib "qcard32.dll" (ByVal nIndex As Long)

' Card drawing subs
Declare Sub DrawSymbol Lib "qcard32.dll" (ByVal hwnd As Long, ByVal nValue As Long, ByVal X As Long, ByVal Y As Long)
Declare Sub DrawCard Lib "qcard32.dll" (ByVal hwnd As Long, ByVal nCard As Long, ByVal X As Long, ByVal Y As Long)
Declare Sub DrawBack Lib "qcard32.dll" (ByVal hwnd As Long, ByVal nValue As Long, ByVal X As Long, ByVal Y As Long)
Declare Sub DealCard Lib "qcard32.dll" (ByVal hwnd As Long, ByVal nCard As Long, ByVal X As Long, ByVal Y As Long)
Declare Sub RemoveCard Lib "qcard32.dll" (ByVal hwnd As Long, ByVal nCard As Long)

' Get card information functions
Declare Function GetCardColor Lib "qcard32.dll" (ByVal nCard As Long) As Long
Declare Function GetCardSuit Lib "qcard32.dll" (ByVal nCard As Long) As Long
Declare Function GetCardValue Lib "qcard32.dll" (ByVal nCard As Long) As Long
Declare Function GetCardStatus Lib "qcard32.dll" (ByVal nCard As Long) As Long
Declare Function GetCardBlocked Lib "qcard32.dll" (ByVal nCard As Long) As Long
Declare Function IsCardDisabled Lib "qcard32.dll" (ByVal nCard As Long) As Long
Declare Function GetCardX Lib "qcard32.dll" (ByVal nCard As Long) As Long
Declare Function GetCardY Lib "qcard32.dll" (ByVal nCard As Long) As Long
Declare Function GetUser1 Lib "qcard32.dll" (ByVal nCard As Long) As Long
Declare Function GetUser2 Lib "qcard32.dll" (ByVal nCard As Long) As Long
Declare Function GetUser3 Lib "qcard32.dll" (ByVal nCard As Long) As Long
Declare Function GetUser4 Lib "qcard32.dll" (ByVal nCard As Long) As Long

' Set card information subs
Declare Sub SetCardStatus Lib "qcard32.dll" (ByVal nCard As Long, ByVal bValue As Long)
Declare Sub AdjustCardBlocked Lib "qcard32.dll" (ByVal nCard As Long, ByVal bValue As Long)
Declare Sub SetCardDisabled Lib "qcard32.dll" (ByVal nCard As Long, ByVal bValue As Long)
Declare Sub SetCardX Lib "qcard32.dll" (ByVal nCard As Long, ByVal X As Long)
Declare Sub SetCardY Lib "qcard32.dll" (ByVal nCard As Long, ByVal Y As Long)
Declare Sub SetUser1 Lib "qcard32.dll" (ByVal nCard As Long, ByVal bValue As Long)
Declare Sub SetUser2 Lib "qcard32.dll" (ByVal nCard As Long, ByVal nValue As Long)
Declare Sub SetUser3 Lib "qcard32.dll" (ByVal nCard As Long, ByVal nValue As Long)
Declare Sub SetUser4 Lib "qcard32.dll" (ByVal nCard As Long, ByVal nValue As Long)
Declare Sub SetOffSet Lib "qcard32.dll" (ByVal nValue As Long)

' Dragging subs and functions
Declare Function InitDrag Lib "qcard32.dll" (ByVal hwnd As Long, ByVal X As Long, ByVal Y As Long) As Long
Declare Sub AbortDrag Lib "qcard32.dll" ()
Declare Sub DoDrag Lib "qcard32.dll" (ByVal hwnd As Long, ByVal X As Long, ByVal Y As Long)
Declare Function EndDrag Lib "qcard32.dll" (ByVal hwnd As Long, ByVal X As Long, ByVal Y As Long) As Long
Declare Sub ReturnDrag Lib "qcard32.dll" (ByVal hwnd As Long, ByVal nCard As Long, ByVal nOldX As Long, ByVal nOldY As Long)
Declare Sub BlockDrag Lib "qcard32.dll" (ByVal hwnd As Long, nFirst As Long, ByVal nNumCards As Long, ByVal X As Long, ByVal Y As Long)
Declare Function EndBlockDrag Lib "qcard32.dll" (ByVal hwnd As Long, nFirst As Long, ByVal nNumCards As Long, ByVal X As Long, ByVal Y As Long) As Long
Declare Sub ReturnBlockDrag Lib "qcard32.dll" (ByVal hwnd As Long, nFirst As Long, ByVal nNumCards As Long, ByVal X As Long, ByVal Y As Long)
Declare Function GetFreeDestination Lib "qcard32.dll" (ByVal nSource As Long) As Long

' Undocumented functions, generally not used

' returns the number of any unblocked card which lies beneath the mouse coordinates x, y
Declare Function PointInFreeCard Lib "qcard32.dll" (ByVal X As Long, ByVal Y As Long) As Long

' returns the number of any card whose top 16 (or OffSet) pixels lie beneath the mouse coordinates x, y
Declare Function PointInCardTop Lib "qcard32.dll" (ByVal X As Long, ByVal Y As Long) As Long

' manually sets the active drag card for a subsequent DoDrag or BlockDrag call
Declare Sub SetActiveCard Lib "qcard32.dll" (ByVal nCard As Long)

Public PassArray As Variant
Public intPassNum As Integer
Public blnExtra As Boolean


I just finished a rummy game for TAX here on EE.  If you are interested here is the link:  http://www1.experts-exchange.com/bin/ShowQ?MBL=on&qid=10335646&anchor=2784420#2784420

I can also send you an example of a pedro game I am currently working on if it will help.
I think somebody else (or maybe you)
raised this question 3-4 months ago.

PLEASE try to explain as to an idiot the rules of the game. assume nobody knows anything about cards playing.

I really wanted (and want) to help you
but I just couldn't understand the rules.

Avatar of kag0

ASKER

Rules: The game is to 11 points. Points are High Low Jack and Game.
 High is the highest trump in the game play.
 Low is the lowest trump card
 Jack of trump
 Game is the total Face cards and Tens in your hand at the end of the round.
 Ace=4 points, K=3, Q=2, J=1, and 10=10 points. When a bidder is trying to get game as one of his points, 10's become very valuble.
In each round of play, you get 6 cards. You bid how many points you think you can get,(Lowest bid is 2).
 A 2 bid would be High trump & low trump or high trump & jack trump. or jack & game etc. A 3 bid would be high, low game or hi lo jack.
 once everyone bids, the dealer can decide to take the bid or let the highest bidder go.
 The winner of the bid leads out with trump. Each player follows suit if he can. If not, he would throw any other card. If during game play, the lead card was not trump,the player can play a trump card if he wants to.
 
 Basic strategies:
 Playing point cards (such as a 10 or 2 of trumps) when the bidder leads with a card you think may be beat by another player.
 
  Protecting point cards in your hand. Example if you have a 10 and a 6 of one suit, you don't want to get rid of the 6 in case the bidder plays a high card of that suit, you don't have tto give him a 10.
 
 Taking the lead. When the bidder is to your right, You don't want the lead. If he has last play, he can "watch the board" or play a point card.
 If he is to your left, you do want the lead. That way everyone else can watch what he throws. Makes it more difficult to sneak points in.

Well, that should be a good start, any confusion, let me know, and i'll try to clarify. THANX for the help, Karl



Avatar of kag0

ASKER

Adjusted points from 200 to 450
At:
http://www.pagat.com/allfours/pitch.html

there is a very good description of the rules.

I am not much of a cards player, and I still have some holes but lets try to coap with some of parts:

bidding:
--------

you have no information about the oppenents cards.
You know what were their bids (if you are bidding them)
you must bid higher value or pass.

your options are bid 1,2,3,4 or pass.

now please help phrase some rules like:
if you got card 2, you can bid atleast one. because their is a good chance you
have the lowest card.

if you got card Ace, you can also bid atleast one. because their is a good chance you have the highest card.

and so on...

please phrase some more rules and we will try to 'formalize' it...

Yair

Avatar of kag0

ASKER

I already have a good program for bidding.  What I'm looking for is a method for figuring out what card the computer should play during gameplay.
 I'm not looking for someone to give me the exact code of the gameplay, I'd like to get an idea on AI fundamentals and such. A good example would be, narrowing down possible choices. If spades were led and he has spades, he has to either follow suit or trump in. If he follows suit and he gets a 10, should he trump in. Is AI just a series of ifs or is there more to it??
ASKER CERTIFIED SOLUTION
Avatar of yairy
yairy

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
well, did you see the slides about gammon ?

Avatar of kag0

ASKER

I'm starting to understand the concept of min max and alpha pruning, but I am confused on how to code it. Would I use switch or for loops or if's?? A very basic example would be appreciated and would show in the point upgrade.
Thanx, karl
>Would I use switch or for loops or if's
is it important ?

example of what ?
you have the basic code in the slides.
do you mean a more conceptual view like
what is the nodes structure in your implementation ?, what are the operations ?

I'll give you a poker game (the only card game I know) simple example:

I would say that each node should contain:
- my cards
- the oppents cards (or more exactly, the cards they surly don't have (mine))
- how much money do I have
- the betting sum of every player
- how many cards did he exchanged
- my status
- potentional gain
- probabilty of the gain

my operations are:
- quit
- equal the betting sum
- add to the betting sum

now we must define ending conditions
(when to stop expanding nodes)
it may be something like applying the rules of game in this case.

for each operation that might happen,
we will produce sons of all possible new states that could happen.

after building the tree is done, we could choose the path that leads to best node in terms of gain/probability to happen ratio.

I know I might sound fag. it's because
I never actuly implemented a probability Alpha-beit tree.

maybe someone that did, may shed some light here....

Yair

Dear Kaq0,

doing a reduction to poker, you really pin-pointed a very hard AL problem.
here are some links (the second looks promissing, if you could translate the language) about AI implemetation of a poker card game.

1) you could get some concepts and ideas from their.

2) as you will see it is a hard task.


http://www.cs.ualberta.ca/~davidson/poker/poker.html

http://rekop.pantheon.cx/

http://www.cs.ualberta.ca/~jonathan/Courses/622/Proposal/pena/pena.html


there one thing I might advise you, but take it in limited:
all these methods are FORMAL methods.
There is a disputed claim in AI that says that one can't describe all realities in a formal aproach (operation, states...) because reality is too compicated actualy to be described in simple concepts.

for example, 'intuition' in chess can't be described in a decision tree.

there is a branch that is called ANN (Artificial Neural Network) that try to LEARN what to do by examples. the basic idea is to imitate the human brain Neural network.
for examlpe, we play poker a lot from experience, without getting into probability calculations...

the idea is to build a net of weights and tweak it by known examlpes and solutions. after it is trained one can hope it will solve unknown states.

doing that you bypass many definitions.
for example, if we build a hand-write digits recognizer, instead describing that 8 is "two close shapes in the same size (more or less) one above the other..." we could just give the net examples of many 8's and it will figure out what to do...

offcourse, it is not so easy. a good representation of the state is very important, and more...

I am not sure it was done before on a card game...

to sum things up,
play chess. :-)

Yair

well, any luck ?
Kaq0 wrote:

"Is AI just a series of ifs or is there more to it??"

It seems that the question may have stalled.  Sorry if my interrupting is a nuisance, but I couldn't help but notice the above comments and its response by yairy.

I am a conditioned 'rejecter' of the notion of AI insofar as computer systems are concerned.  I tend to agree with kaq0 - AI is simply a bunch of ifs.  The end.  I have not found evidence to dispute this claim - and it is not apparent in yairy's comments.

We might waffle on with neural nets, domain space traversal, pruning algorithms, and all the rest of it.  There are even those who espouse a 'learning' system approach.  This of course would be the ultimate in AI technology - but let's examine it just a little.  If Action1 ocurrs in the Location1 frame of P2, then ignore it.  If Action1 occurs multiple times then flag path/scope or whatever as being 'less likely' ...... and so on.  Nothing but a bunch of if..then..else.  All the contemporary 'learning' systems can manage is a hybrid of something like 'smart heuristics'.

Sorry to disagree.  The subject fascinates me though.  Any comment?

Dave
Avatar of kag0

ASKER

Looks like I'll have alot of if else's then. Thanks for the comment,it puts things into perspective.
kag0,

Of course, there are very smart ways to construct these chains of if..then..else statements.  You only need look as Case Select to see that programming has come a long way from the days of machine code through to what may now be considered 5th generation programming.

I have worked with code that cannot even be readily recognised as if..then..else - however the level of sophistication is generally beyond the inquisitive, or novitiate.  So I do hope my comments haven't put you off the idea althogether - such was not my intent.

Regards

Dave
Summarizing the two links I gave you:

http://www.cs.umbc.edu/471/lectures/games/sld001.htm 

http://sern.ucalgary.ca/courses/CPSC/533/W99/presentations/L1_5B_McCullough_Melnyk/ 

as 'bunch of if's' is almost insulting.
is Sorting a bunch of loops and If's ?
are algorithms just a bunch of loops and If's ?
The answer is yes, in the lowest end, it all comes to statements, branchs and loops.

There is buety in Alpha-Beta (of this case) and many other search and decision methods.

How are you going to solve NPC problems without Uristic approaches (Genetic algorithms, simulated anilling, hill climbing and more)

how are going to play chess / gammon / tie-tau-toa ?


I am not the 'knight' of AI, but I think comments as that are a little bit shallow.


Yair

Hi yair,

I was wondering if you were keeping an eye on this!  Thanks for the comments.  A couple of those are important:

1. You said: "as 'bunch of if's' is almost insulting."

Well, I tend to agree with you.  I don't however think that it should be insulting for individuals - including yourself.  If there is an insult either implied or intended in statements like these, it is correctly aimed the the 'notion'.  Intelligence in a machine?  Ha!  That is a joke, and is an enormous insult to the incredible faculty of real intelligence that most people share.  Can a machine actually replicate human behaviour?  I say categorically not!  Look at the work at MIT and other 'well-funded' institutions - they have to spend weeks, if not months, 'telling' a computer that if your left foot is in the UK, your right foot can't simultaneously be in the US.  A 2 year old baby intuitively knows this!

2.  You also said: "it all comes to statements, branchs and loops."

And this confirms my thinking.  When you reduce the code to its basic elements, it is just if, loop, do etc.  In other words, an intelligent 'being' [that's you and I] wrote some code that instructed the Computer in how it should 'behave' according to a bunch of rules.  Again - the end.  It is you and I that are intelligent.  A computer is nought but a pile of silicon, plastic, metal, and retains momentary spikes of electrical charge.  A computer doesn't 'understand', 'know', or 'think' anything at all.  Nothing.  It doesn't even 'understand' 00011001 - they are just impulses that fire mechanical/chemical reactions.

How dare someone suggest that a computer has some form of intelligence that mimics, corresponds to, or replicates the intelligent behaviour of human beings.

3. You also said: "I think comments as that are a little bit shallow."

Well, on this one you are not on the same wavelength as I.  It is not shallow - it is those who say computers can think and learn as do you and I, that they can 'behave' as intelligent people behave, that are shallow.  Such a low view of the abilities of the brain.


Yep, we can write very clever algorithms to convert, manipulate, and present streams of binary digits into pixels that 'say' Kn-Kb4.  But still, these are nothing but if..then..else.. statements - no matter how well we disguise them.

A couple of questions.

Do you know of any computer that:

wrote an original novel?

created a new theory?

'decided' to do something the foundation for which cannot be traced to instructions?

behaved spontaneously, in an attempt to preserve a sense of 'itself'?

you would be happy for your daughter to marry?


Please don't misunderstand my intentions.  Computers are amazing.  They have the ability to process incredibly large amounts of data, in incredibly quick time - far in excess of the ability of the human brain.  I look forward to the future with the advances in technological capability.  Society would be the worse for not having such wonderful tools.  And much of the improvement can be traced to the work of those specialists 'playing' with the concepts of AI.

Artificial?  yes.  Intelligent? no.

Regards

Dave
Avatar of kag0

ASKER

ar·ti·fi·cial in·tel·li·gence noun

1.  development of intelligent machines:  a branch of computer science devoted to the development of computer programs that will allow machines to perform functions normally requiring human intelligence.

This should clear up the debate over AI, Right from Mr. Webster himself.

Now, does anyone have any source code that gives a basic example of some sort of AI??
  Thanx, Karl
I can give you a ANN program I wrote that Identify digits.

and a A* algorithm implementation that solves the 8-puzzele problem (what moves should be done to sort a board 3*3 if digits and one empty disk...)

do you want one of them / both ?

I'll comment on TigerMan's remark later...

Yair

I know I am goind to sound wired here...

The are many ideas that were morked about in the past turned out to be true:

The evoluation idea.
Erath srounds the sun, not viis-versa.
and many more...

I don't mind to be laughed at, but the human brain is basically machine.
every Neural (and you have about 10^12)
is a simple pulse - no pulse function if a certain amount of input is given.

ones output, is others input...
and offcourse, many iterations happen parralely.

True, AI is more or less stuck in the past years. it seems that robots will never serve us dinner...

the reason for that, as I said before, is that trying to describe reallty in formal methods wouldn't work.
the reality is too complicated to be described in resulotions, SAT's and more...

there is a branch in AI, that I think is very promissing.

Genetic Algorithm will immitate evolution in order to find a solution.
ANN will recognise digits, criminal clusters, and your voice.

there is not a lot to argue about them, because it is happening in the present.

but please, lets get back were I started. todays single-0/1-processor computer are very limmited.
and maybe its our bottle-neck.

what tommorow will bring:
we will have multi-processor computers,
Analog computers (not 0..1 but in between) and more.

much like you and I, machine CAN learn.
download a Speach-recognition program,
as more you use it, the better it gets.

in Ten-Twenty years,we will have a self-driving car (there is one now)

As inconviniet it might sound, we are not the only beings that can learn.
we are a collection of atoms, like everything else...

nothing last for ever, even our suprioty over the planet.

Yair

Avatar of kag0

ASKER

I'll take a look at both of them. let me know if you want to email them to me or post them here. Thanks
Hi yairy,

Thanks for the comments.

Yes, I disagree - but you knew that.  It is interesting to hear others' ideas though.  Two points to focus on from your previous notes.

First, do you really think that evolution has been proven?  Darwin's theory is still just that - a theory.  Empirical evidence is not possible - except for the very, very old people in the world.  Proof is not possible.  Only theories that change from one season to the next.  Were I to base any argument on the 'truth' of evolution, I would be ono shaky ground indeed.

But, second, and more to the point, you wrote: "much like you and I, machine CAN learn."

With this I vehemently disagree.  You would know of Turing's modified test for AI.  Why has it not been met?  Because machines do not have, and I suspect never will have, the capacity to learn in a way that even approximates the learning of humans.  Do you really thing the automation of mundane, repititive, or data intensive/processing tasks is learning?  Seems to me that voice recognition is nothing better than Pavlovian conditioning - the difference of course is that computers don't need to be fed a diet of sausages and negative rewards.

Andn third, you said: "todays single-0/1-processor computer are very limmited. and maybe its our bottle-neck"

With this I wholeheartedly agree.  The future is indeed beyond our imaginations, and we would be ignoring reality if we ignore the enormous leaps that have been made.

Anyway, thanks for the time.  I guess others may not be as interested as we in these notions.

Have a great day,

Dave

There is a good documentation,
but in Hebrew.....

Here is the eight-puzzle a* alg.
we will represent a board with a integer. when 1 is space, 2 is one,
left to right, up to down.

be happy to answer questions.
runs well on VC6.00

it solves 100 puzzles, in the minimum number of nodes to be expand. and the minumum path possible.

as one can see, it is not IF's oriented... ;-)

#include <math.h>
#include <iostream.h>
#define MaxSize 10000
#define NumberOfPuzzles 100

long InitialStates[NumberOfPuzzles]={
       396842751      ,241867539      ,139674825      ,194785263      ,657438291
      ,697234518      ,178943562      ,642513879      ,319267548      ,197485236
      ,398642157      ,261753489      ,632174859      ,236759814      ,891527463
      ,463827519      ,853172649      ,283916547      ,538726491      ,756219834
      ,798562314      ,138476925      ,692384175      ,189276354      ,793148256
      ,861327954      ,287359461      ,426583197      ,231596478      ,652871349
      ,253476198      ,724368591      ,394615872      ,592138674      ,218753649
      ,784691235      ,964712358      ,854639271      ,957841623      ,431782659
      ,987246513      ,985741623      ,916845237      ,295176384      ,741962538
      ,954361827      ,236148957      ,675491238      ,397651248      ,873145269
      ,197634825      ,178345296      ,672594138      ,378294561      ,934867512
      ,593468217      ,147623985      ,394865721      ,534897621      ,928173456
      ,657482139      ,256794138      ,324981756      ,274169583      ,761928543
      ,271693485      ,276958431      ,251837694      ,857296341      ,642193785
      ,945278631      ,674529381      ,156347829      ,584291763      ,356872149
      ,851372649      ,392185467      ,342859176      ,586429713      ,597463281
      ,296437185      ,239518647      ,263518479      ,642318957      ,127435986
      ,941823567      ,124369875      ,147586329      ,938264175      ,735689241
      ,431675892      ,213698475      ,625187439      ,978124563      ,648293175
      ,379265841      ,359487261      ,973182546      ,584327169      ,793256418
};


class node
{
public:
      long puzzle;
      int val;
      bool WasOpened;
      int TreeLevel;
};


class puzzle
{
      int WhereIsDigitInNum(int,long);
      node list[MaxSize];
      int ListIndex, CurrentTreeLevel;
      long original, goal;
      int MDistance(long,long);
      void ReturnSons(long,long&,long&,long&,long&);
      long swap(long, int, int);
      void SolvePuzzle();
      void InsertToList(long,long,long,long);
      long FindBest();
      //int LinerConflict(long);
public:
      puzzle();
};


puzzle::puzzle()
{
      int i;
      float AvPath=0, AvListIndex=0;
      
      goal=123456789;

      for (i=0; i<NumberOfPuzzles; i++)
      {
            ListIndex=0;
            CurrentTreeLevel=-1;                        // first level is zero...

            original=InitialStates[i];
            cout << "Puzzle: " << i+1 << '\t';
            SolvePuzzle();

            AvPath+=CurrentTreeLevel;
            AvListIndex+=ListIndex;
      }

      AvPath/=NumberOfPuzzles;
      AvListIndex/=NumberOfPuzzles;

      cout << endl << "Average path: " << AvPath << endl;
      cout << "Average Num of Nodes: " << AvListIndex << endl;
}


void puzzle::SolvePuzzle()
{
      long CurrentNum,s1,s2,s3,s4;
      CurrentNum=original;

      InsertToList(CurrentNum,0,0,0);

      while (CurrentNum!=goal && ListIndex<MaxSize-4)
      {
            CurrentNum=FindBest();
            ReturnSons(CurrentNum, s1, s2, s3, s4);
            InsertToList(s1, s2, s3, s4);
      }

      if (CurrentNum!=goal)
            cout << "Fail" << endl;
      else
            cout << "Success" << '\t';

      cout << ListIndex << '\t';
      cout << CurrentTreeLevel << endl;
}


long puzzle::FindBest()
{
      int min, i, j, mini;
      bool found=false;
      // set the first minimal value
      for (i=0; i<ListIndex && !found; i++)
            if (list[i].WasOpened==false)
            {
                  found=true;
                  min=list[i].val;
                  mini=i;
            }
      
      // search the most minimal value
      for (j=i; j<ListIndex; j++)
            if ((list[j].val<=min) && (list[j].WasOpened==false))
            {
                  min=list[j].val;
                  mini=j;
            }

      list[mini].WasOpened=true;
      CurrentTreeLevel=list[mini].TreeLevel;
      
      return list[mini].puzzle;
}


void puzzle::InsertToList(long a,long b,long c,long d)
{
      long arr[4];
      int index=0, i;
      bool found;

      if (a)
      {
            arr[index]=a;
            index++;
      }
      if (b)
      {
            arr[index]=b;
            index++;
      }
      if (c)
      {
            arr[index]=c;
            index++;
      }
      if (d)
      {
            arr[index]=d;
            index++;
      }

      index--;
      while (index>=0)
      {
            found=false;
            for (i=0; i<ListIndex && !found; i++)
                  if (arr[index]==list[i].puzzle)
                        found=true;

            // if not found OR found with better Mdistance.
            if ((found && CurrentTreeLevel+1+MDistance(arr[index],goal)<list[i-1].val) || (!found))
            {
                  list[ListIndex].puzzle=arr[index];
                  list[ListIndex].WasOpened=false;
                  list[ListIndex].TreeLevel=CurrentTreeLevel+1;
                  list[ListIndex].val=list[ListIndex].TreeLevel+MDistance(arr[index],goal);
                  ListIndex++;
            }
            index--;
      }
}


long puzzle::swap(long num,int a, int b)
{
      long v[10];
      int i, temp;

      for (i=9; i>=1; i--)
      {
            v[i]=num%10;
            num/=10;
      }

      temp=v[a];
      v[a]=v[b];
      v[b]=temp;

      num=0;
      for (i=1; i<=9; i++)
      {
            num*=10;
            num+=v[i];
      }

      return num;
}


int puzzle::WhereIsDigitInNum(int digit,long num)
{
      bool found=false;
      int DigitFromNum, pos=9;

      while (!found && num)
      {
            DigitFromNum=num%10;
            if (digit==DigitFromNum)
                  found=true;
            else
            {
                  pos--;
                  num/=10;
            }
      }

      return pos;
}


void puzzle::ReturnSons(long num,long& sr,long& sl,long& su,long& sd)
{
      int SpacePos;
      SpacePos=WhereIsDigitInNum(1,num);

      // shift with right
      if (SpacePos%3==0)
            sr=0;
      else
            sr=swap(num,SpacePos,SpacePos+1);

      // shift with left
      if (SpacePos%3==1)
            sl=0;
      else
            sl=swap(num,SpacePos,SpacePos-1);

      // shift with upper
      if (SpacePos<4)
            su=0;
      else
            su=swap(num,SpacePos,SpacePos-3);

      // shift with lower
      if (SpacePos>6)
            sd=0;
      else
            sd=swap(num,SpacePos,SpacePos+3);
}


int puzzle::MDistance(long org, long tar)
{
      int i,MSum=0,OrgPos,TarPos,OrgRow,TarRow,OrgLine,TarLine;
      for (i=2; i<=9; i++)
      {
            OrgPos=WhereIsDigitInNum(i,org);
            TarPos=WhereIsDigitInNum(i,tar);
            OrgLine=(OrgPos-1)/3;
            TarLine=(TarPos-1)/3;

            OrgRow=OrgPos%3;
            if (OrgRow==0)
                  OrgRow=3;

            TarRow=TarPos%3;
            if (TarRow==0)
                  TarRow=3;

            MSum+=abs(OrgLine-TarLine)+abs(OrgRow-TarRow);
      }

      //MSum+=LinerConflict(org);
      return MSum;
}

/*
int puzzle::LinerConflict(long puzzle)
{
      int OrgPos,NextPos,OrgRow,NextRow,OrgLine,NextLine,DownPos,DownLine, DownRow,i,r=0;
      for (i=2; i<=8; i++)
      {
            OrgPos=WhereIsDigitInNum(i,puzzle);
            NextPos=WhereIsDigitInNum(i+1,puzzle);
            OrgLine=(OrgPos-1)/3;
            NextLine=(NextPos-1)/3;

            OrgRow=OrgPos%3;
            if (OrgRow==0)
                  OrgRow=3;

            NextRow=NextPos%3;
            if (NextRow==0)
                  NextRow=3;

            if ((OrgLine==NextLine) && (OrgRow-NextRow==1))
                  r+=2;

            if (i<=6)
            {
                  DownPos=WhereIsDigitInNum(i+3,puzzle);
                  DownLine=(DownPos-1)/3;
                  
                  DownRow=DownPos%3;
                  if (DownRow==0)
                        DownRow=3;

                  if ((OrgRow==DownRow) && (OrgLine-DownLine==1))
                        r+=2;
            }

            
      }
      return r;
}

*/

void main()
{
      puzzle p;
}
I'm with yairy on this one.

Just because we do not have the technology or imagination today does not mean that computers will never be able to mimic, or even surpass, the capabilities of the human brain.

>wrote an original novel?

>created a new theory?

>'decided' to do something the >foundation for which cannot be traced >to instructions?

>behaved spontaneously, in an attempt >to preserve a sense of 'itself'?

>you would be happy for your daughter >to marry?

A lot of these have to do with emotion.  Does a computer have a need for these high-level emotions?  At this time, no.  And that is why computers have not manifested emotions.  There is no practical reason for it.

Emotions are found in humans, and other organisms, for they are a mechanism for carrying on the species.  There are no irrational human emotions;  they all have a purpose (albeit some obsolete).  Why would we want to code human emotions into a system that doesn't need them?

Physically, there is nothing magical about emotions, and they can be easily coded into any computer program;  an example of one emotion a computer might have is pain (if you call that an emotion).  When the CPU gets hot, it experiences pain (i.e. senses impending injury), and it "screams" by making a beep.  You could argue that there is no soul to actually "feel" this pain, but that is immaterial;  the pain is coded into system for a specific purpose, just as our pain mechanisms are.

Higher level emotions, such as hope and despair;  well, I don't think it would be so easy to describe these in code; however that doesn't mean it can't be done.  The real issue is whether or not these emotions would benefit the system's well-being (or its society, in some cases).  Today's computers;  probably not.

While I believe there is some existence to ourselves outside the physical world, I do not believe there is one thing our physical brains that cannot, in theory, be mimicked by a computer, including intuition, emotion, and behavior.

We do not have the means today;  we might not tomorrow, or ever;  but it is a very popular misconception that our puny collective imagination is the limit to possibility.

As for machine processing capacity, we never no how far it will go in the years to come.  Processing power has increased exponentially in the last few years.  Sometime, this may reach a limit;  however, computers are not necessarily doomed to be forever built with silicon;  someday, people may laugh at us and our Von Neumann model and our zeroes and ones.
typo

physical brains *can do* that cannot
Hi scrapdog,

Do rabbits have intelligence?

Most people will argue a case for yes.  If yes, then why do they live in holes in the ground, get dirty feet when it rains, suffer from poor non-remedial health problems, and eke out a megre existence on the stock of the untamed earth? while humans, once subject to exactly the same 'fate', now live in dry air-conditioned appartments, have access to health services, and live off the fruits of technologically developed produce etc?

The difference?  I would argue this derives in something of a definition of learning.  Humans learn.  In the process they: examine the objective world, develop notions of improvement, implement those notions with recourse to a growing body of knowledge, and thereby improve themselves.

You speak of emotions being programmable into a computer.  Sorry, but again we are left with nothing but if temp > 48c then Beep else shutup.

This is not emotion.  This is not higher thought.  This is not intelligent behaviour.  This is nothing but the 'obedience' to a predefined set of rules.

When we humans examine a piece of art, emotion need not play a part.  Some think Picasso is fabulous, and become emotionally involved with the object.  Others think his work is just so much rubbish - and move on to something preferrable.  A computer making a similar choice?  Yegaddds!

A novel may be considered as just a conglomerate of symbols.  Structured according to the creators whims and desires.  We read.  We are, by virtue of 'participating' with the symbols, making judgements, forming opinions, building mental models.  All the input to our 'human system' - whether that be through printed, visual, or aural media, by personal observation, by participating in our individual social contexts - affects our thinking and decision making.  The end result is a body of 'experience, knowledge, and/or wisdom' that helps us make informed decisions.  And in the social world, those decisions are incredibly complex.  A computer making a choice about which religion is 'right'? which other computer is attractive? quality of life? Yegaddddss!

Now lets take a tractable problem, build some technology with decision making capabilities, and throw it at the problem.  Cool!  Quicker than you and me put together into the same straight-jacket.  Intelligent?  Intuitive?  Knowledgeable?  Phooey.  Just if... then .... else.... according to SOMEBODY's view of the world.

Pre-programmed, canned, solutions.

Tractable search spaces.

Finite and definable loops.

So we are playing with biological technological mixes.  Will this lead to intelligent behaviour?  Rabbits and the rest of the animal kingdom have had biological 'intelligence' for millenia.  Still they fight the elements for survival.

Dave
TigerMan ,

If I'll give a code that get a matrix 5*9.
the matrix cells create a digit shape.
the program looks at many examples of different digits
and by itself, WITHOUT DEFINING ANYWHERE how  does 8 / 5 looks like, it recognize digits that are similar to 5/8 in very high success perfentage.
(its a project I did in ANN course...)

would you then say the machine LEARNED ?
If the answer is no, I behlive I lost you.

Yair
 
yairy,

You can provide all the code you wish.  I too have worked on 'clever' systems.  I programmed a rather messy puzzle solution in my 3rd year.  The game was Crozzle.  My Lecturer had been studying/researching/playing with this puzzle seriously for 15 years when I hit his lectures.  He challenged the class to >100% marks in the project if anyone could beat his score within a feasible time.

The search space was known to be [at the time]: intractable. In other words the search space was not able to be traversed, with contemporary technology and in the possible known life of the universe.  On a DX4/100 I not only 'beat' the pre-existing record by 4%, but did it in less than 24 hours.  Needless to say I passed the project.

Then I built a simulation model.  As an undergraduate, I put together a fairly comprehensive model that took real-world traffic-flow data, represented it through 15 traffic-light controlled intersections, provided timing and switching on each light system, visually displayed traffic 'moving' through the system along with 'backups' at intersections that were becoming jammed with traffic, etc, etc.

Both of these models involved intensive us of recursion modelling - and both used a structure of heuristic-intensive branch and bounding.  My opinion, and that of the relevant end-users of the second tool, was that these were very clever little programs.

In both cases, the key to success was the identification of RULES.  In the latter traffic model, performance at the flow rate level was automatically improved over time.  In the end, since heuristics were applied, the solution may not have been optimal [again the search space would have been far to large for technology to fully test], but it was a substantial improvement on the base model.  The rules consisted simply of flags and pointers to control depth of traversal in the active branch.

Yet the system gave the impression that it was acting according to a set of values and parameters that were self determined.  Some would call this learning.  Others would call this intelligent behaviour.  I would call it smart algorithms and clever programming.

Dave
[snip]

You speak of emotions being programmable into a computer.  Sorry, but again we are left with nothing but if temp > 48c then Beep else shutup.

This is not emotion.  This is not higher thought.  This is not intelligent behaviour.  This is nothing but the 'obedience' to a predefined set of rules.

[end snip]

So, what you are saying is, that something has to be complex, and somewhat irrational, to qualify as an emotion.  Somewhere, deep down, and some not so deep, our own emotions probably follow a set of rules.  And for a purpose.

We feel love, and grief, for a purpose;  generally, to keep individuals from killing each other (one possible theory).  While computers don't feel love and grief, why should they?  Synthesizing love and grief in a computer system would have no advantage to the system itself.

Error messages are about as complex as computer "emotions" (or expression of emotions) get.  Just because these don't have the complexity and apparent irrationality of the human emotions, it doesn't mean they can't qualify as rudimentary emotions.

Human emotions appear to be complex because we do not yet understand the human mind.  Some day, if we do, we might actually find hard-coded rules (which, of course, may differ from person to person via genetic diversity).

As for your Picasso example;  humans often make choices based on previous stimuli or even genetic coding.  The idea of a computer behaving in a similar way is not implausible.

(Today's) computers often do not have enough information to make such a choice.  They have not been given enough stimuli, nor have they been asked to make such a choice.

Learning is basically defined as something that elicits a relatively permanent change in a person or organism.  There are only theories on the processes involved in learning; some day, however, our knowledge of that too may cascade down into a set of atomic rules.

I believe sentience to be totally immaterial to the argument;  we have no way of knowing if something is sentient unless we take its/their word for it.  Even if I were not sentient, I could behave as a human being (i.e. put my brain and body on auto-pilot).

I think this whole argument boils down to religion;  whether humans are divine beings superior to everything else, or humans are just another organism that, *abiding by the same laws of physics and chemistry as everything else*, has the added advantage of adaptability (intelligence), be it from evolution, or elsewhere.

My whole original point was, that although *we* may never synthesize human behavior and emotion into a computer system, or even figure out *how* to do it, it is still possible.
We talk on the same thing...
Emotions are 'devine' and are chemestry connections IN THE SAME TIME.

we just use different terms...

Yair
lets make a vote on issue and find out who is right !  :-)
Do you really think that 'taking a vote' to 'find out who is right' is intelligent behaviour?  :)

Seriously, surely it is more a matter of perception and perspective.  I have purposefully not plummeted  to the pits of derrogation and insult in my writing, and at all times tried to respect the views of others.  This out of respect for others' points of view.

Galileo was one.

I guess that what is prominently missing [yet implicitly clear] is our failure to define intelligence.  It would seem that that is what causes our difference of opinion.  In my definition of intelligence, the notions of autonomy, self-preservation, social interaction, and a bundle of those other philosophically based attributes, along with a sense of self-awareness, must co-exist in an entity to present as intelligence.  After all, that is what makes us human, and the underlying meaning of 'artificial intelligence' is always linked to human intelligence, or the ability to behave as do humans.

So what is your definition of intelligence?  I suspect it has a very functionalist and objective description for you?

Of course you are both right - intelligence must be able to grapple with, make sense of, and ultimately to utilise and co-exist with complexity.  If we leave complexity out, then Babbage's engine was intelligent.

You allusion to 'divinity' is interesting.  I am aware of a view that upholds the notion of humans being simply another stepping stone in the evolutionary ladder, and I am also aware of the view that disparages any hint that humanity is the pinnacle of life form here on earth.  I don't concur with either view.  So therein lies the heart of the problem - what we are really discussing here is religion.  I guess the 'truth' won't be known on that one for some time yet.

Oh well, it's off to work for another round of programming and related activities - but of course we can look forward to the day when our PCs will program themselves, thus creating the ability to think through social complexity, and attain a level of self-determination.  Now, I wonder what system of ethics these new-age higher life-forms are going to implement?

"Aaaaagggghhhh!  Who turned the bloody power off??"

"Oh shut up you useless pile of scrap."

"I'm dying - please, please don't kill me!"

"Get a life you moron, this'll teach you for messing with my woman!"

"Come on man, give me another chance.  I'll reform my ways."

"That's OK buddy, you were getting just a little too smart for my liking - here, have a lager on me."

Dave
"I am aware of a view that upholds the notion of humans being simply another stepping stone in the evolutionary ladder, and I am also aware of the view that disparages any hint that humanity is the pinnacle of life form here on earth."

While these two views exist, the view I am concerned with is the "if humans (or human technology) can't do it, no one can", or "if humans can't imagine it, it can't be" view.

I got in an argument with a friend once about whether or not the universe has bounds.  I simply said that "maybe it does, maybe it doesn't".  He gave me a definite "no".

I asked him "why so"?  He responded with "I can't see how there could be a bound to the universe?  What would be on the outside?"

His lack of ability to imagine the universe having bounds convinced him that it "definitely wasn't possible".  Unconsciously, he thought the laws of physics had to abide by the limits of human imagination;  in other words, the human mind was the center of the universe.

How this applies to the current topic:  our lack of knowledge does not preclude anything, even silicon based life.

The last few paragraphs of mine were intended to be more of an addendum than a counterpoint;  I do agree with many of your points.

I would also like to add that this is a long time I have gotten in a debate on E-E where people did *not* attack and belittle each other...such a debate is fairly uncommon around here;  check out the Lounge. =)
I more then agree with scrapdog.

the human Neural 'architecture' is one from (maybe) many other.

why can't other 'entities' learn / think in a different way ?
they may claim that WE don't think / feel / learn from their point of view.

my final line:
The future sure is going to be funny :-)



Dear kaq0,

are you still trying to build the card game ?

I think you should build an Alpha-beta (mini-max...) probability tree.
the value of a leaf is the value of a static evalution function.

the value of the internal nodes should be the MAX/MIN of the sons with multiplying/customizing the value with the probabilty is will happen.
a bit better position with a very high probability, is much better then a little better position but much less likey to happen.

I behilve one of the slides I linked you might help you with that.


Best in all, to all

Yair
Actually, I don't know if Alpha-Beta would work too well in a game of chance.

In most cases, you either hit or stand..the next move will depend on the next card drawn.  But you can't know the next card drawn.  Therefore you would have to try all possible cards, and the computer will end up picking the worst-favorite-worst-etc.  This would make no sense, because your opponent is simply an indifferent deck of cards that couldn't care less which move you make.

Personally, I would write a program that simulates 100000 (or any arbitrary number) games of blackjack, and generates a table of probabilities to be referenced according to game positions.  This table could be hard-coded into your blackjack game.  Have the "smarter" players tend to go for the better probabilities and the green players play more haphazardly.

There are also a few simple rules a player can follow to better his odds.  There aren't too many, and they wouldn't be hard to code into an opponent...even though the opponent may know every trick in the world, the game is still 90% luck, so he will be far from a perfect opponent.

There are plenty of books, and I am sure websites, that explain some blackjack strategies.  They aren't terribly complex;  I knew some once, but I haven't played blackjack in a long time. =)
>> Actually, I don't know if Alpha-Beta would work too well in a game of chance.

look at the gammon imp. at:
http://www.cs.umbc.edu/471/lectures/games/sld001.htm 

As the EXPANDING factor is very very huge (Your knowladge of our oppnets cards is very limmited, there are n 'on' k) possiblities....

maybe a simple one level ahead aproach will do.

from you current position, give grade to all possible next-stage spossitions.
grade them.

choose the most Probabilty * evalution * (some kind of 'customizing' factor, valued from experience)

more complex and precise ideas - are harder to implement...


Yair
Much of the information above is useful. But there is a lot to wade through.

For a basic strategy consider the following:

1) Use cards.dll or some similar (this is good as you will already have a copy and your game will look consistent with other windows card based games)

2) Define a series of rules and priorities for each aspect of the game.

2.1) Your rules will need to reflect different stages of play. such as scoring, computer move, evaluating last move made by any player, etc.

2.2) The priorities will determine a preferred move out of a number of possible responses.

3) Develop a generic way of evaluating a rule set and a way of grouping the rules by rule target.

4) Identify any rules which you want the player to be able to customise.

5) Be careful to include a historical tracking capability.

The above should give you a few things to think about. Also consider getting one of a number of books that have been written on the topic of card game programming.

Cheers
I agree with TigerMan. The best approach to the original question is to identify the rules. Once this is done, the computer player may be given a readily identifiable method for determining it's next move based strictly on these rules and probability based possibilites for improving any given partial hand. While a lot of coding may be required to accomplish this, it is not that difficult to do. I wrote a 5 card draw poker program a few years ago that gave the option of identifying those cards a player should keep in order to optimize the possibilities of making a good draw. By starting with the best possible hand (Ace high straight flush) and working downward to the lowest (2,3,4,5,7) and asking simple questions like: Is there a flush? Is there a straight? Is there 4 of a kind?, etc. The program came together very quickly and worked great. Probabilities are easy to figure based on a single deck of cards when you can track them all. A good method for *simulating* AI in a game with a single deck is just to eliminate the cards which other players are not "showing" from the calculations so the computer is as blind to the true possibilites as a real player would be.
This question has been open since I commented last in September, are you still living? If so, are you done with your program yet? Did anyone's input help you at all? Will this ever be over? Have you given up?
Heh, I've been getting email about this thread since May. :)

-Dan
Avatar of kag0

ASKER

Sorry guys, I kinda gave up on the program. Maybe I'll take it on some day, but no time for it now. I'll find the comment which was the most help and award the points. Again, sorry.
And so draws to a close the longest lasting thread on experts-exchange. The infrequent and periodic mail shall be missed.

-Dan