Gaurav Sen

In this article, we talk about what Challenge problems are and how to solve them. I find them the most attractive questions in a long contest.However, students new to competitive programming often avoid them because they seem weird at first. Let’s try and change that perception.

What are Challenge problems?

A challenge problem in a programming contest uses NP (Nondeterministic Polynomial) problems to test a candidate.

With no perfect answer, candidates are tested on how good they are at finding approximate solutions.

This is why the evaluation is score based.The top scorer is given a score of 100, while the others are given relative scores.Usually, problem statements are simple and allow candidates to find interesting nuances while solving.Because of the generality of the problem, candidates can choose numerous approaches to optimize their score.These include Number Theory, Graphs, Data Science, etc...Some problems require prior knowledge of algorithms, but the best challenge problems are those which have simple explanations and lots of scope for improvement.Such problems allow beginners to try and test their approximate solutions while making sure that the experienced players are tested too.

How do we solve this:

Watch this brilliant video by MIT professor Patrick Wilson, who solves a problem (at 42:30) and amazing trick he puts into it

To summarize the procedure for the problem discussed by the professor, here are the steps -

1. Definition
   Does the problem reduce to Knapsack? Subset sum? Something else?
2. Representation
   Should the main data structure be an array, a list or a tree?
3. Approach
   Dynamic Programming? Graph Algorithm? etc...
4. Algorithm
   DFS / Sorting / Edit Distance --> Simulated Annealing / Genetic Algorithm
5. Experiment

A key point is that drawing and discussing ideas are far more important than jumping into code. The other super important thing is you can't follow this process in just one shot.

It has to be repeated, with each iteration improving your solution.



First, you need a base solution. Choose a simple, clear-cut algorithm (like the first three mentioned above in point 4).

This is the foundation, setting a minimum guarantee to your score.

Invest your time in this, because a weak base solution will directly result in a poor score.

You now need to tweak the best solution you have, updating if you get something better than the current best.

Hill climbing, Simulated Annealing, or any Evolutionary Algorithm will help you here.

Most of your time after this will be spent improving the parameters of the algorithm and improving the time complexity.

The time required to solve them

They can’t be solved in half a day, to be practical. Unless you are looking for an okay score and minimum effort, be prepared to invest significantly.Also, beware of the law of diminishing returns. In general, the more time you invest in these problems, the smaller the improvements you will see.

The first few hours will give you interesting solutions => perhaps a score of 75–85; the next few days might take you to 95–100. And staying there takes tons of effort.

The primary reason why these problems are difficult is that we have to customize and optimize our solutions every time.

You can create a general framework for Simulated Annealing to help in the coding phase. However, the “representation” part will change every time.

Up to which 't' point do I keep optimizing

Until you feel that there is very little progress being made. To be practical, the other problems will give you many more points for the same amount of effort.

When you hit problems beyond your league, come back to improving on the challenge problem solution.

Remember that the people at the top have access to the same resources as you do. There is no reason why they should get a better score than you.

When should I start with this problem

This problem will stay at the back of your mind throughout the contest. So, it is better to start a little late.

More often than not, the problems within our league are solved within the first 80% of the contest’s duration.

The challenge problem can be started then.

Final tips and tricks:

1. Do not jump into meta-heuristics (Genetic Algorithms, Simulated Annealing) without creating a strong base solution.
2. When optimizing, try to keep the code clean for later.
3. Your nested loops need the most attention because that’s where you get the maximum gains.
4. Greed is good. Keep your heuristics simple and easy to change.
5. If some idea feels too complicated, it is. Save it for the next contest, after reading a little more and being confident about it.

Practice your learning at one of the challenges at HackerEarth Challenges

This blog explains my approaches to a game contest hosted by HackerEarth. The contest asked programmers to put forward their bots to play games of Chain Reaction. You can find the source code here.

In case you haven't played Chain Reaction, this post should be a treat for you.

Let me warn you that the following will involve some heavy technical words. But all of them are easier to learn than they sound. In my limited experience of developing game playing AI, I have found the following approaches to be most useful.

