Download or view Deducer.frink in plain text format
/** This file contains classes, interface definitions, and algorithms for
implementing a general deducer system that can solve problems / games
like Mastermind, Wordle, Jotto, etc.
To implement a problem or game, you will need to implement DeducerProblem,
DeducerRank, and DeducerMove for that problem. Currently, this involves
implementing 5 methods, 3 of which are trivial (two toString, one equals),
and the other two consist of 1.) enumerating all possible plays for the game
and 2.) ranking a move.
The Deducer class contains methods to manage the state of a game, to
eliminate possibilities, to return possible moves, and to perform moves.
For a sample implementation of the Mastermind game using this framework,
see mastermindDeducer.frink
*/
class Deducer
{
/** A DeducerProblem that represents the current problem or game. */
var problem
/** The remaining options in the game. This is undef before initialization
and an array otherwise. */
var options
/** Construct a new Deducer for the specific problem type. */
new[problem is DeducerProblem] :=
{
this.problem = problem
this.options = undef
}
/** Apply a move and reduce the number of remaining options. This takes a
move and its associated rank and keeps only the remaining moves that
return the same rank. The move should be an appropriate DeducerMove
for the DeducerProblem. */
doMove[move is DeducerMove, moveRank is DeducerRank] :=
{
if options == undef
initialize[]
res = new array
// Now test each move and see if playing that move gives the same
// rank as playing this move. If so, keep it.
for target = options
if problem.rank[move, target].equals[moveRank]
res.push[target]
options = res
}
/** Returns the number of remaining moves */
numMovesRemaining[] :=
{
if options == undef
initialize[]
return length[options]
}
/** Returns the moves remaining as an array of DeducerMove. */
movesRemaining[] :=
{
if options == undef
initialize[]
return options
}
/** Removes a random move from the moves remaining and returns it. */
removeRandomMove[] :=
{
if options == undef
initialize[]
return options.removeRandom[]
}
/** Picks a "smart" move from the moves remaining and returns it. The
"smartness" of the rule is determined by the implementation of
DeducerMove.compareTo[other]
*/
pickSmartMove[numToTest=100] :=
{
if options == undef
initialize[]
bestIndex = undef
bestMove = undef
len = numMovesRemaining[]
num = min[numToTest, len]
chosenIndex = 0
for i=0 to num-1
{
if numToTest >= len
chosenIndex = i // We're exhausively testing all items
else
chosenIndex = random[0, len-1] // We're testing random items
move = options@chosenIndex
if bestMove == undef
{
bestMove = move
bestIndex = chosenIndex
} else
{
cmp = bestMove.compareTo[move]
// If other is better, replace it.
// If both moves are the same, replace at random.
if (cmp == -1) or (cmp == 0 and random[0,1] == 0)
{
bestMove = move
bestIndex = chosenIndex
}
}
}
return options.remove[bestIndex]
}
/** Returns the remaining moves as an array of strings. */
movesRemainingStr[] :=
{
if options == undef
initialize[]
res = new array
for move = options
res.push[move.toString[]]
return res
}
/** Initialize all options. */
initialize[] :=
{
options = toArray[problem.allPossibleMoves[]]
}
/** Resets back to starting state. */
reset[] :=
{
options = undef
}
}
/** The DeducerProblem class describes an interface that is used to describe
a problem or game. */
interface DeducerProblem
{
/** Rank/score a particular move with respect to target and return an object
of type DeducerRank */
rank[move is DeducerMove, target is DeducerMove]
/** Return all possible moves as an array or enumerating expression of
DeducerMove appropriate for this problem. */
allPossibleMoves[]
}
/** The DeducerRank interface describes the methods for ranking a particular
move. For example, a Mastermind ranking would include the count of black
and white pegs. For Wordle, this would indicate which letters are green,
which are yellow, and which are black. */
interface DeducerRank
{
/** Compares this rank with another rank and returns true if they are equal.
*/
equals[other is DeducerRank]
/** Returns a string representation of the rank for display to a human. */
toString[]
}
/** This represents a move for the particular problem or game. */
interface DeducerMove
{
/** Compares the value of this move to another move in an attempt to pick a
"smarter" move. For example, if a Wordle guess has more different
letters, it would probably be considered a "better" guess.
The function should return -1 if "this" move is worse than other,
0 if both moves are equally good,
1 if this move is better than other.
(This is what is returned by the <=> three-way comparison operator.)
If you don't really have a heuristic as to which guess is "smarter",
this can just always return 0.
*/
compareTo[other is DeducerMove]
/** Returns a string representation of the move suitable for presenting to a
human. */
toString[]
}
Download or view Deducer.frink in plain text format
This is a program written in the programming language Frink.
For more information, view the Frink
Documentation or see More Sample Frink Programs.
Alan Eliasen was born 20217 days, 15 hours, 9 minutes ago.