Here is the current version of alg:
alg =: 3 : 0
fail =. 0$0
tree =. ,: 0
stack =. ,: 0
vals =. ,: _1
while. 0 < # stack
do.
topStack =. {. stack
stack =. }. stack
game =. vals {~ topStack toRoot tree
p =. y poss game
numPoss =. # p
if. numPoss > 0
do.
vals =. vals , p
stack =. stack ,~ (# tree) + i. numPoss
tree =. tree , numPoss $ topStack
fail =. fail , y - numPoss
else. fail =. fail , 0
end.
end.
tree;vals
)
When called as in "alg 4", the tree part is:
0 0 0 0 0 1 1 1 5 5 8 9 6 12 7 7 14 15 2 2 18 20 19 19 22 23 3 3 26 26
28 29 27 32 4 4 4 34 34 37 38 35 41 36 36 43 44
and the vals part is:
_1 0 1 2 3 1 2 3 2 3 3 2 3 1 1 2 2 1 2 3 3 0 0 2 2 0 0 1 1 3 3 1 3 0 0
1 2 1 2 2 1 2 0 0 1 1 0
If value n is at the mth position of the tree, it means that node m is
a descendent of node n. In particular, nodes 5, 6 and 7 are
descendants of node 1. The face value of the card corresponding to
node n is the value at the nth position of vals. Therefore we see that
the cards 1, 2 and 3 are descendants of card 0. I've put an
illustration of the game tree for a deck of four cards, at
http://img855.imageshack.us/i/gametree.png/ . It represents every
game, starting at -1, which really represents the empty game, which
the computer would win. The computer wins if all of its predictions
are correct, and we already know how it makes its predictions based on
previously dealt cards. To repeat, a game has a deck of n cards of a
single suit.
Ultimately I would like to generate the tree for 13 cards. I would
then, given a specific node in a tree, like to have the probability of
the computer's still winning n turns after that node in the tree. For
each node I would associate a value of 1 for its winning value, and
also I would associate the number of cards which, if dealt after that
node, would result in a contradiction of the computer's prediction.
That losing value is of course just (size of deck) - (number of
children) - (number of cards already dealt). I would then be able to
obtain a list of values where each row corresponds to the sum of
values at the nth level from that node. Then to get the probability of
the computer's winning n turns down the line, I would go to the node
associated to the last dealt card in the game, sum the first n-1
values to get a (win,lose) value and then take (win/win+lose).
At the moment I would like to focus on making the generation of the
tree a bit faster. The tree for 13 cards will be rather big, and I'm
wondering what kind of storage I should be using.
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
