Help with algorithm: calculate max possible score of DigitParty game

I created a package that provides a programmatically playable copy of Digit Party. The game itself is pretty simple, but has a good depth of strategy; I highly recommend playing a few games.

I need help with one part though: calculating the maximum possible score. Currently I just calculate the maximum possible score assuming that each instance of a given number can be connected to every other instance of that number. This is obviously not correct. Does anyone have any ideas of how to calculate this?

Also, feel free to create your own engine and see how it does!

1 Like

If you know all the digits in advance, which is the case when you design the instance, you can formulate it as an integer program and solve it with eg. https://jump.dev/

1 Like

That sounds really neat! However I know almost nothing about optimization (or jump). Do you have any suggestions?

JuMP’s documentation is really well-done if you only need practical knowledge: Introduction · JuMP
For more theoretical aspects, I have listed some references here: IntroJulia - LP
In particular, I think your problem is close to Sudoku, so you could use their formulation to get started: Sudoku · JuMP

I’ve made an attempt. I believe it correctly establishes all of the constraints. However, I’m struggling with the @objective.

using StaticArrays
using JuMP
using HiGHS

# How the game is defined
mutable struct Game
    board   :: MMatrix{5,5,Int8}
    up_next :: MVector{2,Int8}
end


function get_max_score(g::Game)
    game_is_over(g) || error("Cannot get max score before game is over")

    # Create an array that acts like a dictionary. The index is the number and the value
    # is how many times that number appeared on the board
    counts = @MVector zeros(Int, 9)
    for val in g.board
        counts[val] += 1
    end

    model = Model(HiGHS.Optimizer)
    # Create a 7x7 matrix, where the outer rows and columns are all zeros. Makes getting
    # neighbors easier
    @variable(model, x[1:7, 1:7], Int)

    # All boundaries have to be 0
    @constraint(model, bz1, x[:, 1] .== 0)
    @constraint(model, bz2, x[:, end] .== 0)
    @constraint(model, bz3, x[1, :] .== 0)
    @constraint(model, bz4, x[end, :] .== 0)

    # Need the correct number of instances of each number
    @constraints(
        model,
        begin
            correct_numbers[i = eachindex(counts)], count(==(i), x[2:6, 2:6]) == counts[i]
        end
    )

    # Hoping to use 
    # when `x[idx+dir] >= 1`, we add `x[idx]`, otherwise add 0
    # DIRS = CartesianIndex.([(1, 1), (1, 0), (1, -1), (0, 1), (0, -1), (-1, 1), (-1, 0), (-1, -1)])
    @objective(
        model,
        Max,
        sum(
            x[idx] * (1 - min(x[idx+dir], 1)) for
            idx in eachindex(IndexCartesian(), x[2:6, 2:6]) for dir in DIRS
        )
    )

    optimize!(model)
    @show termination_status(model)
    @show x
end

Any thoughts on how to write the objective?

It looks like the creators of the game don’t yet have a great way to solve it themselves. I asked for clarification on how they calculate the score on the site.

They say

We assume you can get the maximum score for every digit, and we know those. We’re well aware that this isn’t always possible, and people have shared screenshots where it doesn’t work, we just haven’t come up with a better way yet.

Here’s how I would write it, using the package GridGraphs.jl that I developed (be sure to install the latest version 0.9.1):

using Graphs
using GridGraphs: GridGraph, QUEEN_DIRECTIONS, index_to_coord
using HiGHS
using JuMP

d = 4  # size of the grid, vertices are named u or v
n = 9  # maximum number, numbers are named k

grid = GridGraph(ones(Int, d, d); directions=QUEEN_DIRECTIONS);
numbers = rand(1:n, d^2);  # sequence of numbers (order unimportant)
numbers_count = [count(==(k), numbers) for k in 1:n];

model = Model(HiGHS.Optimizer)

# Variables: x[v, k] = 1 <-> number k on vertex v
@variable(model, x[v=1:d^2, k=1:n], Bin);
# Auxiliary variables: y[u, v, k] = x[u, k] x[v, k]
@variable(model, y[u=1:d^2, v=1:d^2, k=1:n; has_edge(grid, u, v)], Bin);

# Constraint 1: one number per vertex
@constraint(model, [v = 1:d^2], sum(x[v, :]) == 1);

# Constraint 2: as many k's as needed
@constraint(model, [k = 1:n], sum(x[:, k]) == numbers_count[k]);

# Linearization constraints: coherence between y and x
@constraint(model, [u = 1:d^2, v = 1:d^2, k = 1:n; has_edge(grid, u, v)], y[u, v, k] <= x[u, k]);
@constraint(model, [u = 1:d^2, v = 1:d^2, k = 1:n; has_edge(grid, u, v)], y[u, v, k] <= x[v, k]);
@constraint(model, [u = 1:d^2, v = 1:d^2, k = 1:n; has_edge(grid, u, v)], y[u, v, k] >= x[u, k] + x[v, k] - 1);

# Objective: sum of k xᵤₖ xᵥₖ over all k's and all edges (u, v)
@objective(model, Max, sum(k * y[src(e), dst(e), k] for k in 1:n, e in edges(grid)));

optimize!(model)

x_sol = round.(Int, value.(x))

solution = zeros(Int, d, d)
for v in vertices(grid)
    (i, j) = index_to_coord(grid, v)
    solution[i, j] = argmax(x_sol[v, :])
end

Here’s what we get at the end for one random instance:

julia> 1:n .=> numbers_count
9-element Vector{Pair{Int64, Int64}}:
 1 => 0
 2 => 2
 3 => 1
 4 => 2
 5 => 4
 6 => 0
 7 => 3
 8 => 3
 9 => 1

julia> solution
4×4 Matrix{Int64}:
 4  4  3  9
 8  8  5  5
 7  8  5  5
 7  7  2  2

It takes a VERY long time to solve for d=5 so maybe there is a better formulation though

1 Like

This might typically be an instance where constraint programming would work faster

Also, looking at the solution, I think we can somehow relate it to bin-packing or other classical problems. A faster approach might explicitly enumerate connected regions where one can put several numbers at once.
Here’s an example of an alternative formulation which has an exponential number of variables but should be solvable with branch & price:

\max_{x \in \{0,1\}^{KR}} \, \sum_k \sum_r k |E(r)| x_{k,r} \quad \text{s.t.} \quad \left\vert \begin{aligned} \sum_r |V(r)| x_{k,r} & = N_k & \forall k \\ \sum_k x_{k,r} & \leq 1 & \forall r \\ \sum_k (x_{k,r_1} + x_{k,r_2}) & \leq 1 & \forall r_1 \cap r_2 \end{aligned} \right.

  • The index k denotes numbers from 1 to 9, while r denotes connected regions of the grid (with V(r) vertices and E(r) internal edges).
  • The binary variable x_{k,r} is equal to 1 if region r is filled with number k
  • The first constraint imposes that we insert exaclty N(k) times the number k
  • The second constraint ensures that a region r is occupied by at most one number k
  • The third constraint enforces that two intersecting regions r_1 and r_2 cannot be occupied at the same time

By using Gurobi instead oh HiGHS, your code solves the 5x5 grids in a few seconds instead of a few minutes. It also becomes slow on 6x6 grids and larger though.

1 Like