<p>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.</p>
<p>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 &quot;non-linear optimization problems&quot;.</p>
<p>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.</p>
<p><strong>EDIT:</strong></p>
<p>An example of a CodinGame challenge is their Fall Challenge 2020 which essentially is writing an agent to play the board game <a href="https://www.board-game.co.uk/how-to-play-century-spice-road/" rel="nofollow noreferrer">Spice Road</a> against another agent.</p>

CC BY-SA 4.0
2021-01-19T23:58:48.853Z
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?
D.W.
CC BY-SA 4.0
2021-01-20T02:31:40.260Z
I added an example (one challenge was to write an agent for the board game [Spice Road](https://www.board-game.co.uk/how-to-play-century-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.
Goh
CC BY-SA 4.0
2021-01-20T04:15:17.297Z
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.
D.W.
CC BY-SA 4.0
2021-01-20T07:21:52.917Z
To me, this question seems to basically ask "What is the CS theory of AI problems?", which is very broad.
Laakeri
CC BY-SA 4.0
2021-01-20T08:25:58.887Z
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.
Emil Jeřábek
<ai.artificial-intel>
What's the relevant CS theory for CodinGame challenges?
Goh
# What's the relevant CS theory for CodinGame challenges?

(Asked by: username_0 on 2021-01-19)

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](https://www.board-game.co.uk/how-to-play-century-spice-road/) against another agent.

**Tags:** ai.artificial-intel
> **Comments:**
> **username_1**: 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?  
> **username_0**: I added an example (one challenge was to write an agent for the board game [Spice Road](https://www.board-game.co.uk/how-to-play-century-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.  
> **username_1**: 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.  
> **username_2**: To me, this question seems to basically ask "What is the CS theory of AI problems?", which is very broad.  
> **username_3**: 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.  

---

## 0 answers

