0
$\begingroup$

CodinGame challenges are basically extremely large decision trees, where your program is trying to find the node with the highest possible score. Greedy algorithms don't work because picking a locally optimal path (such as the highest-value child of the current node) can lead to a globally suboptimal result. Nor do any other straightforward algorithmic approaches, such as dynamic programming.

I'm wondering what's the relevant CS theory for this kind of problems. I'm not even sure what to call them, except maybe "non-linear optimization problems".

I'm also interested in approaches to solve them. Would some sort of machine-learning work? It seems like it should, since the ML approach of AlphaStar was successful in tackling the Starcraft game, which seems to be the same class of a problem.

EDIT:

An example of a CodinGame challenge is their Fall Challenge 2020 which essentially is writing an agent to play the board game Spice Road against another agent.

Improve this question
$\endgroup$
5
  • 4
    $\begingroup$ Can you give a self-contained description of CodinGame challenges, so that the question will be answerable even by those who don't have any prior familiarity with them? What makes you think this is a research-level question about theoretical CS? $\endgroup$
    – D.W.
    Jan 19 at 23:58
  • $\begingroup$ I added an example (one challenge was to write an agent for the board game Spice Road). Generally you are tasked with writing agents to compete against other agents in some sort of a turn-based game, such as a board game. I'm not sure what a "research-level question" is, quite frankly, I'm asking here since this is a theoretical question about CS and I am interested in the state of research in this area. $\endgroup$
    – Goh
    Jan 20 at 2:31
  • 1
    $\begingroup$ That didn't help since I don't know what a Spice Road board game is. Can you give a concise formulation in a self-contained fashion, written for a CS audience who doesn't know that stuff? I'm a little worried that you're saying that's an "example"; I'm worried that others ones might be different and this might be too broad. $\endgroup$
    – D.W.
    Jan 20 at 4:15
  • $\begingroup$ To me, this question seems to basically ask "What is the CS theory of AI problems?", which is very broad. $\endgroup$
    – Laakeri
    Jan 20 at 7:21
  • $\begingroup$ Like the other commenters, I'm rather in the dark what this question is all about, but the complexity of winning strategies for various kinds of games is certainly a studied subject. $\endgroup$
    – Emil Jeřábek
    Jan 20 at 8:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.