Skip to content

Instantly share code, notes, and snippets.

@ITR13

ITR13/buckshot-bruteforce.nim

Last active February 20, 2024 18:29
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save ITR13/00cbc6b28de0f67f3dd70af94361e2f1 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save ITR13/00cbc6b28de0f67f3dd70af94361e2f1 to your computer and use it in GitHub Desktop.
Download ZIP
Finds the optimal move for the player to use against the original dealer AI
Raw
buckshot-bruteforce.nim
import std/tables
import std/hashes
const MaxDepth = 1
type
Item = enum
None, Magnify, Cigarette, Beer, Handcuff, Handsaw
ShootPerson = enum
Self, Other
Action = object
case UseItem: bool
of true: Item: Item
of false: ShootTarget: ShootPerson
ShellType = enum
None, Live, Blank
HandcuffState = enum
Uncuffed, FreeNext, Cuffed
Chance = object
DoubleOrNothing: float64
Death, Health, Items: array[2, float64]
Result = object
Action: Action
Probability: Chance
Player = object
MaxHealth: 1..6
Health: 0..6
Items: array[8, Item]
GameState = object
Depth: 0..MaxDepth
DoubleOrNothing: bool
LiveShells: 0..4
BlankShells: 0..5
PlayerTurn: bool
PlayerData, DealerData: Player
NextShell: ShellType
HandcuffState: HandcuffState
UsedHandsaw: bool
ChanceGameState = object
State: GameState
Probability: float64
Cache = object
PlayerCache: Table[GameState, Result]
NewRoundCache: Table[GameState, Chance]
const itemScoreArray: array[Item, array[9, float64]] = [
[ 0.0, 1.0, 2.0, 2.6, 3.0, 3.0, 3.0 , 3.0, 3.0, ], # FreeSlots
[ 0.0, 1.5, 3.0, 3.5, 4.5, 5.0, 6.5 , 6.8, 7.0 ], # Magnify
[ 0.0, 0.5, 1.0, 1.2, 1.2, 1.2, 1.2 , 1.2, 1.2 ], # Cigarette
[ 0.0, 1.0, 2.0, 3.0, 3.5, 4.0, 4.25, 4.5, 4.75 ], # Beer
[ 0.0, 1.2, 2.0, 2.5, 2.6, 2.7, 2.8 , 2.9, 3.0 ], # Handcuff
[ 0.0, 1.5, 2.6, 3.1, 3.5, 3.6, 3.7 , 3.8, 3.9 ], # Handsaw
]
proc hash(player: Player): Hash =
result = result !& hash(player.Health)
result = result !& hash(player.MaxHealth)
result = result !& hash(player.Items)
result = !$result
proc hash(state: GameState): Hash =
result = result !& hash(state.Depth)
result = result !& hash(state.DoubleOrNothing)
result = result !& hash(state.LiveShells)
result = result !& hash(state.BlankShells)
result = result !& hash(state.PlayerTurn)
result = result !& hash(state.PlayerData)
result = result !& hash(state.DealerData)
result = result !& hash(state.NextShell)
result = result !& hash(state.HandcuffState)
result = result !& hash(state.UsedHandsaw)
result = !$result
func `+`(a, b: array[2, float64]): array[2, float64] =
return [a[0]+b[0], a[1]+b[1]]
func `+`(a, b: Chance): Chance =
return Chance(
DoubleOrNothing: a.DoubleOrNothing+b.DoubleOrNothing,
Death: a.Death+b.Death,
Health: a.Health+b.Health,
Items: a.Items+b.Items
)
func `*`(a: array[2, float64], b: float64): array[2, float64] =
assert b != 0
return [a[0]*b, a[1]*b]
func `*`(a: Chance, b: float64): Chance =
assert b != 0
return Chance(
DoubleOrNothing: a.DoubleOrNothing*b,
Death: a.Death*b,
Health: a.Health*b,
Items: a.Items*b
)
func countItems(player: Player): array[Item, int] =
for item in player.Items:
result[item] += 1
func itemScore(player: Player): float64 =
var value = 0.0
for item, count in player.countItems():
value += itemScoreArray[item][count]
return value
func GetData(state: GameState): array[2, Player] =
if state.PlayerTurn:
return [state.PlayerData, state.DealerData]
return [state.DealerData, state.PlayerData]
func RemoveItem(state: GameState, itemToRemove: Item): GameState =
var templateState = state
if state.PlayerTurn:
for i, item in state.PlayerData.Items:
if item == itemToRemove:
templateState.PlayerData.Items[i] = None
return templateState
else:
for i, item in state.DealerData.Items:
if item == itemToRemove:
templateState.DealerData.Items[i] = None
return templateState
raise newException(AssertionDefect, "No such item")
func Magnify(state: GameState): seq[ChanceGameState] =
var templateState = RemoveItem(state, Magnify)
if state.NextShell != None:
return @[ChanceGameState(State: templateState, Probability: 1)]
var totalShells = state.LiveShells + state.BlankShells
assert totalShells != 0
if state.LiveShells > 0:
var liveState = templateState
liveState.NextShell = Live
result.add(ChanceGameState(State: liveState, Probability: float64(state.LiveShells) / float64(totalShells)))
if state.BlankShells > 0:
var blankState = templateState
blankState.NextShell = Blank
result.add(ChanceGameState(State: blankState, Probability: float64(state.BlankShells) / float64(totalShells)))
return result
func Beer(state: GameState): seq[ChanceGameState] =
var templateState = RemoveItem(state, Beer)
templateState.NextShell = None
var totalShells = state.LiveShells + state.BlankShells
assert totalShells != 0
if state.LiveShells > 0:
var liveState = templateState
liveState.LiveShells -= 1
result.add(ChanceGameState(State: liveState, Probability: float64(state.LiveShells) / float64(totalShells)))
if state.BlankShells > 0:
var blankState = templateState
blankState.BlankShells -= 1
result.add(ChanceGameState(State: blankState, Probability: float64(state.BlankShells) / float64(totalShells)))
return result
func Cigarette(state: GameState): GameState =
var newState = RemoveItem(state, Cigarette)
if state.PlayerTurn:
newState.PlayerData.Health = min(state.PlayerData.Health+1, state.PlayerData.MaxHealth)
else:
newState.DealerData.Health = min(state.DealerData.Health+1, state.DealerData.MaxHealth)
return newState
func Handcuffs(state: GameState): GameState =
assert state.HandcuffState == Uncuffed
var newState = RemoveItem(state, Handcuff)
newState.HandcuffState = Cuffed
return newState
func Handsaw(state: GameState): GameState =
assert not state.UsedHandsaw
var newState = RemoveItem(state, Handsaw)
newState.UsedHandsaw = true
return newState
# For recursion
func NewRound(cache: var Cache, state: GameState): Chance
func NextTurn(cache: var Cache, state: GameState, freeContinue: bool=false): Chance
func Shoot(cache: var Cache, state: GameState, target: ShootPerson): Chance =
var totalShells = state.LiveShells + state.BlankShells
assert totalShells != 0
if state.LiveShells > 0 and state.NextShell != Blank:
var liveChance = if state.NextShell == Live: 1.0 else: state.LiveShells / totalShells
var liveState = state
liveState.LiveShells -= 1
liveState.UsedHandsaw = false
liveState.NextShell = None
let damage = if state.UsedHandsaw: 2 else: 1
if (target == Self) xor state.PlayerTurn:
liveState.DealerData.Health -= min(damage, liveState.DealerData.Health)
else:
liveState.PlayerData.Health -= min(damage, liveState.PlayerData.Health)
result = result + NextTurn(cache, liveState, false) * liveChance
if state.BlankShells > 0 and state.NextShell != Live:
var blankChance = if state.NextShell == Blank: 1.0 else: state.BlankShells / totalShells
var blankState = state
blankState.BlankShells -= 1
if target != Self or state.PlayerTurn:
blankState.UsedHandsaw = false
result = result + NextTurn(cache, blankState, target == Self) * blankChance
return result
const Tolerance = 1e-10
proc `~~`(a, b: float): int =
if abs(a - b) < Tolerance:
return 0
return if a < b: -1 else: 1
proc CompareResults(x, y: Result): int =
let p0 = x.Probability
let p1 = y.Probability
# NB: p0 ~~ p1 -> Minimize number, swap around to maximize number
result = p0.Death[0] ~~ p1.Death[0]
if result != 0:
return
result = p1.Death[1] ~~ p0.Death[1]
if result != 0:
return
result = p1.DoubleOrNothing ~~ p0.DoubleOrNothing
if result != 0:
return
result = p1.Health[0] ~~ p0.Health[0]
if result != 0:
return
result = p0.Health[1] ~~ p1.Health[1]
if result != 0:
return
result = p1.Items[0] ~~ p0.Items[0]
if result != 0:
return
result = p0.Items[1] ~~ p1.Items[1]
proc `<`(x, y: Result): bool =
return CompareResults(x, y) < 0
func PlayerChoice(cache: var Cache, state: GameState): Result =
if cache.PlayerCache.hasKey(state):
return cache.PlayerCache[state]
let totalShells = state.LiveShells + state.BlankShells
if totalShells == 0:
return Result(Action: Action(UseItem: true, Item: None), Probability: NewRound(cache, state))
let players = state.GetData()
let items = players[0].countItems()
var options: seq[Result]
# We always want using a handsaw to be the last action before shooting, because game looks weird otherwise
if not state.UsedHandsaw:
if items[Magnify] > 0:
var chance: Chance
for possibleState in state.Magnify():
let subResult = PlayerChoice(cache, possibleState.State)
chance = chance + subResult.Probability * possibleState.Probability
options.add(Result(
Action: Action(UseItem: true, Item: Magnify),
Probability: chance
))
if items[Beer] > 0:
var chance: Chance
for possibleState in state.Beer():
let subResult = PlayerChoice(cache, possibleState.State)
chance = chance + subResult.Probability * possibleState.Probability
options.add(Result(
Action: Action(UseItem: true, Item: Beer),
Probability: chance
))
if items[Cigarette] > 0:
options.add(Result(
Action: Action(UseItem: true, Item: Cigarette),
Probability: PlayerChoice(cache, state.Cigarette()).Probability
))
if items[Handsaw] > 0:
options.add(Result(
Action: Action(UseItem: true, Item: Handsaw),
Probability: PlayerChoice(cache, state.Handsaw()).Probability
))
if items[Handcuff] > 0 and state.HandcuffState == Uncuffed:
options.add(Result(
Action: Action(UseItem: true, Item: Handcuff),
Probability: PlayerChoice(cache, state.Handcuffs()).Probability
))
for target in ShootPerson:
options.add(Result(
Action: Action(UseItem: false, ShootTarget: target),
Probability: Shoot(cache, state, target)
))
result = min(options)
cache.PlayerCache[state] = result
return result
func DealerChoice(cache: var Cache, state: GameState, assumedShell: ShellType = None): Result =
let totalShells = state.BlankShells + state.LiveShells
if totalShells == 0:
return Result(Action: Action(UseItem: true, Item: None), Probability: NewRound(cache, state))
var assumedShell = assumedShell
if totalShells == 1:
assumedShell = if state.BlankShells == 0: Live else: Blank
let players = state.GetData()
var canUseHandsaw = false
for item in players[0].Items:
case item:
of None:
continue
of Magnify:
if assumedShell != None:
continue
var chance: Chance
for possibleState in state.Magnify():
let subResult = DealerChoice(cache, possibleState.State, possibleState.State.NextShell)
chance = chance + subResult.Probability * possibleState.Probability
return Result(Action: Action(UseItem: true, Item: item), Probability: chance)
of Cigarette:
if players[0].Health >= players[0].MaxHealth:
continue
let subResult = DealerChoice(cache, state.Cigarette(), assumedShell)
return Result(Action: Action(UseItem: true, Item: item), Probability: subResult.Probability)
of Beer:
if assumedShell == Live or totalShells <= 1:
continue
var chance: Chance
for possibleState in state.Beer():
let subResult = DealerChoice(cache, possibleState.State, assumedShell)
chance = chance + subResult.Probability * possibleState.Probability
return Result(Action: Action(UseItem: true, Item: item), Probability: chance)
of Handcuff:
if state.HandcuffState != Uncuffed or totalShells <= 1:
continue
let subResult = DealerChoice(cache, state.Handcuffs(), assumedShell)
return Result(Action: Action(UseItem: true, Item: item), Probability: subResult.Probability)
of Handsaw:
if state.UsedHandsaw:
continue
if assumedShell != Live:
canUseHandsaw = true
continue
let subResult = DealerChoice(cache, state.Handsaw(), assumedShell)
return Result(Action: Action(UseItem: true, Item: item), Probability: subResult.Probability)
let otherTarget = Action(UseItem: false, ShootTarget: Other)
let selfTarget = Action(UseItem: false, ShootTarget: Self)
result = case assumedShell:
of None:
Result(
Action: Action(UseItem: true, Item: None),
Probability: (
Shoot(cache, state, Other) +
Shoot(cache, state, Self)
) * 0.5
)
of Live: Result(Action: otherTarget, Probability: Shoot(cache, state, Other))
of Blank: Result(Action: selfTarget, Probability: Shoot(cache, state, Self))
return result
func NewRoundWithItems(cache: var Cache, state: GameState, playerItemsToGrab, dealerItemsToGrab: int): Chance =
var nextState = state
var statesChecked = 0
let totalItemsToGrab = playerItemsToGrab + dealerItemsToGrab
# TODO: Only 2 cigarettes allowed
for shells in 1..8:
nextState.LiveShells = shells div 2
nextState.BlankShells = shells - nextState.LiveShells
var itemsToAdd: seq[Item]
for i in 0..totalItemsToGrab:
itemsToAdd.add(Magnify)
# Magnify, Cigarette, Beer, Handcuff, Handsaw
var running = true
while running:
nextState.PlayerData.Items = state.PlayerData.Items
nextState.DealerData.Items = state.DealerData.Items
var grabItemIndex = 0
for i in 0..7:
if grabItemIndex == playerItemsToGrab:
break
if nextState.PlayerData.Items[i] != None:
continue
nextState.PlayerData.Items[i] = itemsToAdd[grabItemIndex]
grabItemIndex += 1
grabItemIndex = 0
for i in 0..7:
if grabItemIndex == totalItemsToGrab:
break
if nextState.DealerData.Items[i] != None:
continue
nextState.DealerData.Items[i] = itemsToAdd[grabItemIndex]
grabItemIndex += 1
result = result+PlayerChoice(cache, nextState).Probability
statesChecked += 1
for i in 0..totalItemsToGrab:
if itemsToAdd[i] != Handsaw:
itemsToAdd[i] = Item(int(itemsToAdd[i])+1)
break
if i == totalItemsToGrab:
running = false
break
itemsToAdd[i] = Magnify
return result * (1/float64(statesChecked))
func NewRound(cache: var Cache, state: GameState): Chance =
if cache.NewRoundCache.hasKey(state):
return cache.NewRoundCache[state]
var playerHealth = state.PlayerData.Health
var dealerHealth = state.DealerData.Health
var finishedSearching = playerHealth <= 0 or (dealerHealth <= 0 and not state.DoubleOrNothing)
if state.Depth >= MaxDepth or finishedSearching:
result = Chance(
DoubleOrNothing: 0.0,
Death: [
if playerHealth == 0: 1.0 else: 0.0,
if dealerHealth == 0: 1.0 else: 0.0
],
Health: [float64(playerHealth), float64(dealerHealth)],
Items: [state.PlayerData.itemScore(), state.DealerData.itemScore()],
)
cache.NewRoundCache[state] = result
return result
var nextState = state
nextState.Depth += 1
nextState.DoubleOrNothing = nextState.DoubleOrNothing and dealerHealth > 0
var highestPlayerItem = -1
var lastNoneTaken = 0
for i in 0..7:
if i > lastNoneTaken:
lastNoneTaken = i
if nextState.PlayerData.Items[i] != None:
highestPlayerItem = i
continue
for j in lastNoneTaken+1..7:
if nextState.PlayerData.Items[j] != None:
nextState.PlayerData.Items[i] = nextState.PlayerData.Items[j]
nextState.PlayerData.Items[j] = None
lastNoneTaken = j
break
if lastNoneTaken == 7:
break
var highestDealerItem = -1
lastNoneTaken = 0
for i in 0..7:
if i > lastNoneTaken:
lastNoneTaken = i
if nextState.DealerData.Items[i] != None:
highestDealerItem = i
continue
for j in lastNoneTaken+1..7:
if nextState.DealerData.Items[j] != None:
nextState.DealerData.Items[i] = nextState.DealerData.Items[j]
nextState.DealerData.Items[j] = None
lastNoneTaken = j
break
let playerItemsToGrab = min(4, 7-highestPlayerItem)
let dealerItemsToGrab = min(4, 7-highestDealerItem)
let maxItemsToGrab = max(playerItemsToGrab, dealerItemsToGrab)
var subCache: Cache
if dealerHealth <= 0:
for startingHealth in 2..4:
nextState.PlayerData.Health = startingHealth
nextState.PlayerData.MaxHealth = startingHealth
nextState.DealerData.Health = startingHealth
nextState.DealerData.MaxHealth = startingHealth
for itemsGained in 1..maxItemsToGrab:
var subResult = NewRoundWithItems(subCache, nextState, min(itemsGained, playerItemsToGrab), min(itemsGained, dealerItemsToGrab))
if itemsGained == maxItemsToGrab:
result = result + subResult * float64(5-maxItemsToGrab)
else:
result = result + subResult
result = result * (1.0 / (3.0 * 4.0))
result.DoubleOrNothing = 1.0
else:
for itemsGained in 1..maxItemsToGrab:
var subResult = NewRoundWithItems(subCache, nextState, min(itemsGained, playerItemsToGrab), min(itemsGained, dealerItemsToGrab))
if itemsGained == maxItemsToGrab:
result = result + subResult * float64(5-maxItemsToGrab)
else:
result = result + subResult
result = result * (1.0 / 4.0)
cache.NewRoundCache[state] = result
return result
func NextTurn(cache: var Cache, state: GameState, freeContinue: bool=false): Chance =
if state.PlayerData.Health <= 0 or (state.LiveShells == 0 and state.BlankShells == 0):
return NewRound(cache, state)
if freeContinue:
if state.PlayerTurn:
result = PlayerChoice(cache, state).Probability
else:
result = DealerChoice(cache, state).Probability
var newState = state
if state.HandcuffState == Cuffed:
newState.HandcuffState = FreeNext
else:
newState.HandcuffState = Uncuffed
newState.PlayerTurn = not newState.PlayerTurn
if newState.PlayerTurn:
return PlayerChoice(cache, newState).Probability
else:
return DealerChoice(cache, newState).Probability
var cache = Cache()
echo PlayerChoice(
cache,
GameState(
Depth: 0,
DoubleOrNothing: true,
LiveShells: 4,
BlankShells: 4,
PlayerTurn: true,
PlayerData: Player(Health: 2, MaxHealth: 2, Items: [Handsaw, None, None, None, None, None, None, None]),
DealerData: Player(Health: 2, MaxHealth: 2, Items: [None, None, None, None, None, None, None, None]),
NextShell: None,
HandcuffState: Uncuffed,
UsedHandsaw: false,
)
)
echo getOccupiedMem()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment