treedef.h

/* treedef.h
 * 19 Apr 2000
 * defining a game tree
 */

/* #include before: "rat.h" */

#define PLAYERS 3        /* no of players including chance              */
#define NAMECHARS 8      /* char[NAMECHARS] names infosets & moves      */
#define ROOT 1           /* first (=root) index of nodes[]              */
#define MAXRANDPAY 100   /* 1..MAXRANDPAY  are possible payoffs         */
/* LARGEST payoff could be as negative as MINUSINFTY,
 * used in  maxpayminusone()
 */
#define MINUSINFTY -30000
/*  char s[MAXSTRL]  should contain  rational, sequence name, movetuple */
#define MAXSTRL 100

/* first autoname char for iset */
extern char an1[];
/*  last autoname char for iset */
extern char an2[];

typedef struct node *    Node;
typedef struct iset *    Iset;
typedef struct move *    Move;
typedef struct outcome * Outcome;

typedef Rat Payvec[PLAYERS-1];  /* pay vector, player-1 saves space     */

struct node
    {
    Bool        terminal;       /* 0: decision node / 1: terminal node  */
    Iset        iset;           /* which information set                */
    Node        father;         /* node closer to root                  */
    Move        reachedby;      /* move of edge from father             */
    Outcome     outcome;        /* which outcome                        */
    /* will be generated by  genseqin()                                 */
    Move        defseq[PLAYERS];/* seq defd by node for each player     */
    };

struct iset     /* information set      */
    {
    /* given                    */
    int         player;         /* 0: chance player                     */
    int         nmoves;
    Move        move0;
    /* autoname possible                                                */
    char        name[NAMECHARS];        /* name of iset                 */
    /* will be generated                                                */
    Move        seqin;          /* sequence leading to that iset        */
    /* for NF computation                                               */
    int         ncontin;        /* how many strategy-type continuations */
    int         prefact;        /* multiplyer for later parallel isets  */
    };

struct move   /* move, also sequence ending in that move        */
    {
    Iset        atiset;         /* where this move emanates from        */
    Rat         behavprob;      /* behavior probability                 */
    Rat         realprob;       /* realization probability              */
    int         redsfcol;       /* column of reduced sequence form      */
    /* for NF computation                                               */
    int         ncompat;        /* number of compatible partial strats  */
    int         offset;         /* number of partial strats for moves   */
				/* to the right of this at same iset    */
    };

struct outcome
    {
    Payvec      pay;
    Node        whichnode;
    };

/* ------------- global variables ------------------------------------- */
/* game tree                                    */
extern  Node    nodes;          /* nodes of game tree   */
extern  Node    root;           /* &nodes[ROOT]         */
extern  Iset    isets;          /* information sets     */
extern  Move    moves;          /* moves & sequences    */
extern  Outcome outcomes;       /* outcomes             */
/* sizes of these arrays                                                */
/* first ILLEGAL pointer at the end of array nodes      */
extern  Node lastnode;
/* isets for player  pl:  firstiset[pl] ... firstiset[pl+1]-1       */
extern  Iset firstiset[PLAYERS+1];
/* moves for player  pl:  firstmove[pl] ... firstmove[pl+1]-1       */
extern  Move firstmove[PLAYERS+1];
/* first ILLEGAL pointer at end of array outcomes */
extern  Outcome lastoutcome;

/* number of sequences for each player          */
extern  int nseqs[PLAYERS];     
/* number of information sets for each player   */
extern  int nisets[PLAYERS];

/* alloctree:
 * after freeing space used for old tree,
 * allocate storage space for a game tree with 
 * nn  nodes    (determines  lastnode)
 * ni  isets    (determines  firstiset[PLAYERS] )
 * nm  moves    (determines  firstmove[PLAYERS] )
 * no  outcomes (determines  lastoutcome)
 */
void alloctree(int nn, int ni, int nm, int no);

/* ----------- generating derived tree data -------------------- */
/* checks perfect recall, returns 1 if there is a problem 
 * sets  sequence triples leading to nodes & seqin for isets
 * sets  nseqs[], nisets[]
 */
Bool genseqin(void);

/* next integer representing payoff, using MAXRANDPAY   */
int nextrandpay (void); 

/* normalize maximum payoff to players to -1
 * bprint:  announce current max payoffs to stdout
 */
void maxpayminusone(Bool bprint);

/* names  isets  using an1[pl]..an2[pl]
 * assume nisets[] set  by  genseqin()
 */
void autoname(void);

/* ----------- output routines --------------------------------- */
/*
 * convert  c  of player  pl  to string  s
 * c == NULL:  s = "*".  c == empty sequence: s="()"
 * o/w  iset's name + move no
 * returns length of string.  s must be long enough
 */
int movetoa (Move c, int pl, char *s);

/* convert sequence  seq  of player  pl  to string  s  
 * c == NULL:  s = "*".  c == empty sequence: s="." 
 * returns length of string.  s must be long enough
 */
int seqtoa (Move seq, int pl, char *s);

/* prints the raw tree data                     */
void rawtreeprint(void);