🚀 go-pugleaf

There are a couple of examples of the evolution of
game playing strategies in Koza's book (and movie),
but nothing too complex.

Angeline at Ohio state has tinkered with tic-tac-toe using
GP.



Rice.

On the BlackJack problem:

aIt might be knd of interesting to give as input the history of all
cards turned up in the game (current shoe). Emergent card counting!

Just a notion.

-- 
  Layne Ainsworth | lains@world.std.com <or> ...!{xylogics,uunet}!world!lains
	  The truth can't hurt you; it's just like the dark.

In article <LAINS.93Jan8190731@world.std.com>, lains@world.std.com (Layne L Ainsworth) writes:
|> 
|> On the BlackJack problem:
|> 
|> aIt might be knd of interesting to give as input the history of all
|> cards turned up in the game (current shoe). Emergent card counting!

   Yes, that should give a better playing strategy, but at a huge cost.
To make a hit/stay decision, you need to know the value of your hand and
some reasonable number of the cards that have appeared up to this point.  
This should always include the dealer's upcard and your two cards.  (Note that
I am not assuming any other players in the game.  I am also not allowing the
computer enough info to allow for splitting or doubling down, two things
you really need to use well to cut the bank's advantage.  I am ALSO assuming
that ONE deck is reshuffled after every play.  A three-deck shoe would make
these numbers worse.)  
This doesn't seem much more complicated than the original problem statement, 
but let's see:

   Item             Number of possiblilities
   Hand's value       9  (assume always stay on 19 and always hit on 10)
   3 cards seen        22,100       All of these numbers assume that
   4 cards seen        270,725       you have some nice way of storing the cards
   5 cards seen        2,598,960      compactly and non-redundantly.

  The algorithm has to be able to make a decision under any case:  3 cards known,
4 or 5.   If six cards are known, you might want to just assume that only 5 are,
and go with that.  Now....  each string must give a 1 or a 0 (hit/stay) for
each possibility.  That gives a total string length of
                                                             .
       9*(22,100 + 270,725 +  2,598,960) =  26,026,065 bits = 3.2 megs.

  You do NOT want to use strings this large.  you would need gigabytes
of quickly accessible memory during a run if you expect to sample a significant 
region of the problem space.

    Let me compare that with the string size for the original problem.

     Item             Number of possibilities
     Hand's value        9
     dealers upcard      52
     Is hand splitable?  2
      
    This gives only 9*2*52 = 936 bits per string, or 117 bytes.  That would
mean you could deal with a significant population size in about 500k total.
Even PC's can deal with this.

Rod

In article <1993Jan9.192644.24693@fcom.cc.utah.edu> freier@mail.physics.utah.edu (rodney james freier) writes:
>In article <LAINS.93Jan8190731@world.std.com>, lains@world.std.com (Layne L Ainsworth) writes:
>|> 
>|> On the BlackJack problem:
>|> 
>|> aIt might be knd of interesting to give as input the history of all
>|> cards turned up in the game (current shoe). Emergent card counting!
>
>   Yes, that should give a better playing strategy, but at a huge cost.
>To make a hit/stay decision, you need to know the value of your hand and
>some reasonable number of the cards that have appeared up to this point.  
>This should always include the dealer's upcard and your two cards.

It might be possible to allow some card counting without the huge costs you
assume.  For starters, one can make significant modification of the house
percentage just by counting aces, face cards, and 10s.  Additionally, one
advantage that blackjack has over card games such as poker is that the card
suit has no value.  A jack of diamonds is equivalent in all cases to a jack
of spades.  This means that you only need to keep track of 13 categories
with a value from 0-4, hence only 39 bits and not the 52 you mentioned.
You could even decrease this number by storing all cards with a value of 10
as a single number (now we are down to 32 bits, and only 8 bits to count
aces and cards with a value of 10.)
>
>    Let me compare that with the string size for the original problem.
>
>     Item             Number of possibilities
>     Hand's value        9
>     dealers upcard      52
>     Is hand splitable?  2
>      
>    This gives only 9*2*52 = 936 bits per string, or 117 bytes.  That would

Or we could try this:

cards in hand:	10 bits, 5 per card (values 0-16, suit is irrellevant)
dealers upcard: 5 bits

By ignoring suit you will be able to cut out a major amount of noise from
the strings you proposed.  We could even add the 32 bits necessary to count
a full deck as mentioned previously and still be way under the 936 bits you
suggest.  Then again, I could be missing something very obvious here...it
has been a long day... :)

jim




