How I Scored 1.38 Million in Tencent’s Tetris Challenge with AI and Dynamic Programming

Problem Context

The competition required achieving the highest possible score in a JavaScript‑based Tetris variant called E‑Tetris . The game runs in a web page, limits the total number of pieces to 10,000 , and uses a deterministic piece sequence generated from a fixed‑seed RNG with orientation derived from the piece count modulo 4. Because the sequence is known in advance, offline planning is possible.

Heuristic Evaluation (EI‑Tetris)

The algorithm adopts the EI‑Tetris heuristic originally described by Pierre Dellacherie. Each board state is evaluated by a weighted sum of six features:

Landing Height : height of the board after placing the piece.

Rows Eliminated : number of lines cleared by the placement.

Row Transitions : number of horizontal edge changes across rows.

Column Transitions : number of vertical edge changes across columns.

Number of Holes : empty cells that have a filled cell above them.

Well Sums : sum of depths of vertical wells.

The weights are tuned by particle‑swarm optimization; a larger weighted sum indicates a more promising board.

Game Automation

Qt’s QWebEngine was used to embed the game page and automate key presses, allowing the AI to control the game without manual input.

State‑Pruned Dynamic Programming

The solution treats each step i as a state s representing the board after placing the i ‑th piece. For each state the maximum achievable score Score_{i,s} is stored. The optimal final score is max_{s∈S_N} Score_{N,s} with N=10000. To keep the state space tractable, each board is compressed into four uint64_t integers that encode five rows of the 20×10 grid.

struct ResultType {
    StringPtr steps; // move sequence and predecessor pointer
    int score = 0;
};

ResultType Solver::solve(Board &board) {
    return greedyForScore(0, (int)brickSeq.size(), board);
}

ResultType Solver::greedyForScore(int first, int last, Board &board) {
    unordered_map<Board, ResultType> boardMap, tempMap;
    boardMap[board]; // insert initial state
    for (int i = first; i < last; ++i) {
        generateChoices(brickSeq[i], boardMap, tempMap);
        boardMap.clear();
        tempMap.swap(boardMap);
    }
    ResultType best{StringPtr(), -1};
    for (auto &item : boardMap)
        if (item.second.score > best.score) {
            best = item.second;
            board = item.first; // keep board of best final state
        }
    return best;
}

void Solver::generateChoices(const Brick &brick,
                             const unordered_map<Board, ResultType> &originMap,
                             unordered_map<Board, ResultType> &targetMap) {
    for (const auto &item : originMap)
        expand(brick, item.first, item.second, targetMap);
    filterHighEvaluation(targetMap, reservedBoardCount); // keep only top‑k states
}

Because the full state space (~2.2 × 10⁸ possible boards) cannot be stored, the algorithm retains only a fixed number of promising states ( reservedBoardCount) at each step, selected by the evaluation function.

Evaluation Function Tuning

The final evaluation combines a board score and a safety penalty proportional to the accumulated game score:

auto evaluation = BoardEvaluator::evaluate(it->first) - it->second.score * scoreWeight;

The board evaluator was simplified to four terms (the original Landing Height and Row Elimination terms were removed, and the Well Sums term was omitted to avoid creating wide wells that hinder the long piece). The remaining parameters were manually tuned:

double BoardEvaluator::evaluate(const Board &board) {
    return params[0] * board.getCount()
         + params[1] * board.getRowTransition()
         + params[2] * board.getColumnTransition()
         + params[3] * board.getNumberOfHoles();
}

inline static constexpr double params[] = {
    -1.0,
    3.2178882868487753,
    9.348695305445199,
    7.899265427351652
};

constexpr double scoreWeight = 1.0 / 38.0;

Removing the Landing Height and Row Elimination terms and adding a Count term (total placed blocks) encourages building higher stacks, while dropping Well Sums forces the algorithm to keep a single‑column slot for the long piece.

Results

With reservedBoardCount = 1000, the program reaches approximately 1.30 M points in about two minutes on a typical desktop. Increasing reservedBoardCount to 30 000 yields around 1.37 M points but requires roughly 1.5 hours of computation. The algorithm naturally stacks blocks on both sides of the board, leaving a narrow vertical well that the long piece can clear for high scores.

Potential Improvements

Automate parameter optimization (e.g., meta‑heuristics) instead of manual tuning.

Enumerate all possible rotations and placements rather than only the default rotation‑plus‑drop.

Optimize data structures and add parallelism (OpenMP or multithreading) to speed up state expansion.

Adjust the scoring bias to exploit non‑long pieces and reduce over‑reliance on the long piece.

Source Code

The full implementation is available at the following repository:

https://github.com/MaxDumbledore/Tencent_Geek_Competition_4

The default reservedBoardCount is 1000; increasing it improves the score at the cost of longer runtime.

Conclusion

A relatively simple heuristic combined with state‑pruned dynamic programming can achieve competitive scores in a deterministic Tetris variant. Further gains require richer search, better automated parameter tuning, and parallel execution.