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
