I in fact meant that when the complement of the beginning deck and the cards dealt is continuous, the tree is symmetric.
On 2 March 2011 09:17, Justin Paston-Cooper <[email protected]> wrote: > Thank you to all for the suggestions. I found the essay on tree sums > to be really useful, and I've tried to apply it to my hi-lo problem. I > have written a function to generate all possible winning games. A game > is dealt from n cards of a single suit. The game starts with one card > being dealt. If there is an equal or greater number of cards which are > higher than the dealt card, then the computer predicts high, and deals > the next card. The same prediction continues to be done based on the > last card dealt until there are no cards left. Strictly speaking, the > game ends when there is only one card left, because there is no doubt > as to the outcome of the next deal, but I haven't dealt with that yet. > > Here is my code: > > NB. "n poss game" gives the cards that, if dealt in the next turn, > would result in a win based on the computer's prediction. n is the > size of the deck of one suit. > NB. a game is a list of cards dealt in sequence where the last card > dealt is the last in the list. > > poss =: ({:@:] (>@:{~ <:&:(#@:>)/)`(>@:{.)@.(1=#)@:(> </. ]) (-.~ > i.)~)`(0$0"0)@.(= #) > > NB. "n toRoot" tree takes a tree as in > http://www.jsoftware.com/jwiki/Essays/Tree%20Sum and a node number > and > NB. gives the path from the root to n where the root is in fact > omitted. This is useful for getting the node numbers of a > NB. game ending at a given node. One uses the node numbers to look up > the face values corresponding to the node > NB. numbers to get the game. > > toRoot =: ([ ,~ { $: ])`(0$0"0)@.(0=[) > > alg =: 3 : 0 > > NB. A list holding the number of cards at each node in the tree which, > when next dealt, would result in a lose for the computer > fail =: 0$0 > > tree =: ,: 0 > > NB. A stack of tree positions to which the algorithm should later > return to generate more games starting from the point at the top > stack =: ,: 0 > > NB. The face values corresponding to nodes in the tree > vals =: ,: _1 > > while. 0 < # stack > do. > > NB. If there is an item in the stack, get the game up until the point > at the top of the stack > > topStack =: {. stack > stack =: }. stack > game =: vals {~ topStack toRoot tree > > NB. What are the winning cards that could come next in a game of y cards? > p =: y poss game > numPoss =: # p > > if. numPoss > 0 > do. > > NB. If there are possibilities, add them to the stack > > vals =: vals , p > stack =: stack ,~ (# tree) + i. numPoss > tree =: tree , numPoss $ topStack > fail =: fail , 6 - numPoss > > else. fail =: fail , 0 > > end. > > end. > > ) > > NB. tsum_dfs is as in the Tree Sum essay. > > tsum_dfs=: 4 : 0 > e=. y (~: #"1 ,:) i.#y > while. {:$e do. > b=. e.~/e > 'p q'=. (-.b)#"1 e > j=. ~.p > x=. ((j{x)+p+//.q{x) j}x > e=. b#"1 e > end. > x > ) > > At the moment alg is rather slow even for games of size 9. I am aware > that when the list of possibilities for the next turn is continuous, > the tree for them is symmetric. I have yet to account for that. Could > anyone suggest how I might make it a bit faster otherwise? Should the > algorithm be changed in any fundamental way? > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
