Body: <p>I'm attempting to write an AI for the game <a href="https://en.wikipedia.org/wiki/Slay_the_Spire" rel="nofollow noreferrer">Slay the Spire</a>.  One of the tasks it will need to do is navigate the map.  The map is a directed acyclic graph with the same start and end node.</p>
  <p>Each node (including the end node) will have 2 values associated with it: Expected value and death probability.  The goal of the AI should be to maximize the expected value without dying.  So far, none of this seems tough.</p>
  <p>The twist here is that the death probability changes over time.  Some nodes (elites) have high volatility:  The death probability may go up or down drastically as we move through the map.  The pathfinding algorithm would need to consider <em>adjacent alternatives</em>.  A path that allows me to switch to a low-volatile node if things are getting tough is important.</p>
  <p>As an example, the following map has two major routes.  Both routes have an elite (the creature with horns), but the one on the right is a forced elite, while the one on the left can be skipped if death probability is too high.  The ability for me to be flexible mid-route is an attractive feature, and one I'd like to take into account when pathfinding somehow.</p>
  <p><a href="https://i.sstatic.net/VmnMa.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/VmnMa.png" alt="Sample map" /></a></p>
  <p>How can my path-finding algorithm take into account adjacent paths/path flexibility?  Is this even a job for pathfinding at all?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-02-20T20:27:01.683Z
Comments.Text: I don't know Slay the Spire. Can you explain how your AI will get access to the map? E.g. is it always the same and someone (maybe you) has coded it up outside the game. Or do you have an API that will allow your bot to inspect game state - including the map - to help make decisions?
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-02-20T21:30:29.333Z
Comments.Text: I essentially have an API to inspect the game state, including the game map.  The values "expected value", "death probability", and "volatility" are calculated by a separate part of my AI, and fed into my path-planning algorithm.  All paths are visible from the start, and every node will have those 3 values.
Comments.UserDisplayName: Nathan Merrill
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-02-20T21:39:07.263Z
Comments.Text: I've added a picture, hopefully that helps.
Comments.UserDisplayName: Nathan Merrill
Tags: <path-planning><path-finding>
Title: How to pathfind with volatile probabilities (Slay the spire)
UserDisplayName: Nathan Merrill
ThreadText: # How to pathfind with volatile probabilities (Slay the spire)
  
  (Asked by: username_0 on 2021-02-20)
  
  I'm attempting to write an AI for the game [Slay the Spire](https://en.wikipedia.org/wiki/Slay_the_Spire). One of the tasks it will need to do is navigate the map. The map is a directed acyclic graph with the same start and end node.
  
  Each node (including the end node) will have 2 values associated with it: Expected value and death probability. The goal of the AI should be to maximize the expected value without dying. So far, none of this seems tough.
  
  The twist here is that the death probability changes over time. Some nodes (elites) have high volatility: The death probability may go up or down drastically as we move through the map. The pathfinding algorithm would need to consider *adjacent alternatives*. A path that allows me to switch to a low-volatile node if things are getting tough is important.
  
  As an example, the following map has two major routes. Both routes have an elite (the creature with horns), but the one on the right is a forced elite, while the one on the left can be skipped if death probability is too high. The ability for me to be flexible mid-route is an attractive feature, and one I'd like to take into account when pathfinding somehow.
  
  [![Sample map](https://i.sstatic.net/VmnMa.png)](https://i.sstatic.net/VmnMa.png)
  
  How can my path-finding algorithm take into account adjacent paths/path flexibility? Is this even a job for pathfinding at all?
  
  **Tags:** path-planning, path-finding
  
  > **Comments:**
  > **username_1**: I don't know Slay the Spire. Can you explain how your AI will get access to the map? E.g. is it always the same and someone (maybe you) has coded it up outside the game. Or do you have an API that will allow your bot to inspect game state - including the map - to help make decisions?  
  > **username_0**: I essentially have an API to inspect the game state, including the game map.  The values "expected value", "death probability", and "volatility" are calculated by a separate part of my AI, and fed into my path-planning algorithm.  All paths are visible from the start, and every node will have those 3 values.  
  > **username_0**: I've added a picture, hopefully that helps.  
  
  ---
  
  ## 0 answers
  
  