-- 
Jim McCoy          |  PGP 2.0 Key md5 hash:
j-mccoy@nwu.edu    |  61323c49024cb089337c78a05aafe8c6
mccoy@ils.nwu.edu  |  finger mccoy@ils.nwu.edu for public key

I'm surprised by this discussion of how to represent blackjack so a
genetic algorithm could solve it.  If you have to put that much effort into
getting the representation just right, it seems like you -- the humans -- have
already done the interesting learning.

(Equivalently, maybe the problem isn't simple.)

-Tom

   In Goldbergs book (on Page 108) is a set of five "standard"
functions (over the reals) to optimize.  These get around the
difficulty "How do I code blackjack?!?" by not being blackjack.
They're good for learning how to do GA's in an environment where
they are well understood and you know what will happen.  Goldberg
himself (in his book) will tell you what ought to happen :).

Dan
Danwell@IASTATE.EDU

In article <1993Jan8.202702.21180@fcom.cc.utah.edu>,
freier@mail.physics.utah.edu (rodney james freier) writes:
>   I'm looking for a few simple games/problems that can be played/solved
> genetically.  I'm just trying to practice with the concept.

  Just about any game with an evaluation phase can be done (chess, checkers,
tic-tac-toe).  Just have an alpha-beta search with node rating, and evolve
different ways to rate nodes.  I did this way back with connect-four.

  I think some of the top chess programs already do this.

>  The best
> simple project I've been able to come up with so far is generating a
> Blackjack strategy genetically.

  I tried this when I first thought of genetic algorithm games.  The problem is