1. Min-Max tree generation
2. Heuristic Improvements
3. Iterative deepening
4. Alpha-Beta Pruning
5. Program Optimization

Min Max tree generation

A Min Max tree mimics natural human thinking. When playing tic tac toe, our thinking goes like this:

What you see above is exactly what a min max strategy is. It considers your move, your opponent's possible responses, and your subsequent responses. The loop goes on till we find a terminal game state, in which case we return the terminal node's value.

Every possible board position maps to a value. The value is directly proportional to how much X favors the position. If X wins (green position), the position has +? value. For a loss (circled in red), it evaluates to -?.

Each layer in the tree contains all possible positions for that move number. If X was playing first, the second layer is O's turn. The third is X's, and so on. When a terminal value reaches the parent, it tries to maximize (if X) or minimize (if O) the score from all its available branches.

Generating the entire min-max tree from move 1 for all moves is infeasible. We need a method of guessing how good a position is without looking at every possibility from it.

Heuristic Evaluation

If you have played any sport, you have had moments when your instinct wakes up. Danger, opportunity, momentum... all these feelings rise from an acute understanding of game positions.

So, play a few games in the competition. Try to get a sense of a given position. If a position feels good, then ask yourself “why”. What are the elements on the board which are key factors to this assessment?

instinct(game_position, player_to_move) = feeling

Heuristics are instinct functions for computers. Since generating the entire min max tree is infeasible, we cut off search depth and treat the position as terminal, returning a heuristic value.

f(game_position, player_to_move) = evaluation

Note down the factors you use for assessing a position and assign a weight to each. Then design a heuristic. Avoid making it too fancy. I used:

f(position, player) = (player == 1 ? 1 : -1) * (cell_diff() + explosive_diff())

This simple function performed better than several more complex attempts I tried during the competition.

Iterative deepening

The problem with fixed depth cutoffs is that they are too rigid. Early-game positions have many possibilities; late-game positions have fewer. We need a flexible way to search as deeply as time allows.

Iterative deepening builds min max trees of increasing depth. Start with depth 2–3, then increase by 1 in each iteration. The best result before the timeout is returned.

This way, the algorithm adapts. If many moves exist, it searches shallow. If few moves exist, it searches deeper. This technique is essential for competitive game AI.

Alpha Beta Pruning

It isn’t α–β itself that sets the top entries apart, but most of them surely use it.

In competitions, move prediction is everything. We assume the opponent will always optimize their move. A lot of nodes in a min max tree are wasteful and can be proven suboptimal early.

α and β are bounds for each node. α is the minimum X will accept; β is the maximum O will allow. X tries to maximize α, and O tries to minimize β.

An excellent explanation of implementing α–β pruning is available here.

Each additional move you can predict makes your bot stronger. Without pruning, 1000 evaluations with branch factor 4 allows depth = 5. With α–β pruning, you can reach depth = 6 with a reasonable heuristic.

Program Optimization

Optimization is the most advanced and complex part of developing game AI. But please, DO NOT optimize prematurely. Do it only when:

1. Your program is bug-free
2. You've avoided repeated calculations by caching values
3. Your program fails test cases only due to insufficient evaluation time

Here are some advanced optimization concepts with their complexity and effectiveness:

	Technique	Effectiveness	Implementation
1.	Position Cache	Moderate	Moderate
2.	Killer Move Heuristic	Moderate	Easy – Moderate
3.	Symmetry Analysis	Low–Moderate	Moderate – Difficult
4.	Concise Representations	High	Very Difficult
5.	Object Pooling and Reuse	High	Difficult
6.	Parallelization	Low–Moderate	Difficult – Very Difficult
7.	Heuristic Improvement	High	Moderate – Difficult

A great way to generate test positions is to let your bot play against itself with different heuristic weights. Store decisive positions and optimize based on performance.

Use static objects for classes like “Move”. If you can implement “undo” in O(1), avoid copying boards. Otherwise, pool board objects instead of constant reallocation.

One excellent paper I found for game development is on Othello—highly recommended for crunch-time competitions.

Participate here in HackerEarth's AI challenge, Battle of the Bots.