Also I've just realised that my definition of fail in alg is incorrect. It should take account of the number of cards already dealt as well, so
fail =. y - numPoss - # game On 3 March 2011 11:24, Justin Paston-Cooper <[email protected]> wrote: > 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
