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 20266 days, 20 hours, 18 minutes ago.