Crossposted to wordgame-programmers and quackle... I've been chatting with [EMAIL PROTECTED] (who is on the Quackle list but I don't think is a member of wordgame-programmers) about my Global Analysis algorithm that I posted here (=wgp) too many years ago. He pointed out that it didn't take into account any form of opponent modelling to determine the opponent's rack leave/carry over into his next rack.
So here are some quick notes on an idea I've come up with for opponent modelling that takes advantage of the global analysis algorithm: We have just played and picked up our replacement tiles. While waiting for the opponent, we do a GA on his behalf. This gives us a list of all possible replies from the opponent, and their scores. Then when he plays, we remove from the precomputed play list all those plays which came from a rack that he could not have held, as determined by the tiles he put down. We now have a list of possible racks he might have been holding plus knowlege of the actual word played. For each possible rack, we compare the best move available for that rack to the actual move; the nearer the highest score is to the actual score, the higher the probability that this was the rack he held. The more disparate the score, the less likely. Subtracting the tiles he placed from the possible racks he may have held, ordered by probability, directly gives us the opponent's possible rack leaves, ordered by probability. (Or at least a crude approximation to probability, due to modelling the opponent as a naive algorithm.) Now it is our move again, and we calculate the opponent's replies to our many potential plays using global analysis as usual, but we modify the probability of each of his moves by the probability of that move's rack-leave. Most of the work for our opponent-modelling calculation was done on the opponents time with only a quick sweep of a list being done after he plays in order to analyze the results. Doing more modelling of the opponents algorithm at this point is likely to exhaust our time. It is axiomatic that we can *never* have as much time to model our opponent's moves as he has to make his moves, all other things (like CPU speed) being equal, as we have to work on our own move as well as try to duplicate his decision-making process with the same length of time as he has to merely make his own decision. If his algorithms in turn try to take ours into account, we have a case of infinite recursion. At some point we will run out of time modelling the modelling of the modelling, ad nauseam. Trying to do so must lead to a horizon effect. So the simple solution is to model the opponent relatively naively - just looking for missed bonuses for example, only pushing down deeper on lesser scoring plays if we can work out when it is worth doing, which may not be easy. Maybe Mark Richards who has done some work on opponent modelling using Quackle's codebase could comment on whether the above makes sense or is too naive? (hence the crosspost to the quackle list; could you include [EMAIL PROTECTED] in your followup please?) G PS If you haven't read the Global Analysis idea, here's my write up: http://www.gtoal.com/wordgames/scrabble_solver/analysis.html The only major change to it that I need to put in (it's unedited since I first posted it in Y2K!) is a correction to the maths that came about after a long discussion on this group (i.e. ignore the code in the link and use this instead: http://www.gtoal.com/wordgames/scrabble_solver/fixedprob.c.html ) Also tcheq has given me some good input which will come in handy for a rewrite.
