Re: [Bug-gnubg] gnu gammon question

[Russ Allbery]

Nicholas Suplizio <address@hidden> writes:

> Thank you for your help. So far I don't think anything like what I'm
> looking for exists. I do quite a bit of programming but I've never taken
> on a project like developing a Gin Rummy evaluator before. The most
> valuable part of GNUBG to me is the hint feature and I'd like something
> similar for Gin. Any recommendation as to where I may read up on how
> something like that is designed? I was told it had something to do with
> "combinatorics". Could you provide further guidance of material that may
> help me with this project?

The place where you'd start is building a mathematical model of the game.
Both backgammon and gin rummy are games with a substantial randomness
component, which means that your mathematical model is going to involve a
lot of probability calculations (unlike, say, chess or go, where it's
instead a pure positional evaluation and game tree problem).  That's where
the combinatorics come in.

The nature of the randomness is somewhat different for a card game like
gin rummy, however.  Backgammon has no hidden but knowable information.
The full state of the game is present and openly visible on the board, and
the only unknown factor (apart from opponent decisions) is upcoming die
rolls.  However, those rolls are *completely* random.

Gin rummy paints a more complex picture.  Quite a bit of important
knowledge is knowable but hidden, namely the complete list of all
previously-played cards.  Therefore, a computer player will be better than
any human player except one with perfect memory since a computer counts
cards perfectly and therefore can make full use of state knowledge about
the game that most humans will struggle to retain.

Similarly, the upcoming card draws in gin rummy are *not* completely
random.  They are skewed by the cards that have previously appeared.  The
ideal gin rummy player is constantly recalculating probability tables for
the likelihood of drawing various cards given the cards that have already
appeared in the game, and then making decisions based on probability of
outcomes given that game state.

All this means that a human backgammon player can compete with even very
good computer backgammon players better than a human gin rummy player can
compete with a computer gin rummy player that takes the simple step of
remembering the full game state, an operation that's trivial for a
computer but quite difficult for a human.  But in terms of writing that
computer player, the devil is in the math.  You would need to work out the
probability calculations of the likelihood of particular draws given
various card retention strategies, which is quite doable but which may
involve a fair bit of probability work.  Quite a bit more than backgammon,
since the amount of information that you have is much larger and the
randomness space is also much larger.

It's much more similar to writing a computer poker player than writing a
computer backgammon player.

-- 
Russ Allbery (address@hidden)              <http://www.eyrie.org/~eagle/>