that it has already been thouroughly mapped out, so at best you could only match
what is already known :-(

 |  __L__
-|-  ___  Warren Kurt vonRoeschlaub
 |  | o | kv07@iastate.edu
 |/ `---' Iowa State University
/|   ___  Math Department
 |  |___| 400 Carver Hall
 |  |___| Ames, IA  50011
 J  _____

kv07@IASTATE.EDU (Warren Vonroeschlaub) writes:

>In article <1993Jan8.202702.21180@fcom.cc.utah.edu>,
>freier@mail.physics.utah.edu (rodney james freier) writes:
*** Stuff deleted ***
>>  The best
>> simple project I've been able to come up with so far is generating a
>> Blackjack strategy genetically.

>  I tried this when I first thought of genetic algorithm games.  The problem is
>that it has already been thouroughly mapped out, so at best you could only match
>what is already known :-(

There are many variations of blackjack.  Such as one which used to be
played in the Las Vegas Club which allowed the player to buy back half of
his bet before he drew any cards.  A friend of mine James D. Pugh,
figured out a simple strategy where the player could (barely) have an
edge on the house.  An advantage of around 0.1%.  He has since died and
his strategy with him.  Seems to me that this idea could be the basis
for a GA.

In article <1993Jan11.145224@IASTATE.EDU>, kv07@IASTATE.EDU (Warren Vonroeschlaub) writes:
|>|> 
|>   I tried this when I first thought of genetic algorithm games.  The problem is
|> that it has already been thouroughly mapped out, so at best you could only match
|> what is already known :-(
|> 
|>
  Oh, that's ok.  I just wanted homework-type problems,  not senior project
problems.  I'm not looking to do any ground-breaking research.

Rod

In article <1993Jan11.145224@IASTATE.EDU> from [Mon, 11 Jan 1993 20:52:24 GMT] you wrote:
 > In article <1993Jan8.202702.21180@fcom.cc.utah.edu>,
 > freier@mail.physics.utah.edu (rodney james freier) writes:
 > >   I'm looking for a few simple games/problems that can be played/solved
 > > genetically.  I'm just trying to practice with the concept.
 > 
 >   Just about any game with an evaluation phase can be done (chess, checkers,
 > tic-tac-toe).  Just have an alpha-beta search with node rating, and evolve
 > different ways to rate nodes.  I did this way back with connect-four.
 > 
 >   I think some of the top chess programs already do this.

Really? I am highly interested in more information. What chess program does
use GAs? Any references?

 >  |  __L__
 > -|-  ___  Warren Kurt vonRoeschlaub
 >  |  | o | kv07@iastate.edu
 >  |/ `---' Iowa State University
 > /|   ___  Math Department
 >  |  |___| 400 Carver Hall
 >  |  |___| Ames, IA  50011
 >  J  _____

Thanks a lot,
Peter (bruhn AT uxe.wu-wien.ac.at)

In article <1993Jan12.120525@IASTATE.EDU> kv07@IASTATE.EDU (Warren Vonroeschlaub) writes:
# In article <7268265448-38850@exaia>, bruhn@exaia (Peter Bruhn ) writes:
# >In article <1993Jan11.145224@IASTATE.EDU> from [Mon, 11 Jan 1993 20:52:24 GMT]
# you wrote:
# >> In article <1993Jan8.202702.21180@fcom.cc.utah.edu>,
# >> freier@mail.physics.utah.edu (rodney james freier) writes:
# >> >   I'm looking for a few simple games/problems that can be played/solved
# >> > genetically.  I'm just trying to practice with the concept.
# >> 
# >>   Just about any game with an evaluation phase can be done (chess, checkers,
# >> tic-tac-toe).  Just have an alpha-beta search with node rating, and evolve
# >> different ways to rate nodes.  I did this way back with connect-four.
# >> 
# >>   I think some of the top chess programs already do this.
# > 
# >Really? I am highly interested in more information. What chess program does
# >use GAs? Any references?
#
#   I remember hearing that Carnegie Mellon's "Deep Thought" chess player had its
# position evaluater made by a GA (It was #1 in '90 or therabouts).  Can't give
# any references though, sorry.  Try looking in the procedings of the computer
# chess competitions at around that time.  Some others have done this too from
# what I've heard.

As I recall, the Deep Thought team did not use a traditional GA, but
instead employed a hill-climbing approach that provided simultaneous
optimization of several dozen positional evaluation parameter scalars.
The details can be found in past issues of the _ICCA Journal_ (for
subscription details, see the rec.games.chess FAQ or e-mail me).  The
optimization run was made using several thousand master level games
provided by a commercial database service.

I myself am a computer chessplaying program researcher and I am
working on the topic of machine learning in such programs.  My
approach does not use classical GA, but is instead based on "rule
pool" (cf. "gene pool") evolution where rules (pattern templates) are
automatically generated, applied, and scored.  Although I have a
reasonably strong working program, its rule pool subsystem is far from
complete.  However, I feel that this approach is superior to a
classical GA method because of the immense combinatorial numbers
involved in chess search and also because of some previous success
with rule pool evolution as part of an earlier NLP project of mine.

I am hesitent to go into details as much is still yet to be done.  It
may very well be that my particular rule pool approach is insufficient
for the chessplaying domain.  On the other hand, I consider it very
unlikely that any reasonable hardware (ca. US$1000) implementation
using unintelligent brute force has a chance against hardware like
Deep Thought and its multiple MHz node freqencies.  A world class
chessplaying program on a microcomputer must use some sort of
intelligence to hold its own against the special purpose machines.  I
feel that a rule pool method is the best approach; others may prefer
some sort of GA.

 [The above opinions expressed are my own; not necessarily held by others.]
      == Steven J. Edwards           Bull HN Information Systems Inc. ==
      == (508) 294-3484              300 Concord Road         MS 820A ==
      == sje@xylos.ma30.bull.com     Billerica, MA 01821          USA ==
"That Government which Governs the Least, Governs Best." -- Thomas Jefferson

In article <7268265448-38850@exaia>, bruhn@exaia (Peter Bruhn ) writes:
>In article <1993Jan11.145224@IASTATE.EDU> from [Mon, 11 Jan 1993 20:52:24 GMT]
you wrote:
>> In article <1993Jan8.202702.21180@fcom.cc.utah.edu>,
>> freier@mail.physics.utah.edu (rodney james freier) writes:
>> >   I'm looking for a few simple games/problems that can be played/solved
>> > genetically.  I'm just trying to practice with the concept.
>> 
>>   Just about any game with an evaluation phase can be done (chess, checkers,
>> tic-tac-toe).  Just have an alpha-beta search with node rating, and evolve
>> different ways to rate nodes.  I did this way back with connect-four.
>> 
>>   I think some of the top chess programs already do this.
> 
>Really? I am highly interested in more information. What chess program does
>use GAs? Any references?

  I remember hearing that Carnegie Mellon's "Deep Thought" chess player had its
position evaluater made by a GA (It was #1 in '90 or therabouts).  Can't give
any references though, sorry.  Try looking in the procedings of the computer
chess competitions at around that time.  Some others have done this too from
what I've heard.

 |  __L__
-|-  ___  Warren Kurt vonRoeschlaub
 |  | o | kv07@iastate.edu
 |/ `---' Iowa State University
/|   ___  Math Department
 |  |___| 400 Carver Hall
 |  |___| Ames, IA  50011
 J  _____