super-auto-pets-board-game/internal/ai/arrange.go

package ai

import (
	"slices"
	"strings"

	"github.com/greyson/super-auto-pets-board-game/internal/game"
)

// decideArrange searches for the best secret battle ordering of the bot's
// deck. This is where "guess what the opponent will do" matters most: every
// candidate ordering is judged by simulated battles against a spread of
// sampled opponent decks and orderings, never against the opponent's real
// (hidden) choice.
//
// The search runs in two stages to stay cheap:
//  1. every permutation of the pets (≤ 5! = 120), each with a default food
//     placement, gets a quick screening score;
//  2. the best few permutations are re-scored precisely, each trying several
//     food-placement variants (front-loaded, on the strongest pet, spread,
//     on an apple-synergy pet like Rooster or Leopard).
func (b *Bot) decideArrange(v *game.View, mem *Memory) *Action {
	cx := newCtx(v, mem)
	deck := cx.me.Deck

	var pets, foods []game.Card
	for _, c := range deck {
		if c.IsPet() {
			pets = append(pets, c)
		} else {
			foods = append(foods, c)
		}
	}
	if len(pets) == 0 {
		// Nothing can fight; any order loses identically.
		return &Action{Type: "arrange", Order: cardIDs(deck)}
	}

	oppSamples, simsPer := b.budget()
	oppDecks := cx.oppArrangements(oppSamples)

	// Stage 1: screen every pet permutation with the default food placement
	// against a subset of the opponent guesses.
	perms := permutations(len(pets), 200)
	screen := oppDecks[:min(4+int(b.level*4), len(oppDecks))]
	type scored struct {
		perm  []int
		score float64
	}
	ranked := make([]scored, 0, len(perms))
	for _, perm := range perms {
		arr := buildArrangement(pets, perm, foods, placeFront)
		ranked = append(ranked, scored{perm, cx.winProb(arr, screen, 1)})
	}
	slices.SortStableFunc(ranked, func(a, b scored) int {
		switch {
		case a.score > b.score:
			return -1
		case a.score < b.score:
			return 1
		}
		return 0
	})

	// Stage 2: refine the leaders with every food-placement variant and the
	// full opponent sample set.
	var cands []candidate
	seen := map[string]bool{}
	for _, r := range ranked[:min(5, len(ranked))] {
		for _, place := range []foodPlacement{placeFront, placeStrongest, placeSpread, placeSynergy} {
			arr := buildArrangement(pets, r.perm, foods, place)
			key := fingerprint(arr)
			if seen[key] {
				continue
			}
			seen[key] = true
			cands = append(cands, candidate{
				act:   &Action{Type: "arrange", Order: cardIDs(arr)},
				score: cx.winProb(arr, oppDecks, simsPer),
			})
		}
	}
	return b.pick(cands).act
}

// foodPlacement decides which pet slot (index into the pet order) each food
// card sits in front of.
type foodPlacement func(pets []game.Card, foodIdx int, food game.Card) int

// placeFront stacks everything on the leading pet: it fights the most
// clashes, so buffs there see the most use.
func placeFront([]game.Card, int, game.Card) int { return 0 }

// placeStrongest feeds the biggest pet — apples on a heavy hitter compound,
// and perks protect the pet that fights longest.
func placeStrongest(pets []game.Card, _ int, _ game.Card) int {
	best := 0
	for i, p := range pets {
		if p.Power > pets[best].Power {
			best = i
		}
	}
	return best
}

// placeSpread deals foods round-robin so one Skunk or Wolverine can't strip
// the whole stockpile at once.
func placeSpread(pets []game.Card, foodIdx int, _ game.Card) int {
	return foodIdx % len(pets)
}

// placeSynergy targets pets whose abilities key off attached apples
// (Rooster's bees, Dodo's recycling, Leopard's per-power rocks, Peacock and
// Scorpion wanting to survive); falls back to the strongest pet.
func placeSynergy(pets []game.Card, foodIdx int, food game.Card) int {
	for i, p := range pets {
		switch p.Name {
		case "Rooster", "Dodo", "Leopard", "Peacock", "Scorpion", "Bulldog", "Macaque":
			return i
		}
	}
	return placeStrongest(pets, foodIdx, food)
}

// buildArrangement lays out the deck: foods assigned to a pet slot appear
// directly above that pet, and no food ever trails uselessly at the bottom.
// Perks assigned to the same pet keep only the last one applied, so extras
// are pushed to later pets.
func buildArrangement(pets []game.Card, perm []int, foods []game.Card, place foodPlacement) []game.Card {
	ordered := make([]game.Card, len(perm))
	for i, pi := range perm {
		ordered[i] = pets[pi]
	}
	assign := make([][]game.Card, len(ordered))
	perkUsed := make([]bool, len(ordered))
	for fi, f := range foods {
		at := place(ordered, fi, f)
		if f.Perk {
			// Slide duplicate perks onto the next unperked pet.
			for at < len(ordered) && perkUsed[at] {
				at++
			}
			if at >= len(ordered) {
				at = len(ordered) - 1
			}
			perkUsed[at] = true
		}
		assign[at] = append(assign[at], f)
	}
	out := make([]game.Card, 0, len(pets)+len(foods))
	for i, p := range ordered {
		out = append(out, assign[i]...)
		out = append(out, p)
	}
	return out
}

// permutations enumerates permutations of n indices, up to limit (5 pets is
// 120, so the limit only guards hypothetical future rule changes).
func permutations(n, limit int) [][]int {
	idx := make([]int, n)
	for i := range idx {
		idx[i] = i
	}
	var out [][]int
	var rec func(k int)
	rec = func(k int) {
		if len(out) >= limit {
			return
		}
		if k == n {
			out = append(out, slices.Clone(idx))
			return
		}
		for i := k; i < n; i++ {
			idx[k], idx[i] = idx[i], idx[k]
			rec(k + 1)
			idx[k], idx[i] = idx[i], idx[k]
		}
	}
	rec(0)
	return out
}

func cardIDs(cards []game.Card) []string {
	ids := make([]string, len(cards))
	for i, c := range cards {
		ids[i] = c.ID
	}
	return ids
}

func fingerprint(cards []game.Card) string {
	return strings.Join(cardIDs(cards), "|")
}