Escape from Monkey Island Monkey Kombat advisor/"calculator"

dominances.dot

digraph {
	aa, cc, dm[color=green];
	bb, gg[color=blue];
	aa, bb, cc, dm, gg[shape=round];

	dm -> cc[color=cyan];
	dm -> aa[color=cyan];
	aa -> cc[color=cyan];

	aa -> gg;
	bb -> aa;
	cc -> gg;
	gg -> bb;
	gg -> dm;
	cc -> bb;
	bb -> dm;
}

MonkeyKombat.py

#!/usr/bin/env python3

import asyncio
import typing
from pathlib import Path

import networkx as nx
from plumbum import cli
from prompt_toolkit.patch_stdout import patch_stdout
from prompt_toolkit.shortcuts import PromptSession


def importGraph(cls: typing.Type[nx.Graph], fn: Path) -> nx.Graph:
	g = cls(nx.nx_pydot.read_dot(fn))
	g.remove_node("\\n")
	g.remove_node(",")
	return g


class Move:
	__slots__ = ("transition", "pose", "minRespPoses", "heur")

	def __init__(self, transition: str, pose: str, minRespPoses: typing.Set[str], heur: float):
		self.transition = transition
		self.pose = pose
		self.minRespPoses = minRespPoses
		self.heur = heur

	def __repr__(self):
		return self.__class__.__name__ + "(" + ", ".join(k + "=" + repr(getattr(self, k)) for k in self.__class__.__slots__) + ")"


class Solver:
	__slots__ = ("posesDominances", "posesTransitions")

	def __init__(self, posesDominances, posesTransitions):
		self.posesDominances = posesDominances
		self.posesTransitions = posesTransitions

	def getBeating(self, pose: str) -> typing.Set[str]:
		return {d for _, d in self.posesDominances.out_edges(pose)}

	def getReacheable(self, pose: str) -> typing.Set[str]:
		return {d for _, d in self.posesTransitions.edges(pose)} | {pose}

	def getReacheableAndBeating(self, beaterCurrentPose: str, beatedCurrentPose: str) -> typing.Set[str]:
		beatsOther = self.getBeating(beatedCurrentPose)
		reacheable = self.getReacheable(beaterCurrentPose)
		return reacheable & beatsOther

	def heurFunc(self, ourNextPoseHypothesis: str, opponentResponseMoves: typing.Set[str]) -> float:
		return 2 * self.posesTransitions.degree(ourNextPoseHypothesis) - sum(self.posesTransitions.degree(el) for el in opponentResponseMoves)

	def minimax(self, our: str, opponent: str, neutralMove: str="aaa") -> typing.Set[str]:
		reacheableBeating = self.getReacheableAndBeating(our, opponent)

		minHeur = float("-inf")
		minCountBeatPossibs = 5
		minHypot = None
		minRespMoves = None

		for ourNextPoseHypothesis in reacheableBeating:
			opponentResponseMoves = self.getReacheableAndBeating(opponent, ourNextPoseHypothesis)
			curMonkeyBeatMoves = len(opponentResponseMoves)
			if curMonkeyBeatMoves > minCountBeatPossibs:
				continue

			curHeur = self.heurFunc(ourNextPoseHypothesis, opponentResponseMoves)
			if curMonkeyBeatMoves < minCountBeatPossibs:
				minCountBeatPossibs = curMonkeyBeatMoves
				minHypot = ourNextPoseHypothesis
				minRespMoves = opponentResponseMoves
				minHeur = curHeur
			elif curMonkeyBeatMoves == minCountBeatPossibs:
				if curHeur > minHeur:
					minHypot = ourNextPoseHypothesis
					minRespMoves = opponentResponseMoves
					minHeur = curHeur

		if our == minHypot:
			transition = neutralMove
		else:
			transition = self.posesTransitions.edges[our, minHypot]["label"]

		return Move(transition, minHypot, minRespMoves, minHeur)

	def precomputeMoveTable(self, neutralMove: str="aaa") -> typing.Mapping[typing.Tuple[str, str], Move]:
		res = {}
		for our in self.posesDominances.nodes:
			for opponent in self.posesDominances.nodes:
				res[our, opponent] = self.minimax(our, opponent, neutralMove = neutralMove)
		return res


async def main(precomputedTable):
	with patch_stdout():
		inputStringFormat = "monkey you"
		session = PromptSession(inputStringFormat + ": ")
		while True:
			try:
				yourMsg = await session.prompt_async()
				splitted = yourMsg.strip().split(" ")
				if len(splitted) == 2:
					monkey, you = splitted

					try:
						print(precomputedTable[you, monkey])
					except KeyError:
						print("Not found: ", (you, monkey))
				else:
					print("Incorrect input string, please follow the format:", inputStringFormat)
			except (EOFError, KeyboardInterrupt):
				return


class CLI(cli.Application):
	"""
	This is a script guiding you through Monkey Kombat minigame of Escape from Monkey Island. This game seems to be hard to play to people unfamiliar with game theory and graphs.
	You need to prepare 2 files with data in GraphViz format. Some info is introduced by Jojo Jr. The rest has to be gained by dueling with monkeys.
	First, notation:
	* poses are 2 first letters of the words, `bb` for `Bobing Baboon`
	* transitions are 3 letters: `cue` for `Chee Oop Eek`

	First you need to get the directed graph describing pose dominances. `aa -> gg;` means pose `gg` beats pose `aa`. If you visialize this graph using `xdot` and hover to the pose of the monkey, the outgoing arrows will point to poses that Guybrush can use to beat them.
	Second you need to get the undirected graph describing transitions. `cc -- gg  [label=auc];` means pose `cc` and pose `gg` can be transformed to each other using the transition `auc`. Again, hovering your pose in `xdot` visualization will show the poses you can reach.
	Then you start this script, type the pose of the monkey then, after a whitespace, the pose of Guybrush, and you will get the instruction what to do next.
	If the monkey is in Charging Chimp and you are in Drunken monkey, print `cc dm`.

	The transition and dominance graphs have the structure that for each pair of poses of players there is a move that beats opponent's pose.
	Proof: each pose has at least 3 moves (to other poses) and there are exactly 2 poses that are dominated by each pose. So there are at least 3 - 2 = 1 move that dominates each pose. But usually there are 2.
	If there are no errors and no regeneration, the player who has more health wins. If they start with equal health, the one making the move first wins. So the monkeys AI is made to make errors with some probability.
	But the game has regeneration, based not on turns, but on real time.

	WARNING!!! Don't use this script in the very final battle! Since noone makes errors there, and given the regeneration (life bar is broken in ScummVM by now, you won't see this) that battle can continue indefinitely. The solution to the final battle is not to win it.
	"""

	def main(self, dominances: cli.ExistingFile = "./dominances.dot", transitions: cli.ExistingFile = "./transitions.dot"):
		s = Solver(posesDominances=importGraph(nx.DiGraph, Path(dominances)), posesTransitions=importGraph(nx.Graph, Path(transitions)))
		precomputedTable = s.precomputeMoveTable()
		asyncio.run(main(precomputedTable))


if __name__ == "__main__":
	CLI.run()
 

transitions.dot

graph{
	aa, cc, dm[color=green];
	bb, gg[color=blue];

	aa -- cc  [label=aue, color=green];
	aa -- dm  [label=uac, color=green];
	aa -- bb  [label=cue];
	aa -- gg  [label=acu];
	cc -- dm  [label=aeu, color=green];
	cc -- bb  [label=eca];
	cc -- gg  [label=auc];
	dm -- bb  [label=cae];
	dm -- gg  [label=ace];
}

UNLICENSE

This is free and unencumbered software released into the public domain.

Anyone is free to copy, modify, publish, use, compile, sell, or
distribute this software, either in source code form or as a compiled
binary, for any purpose, commercial or non-commercial, and by any
means.

In jurisdictions that recognize copyright laws, the author or authors
of this software dedicate any and all copyright interest in the
software to the public domain. We make this dedication for the benefit
of the public at large and to the detriment of our heirs and
successors. We intend this dedication to be an overt act of
relinquishment in perpetuity of all present and future rights to this
software under copyright law.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
OTHER DEALINGS IN THE SOFTWARE.

For more information, please refer to <https://unlicense.org/>