Page 1 of 1

playing optimally: definition

PostPosted: Thursday, 16th February 2017, 13:18
by pedritolo
I'll formally define what constitutes the optimal playing strategy for dcss.

Since dcss is a fully-deterministic game (rng is only pseudo-random, with initial seeds for map gen and combat and such), like chess, we can construct a full decision tree for each tuple of possible initial rand seeds.
Now we mark each branch as OK if it has a valid path to a win scenario (we could complicate and weight based on #turns to win, etc).
Once we have this collection of decision trees, we can determine the best move for any given ongoing game by
1- Find all decision trees that match what the game has encountered so far (different starting seeds may lead to identical game starts).
2 - Take the decision branch that has the greater proportion of OK's vs non-OK's across all the matching decision trees.

That's optimal gameplay. It exists, and it can be quantified.

When it comes to using the hypothetical optimal player as a deciding factor on game design considerations, I see it a bit like the efficient-market hypothesis - theoretically interesting, but wholly inadequate to describe reality. And for the same reasons - people's motivations are not at all rational.

Re: playing optimally: definition

PostPosted: Thursday, 16th February 2017, 16:03
by lethediver
Tldr; maximize winrate

Re: playing optimally: definition

PostPosted: Thursday, 16th February 2017, 17:16
by Shard1697
of course, there is also optimal play for getting highscore, optimal play for low turncount, optimal play for low realtime, and optimal play for winning as much as possible without driving yourself insane(the realworld cost of too much optimal play)

Re: playing optimally: definition

PostPosted: Thursday, 16th February 2017, 19:37
by Sprucery
I try to play optimally for maximizing my enjoyment of the game.

Re: playing optimally: definition

PostPosted: Thursday, 16th February 2017, 20:28
by moocowmoocow
Signs of optimal play:
- Pile of broken keyboards
- Clumps of hair missing
- Bleeding from eyes
- Deep sense of loss and regret

Re: playing optimally: definition

PostPosted: Thursday, 16th February 2017, 20:50
by pedritolo
Shard1697 wrote:of course, there is also optimal play for getting highscore, optimal play for low turncount, optimal play for low realtime, and optimal play for winning as much as possible without driving yourself insane(the realworld cost of too much optimal play)


Sure. As long as a cost function can be quantitatively defined, it can trivially be incorporated in my definition above. I gave in parentheses an example for low turncount.

Re: playing optimally: definition

PostPosted: Thursday, 16th February 2017, 20:57
by CanOfWorms
what if there's a branch with 2 OKs but 10^100 non-OKs and another branch that has no sub-branches and is OK, is it still optimal to take the branch with 2 OKs (e.g. if you have the orb of zot and you're on the exit, is it more optimal to do random things since it can generate more OK branches instead of winning)

Re: playing optimally: definition

PostPosted: Thursday, 16th February 2017, 21:02
by pedritolo
CanOfWorms wrote:what if there's a branch with 2 OKs but 10^100 non-OKs and another branch that has no sub-branches and is OK, is it still optimal to take the branch with 2 OKs (e.g. if you have the orb of zot and you're on the exit, is it more optimal to do random things since it can generate more OK branches instead of winning)


You always take the branch with the highest proportion of OK's vs non-OK's. Well spotted, I'll edit my original post.

Re: playing optimally: definition

PostPosted: Thursday, 16th February 2017, 23:23
by tasonir
You didn't specifically address the end condition: when you're on the exit with the orb, you can generate more OK's by just walking around or picking up/dropping items. There needs to be some notion of taking the shortest branch towards the actual winning turn, but you don't necessarily want to always choose the shortest OK branch, as then you're solving for a speedrun and taking high risk activities. This would of course be perfectly safe if you really had this perfect knowledge vision of the game, as you'd already know the 10,000 steps required to win, so taking a high risk speed run path would be optimal.

But optimizing for winrate still shouldn't walk back and forth just because it's safe, so there needs to be some way to say "take the safest steps which also decrease the total length of branches moving forward".

Re: playing optimally: definition

PostPosted: Thursday, 16th February 2017, 23:55
by papilio
The playstyle defined by tavern meme "playing optimally" maybe could maximize winning probability of the given game (though I seriously doubt about that),
the clear fact is that playing in that style is extremely tedious, cumbersome and sucks ass

Re: playing optimally: definition

PostPosted: Friday, 17th February 2017, 00:00
by Siegurt
tasonir wrote:You didn't specifically address the end condition: when you're on the exit with the orb, you can generate more OK's by just walking around or picking up/dropping items.


He revised it to be the branch with the highest *proportion* of oks, the win condition of "take the exit with the orb" has 1:1 (100%) oks, any other action would be less than 100%, so would be a worse proportion.

Edit: hmm, i retract that, any activity that doesn't directly add any not ok paths, and still allows for the victory action with no possible intervention has the same proportion 100% of oks.

Re: playing optimally: definition

PostPosted: Friday, 17th February 2017, 00:03
by pedritolo
tasonir wrote:You didn't specifically address the end condition: when you're on the exit with the orb, you can generate more OK's by just walking around or picking up/dropping items. There needs to be some notion of taking the shortest branch towards the actual winning turn, but you don't necessarily want to always choose the shortest OK branch, as then you're solving for a speedrun and taking high risk activities. This would of course be perfectly safe if you really had this perfect knowledge vision of the game, as you'd already know the 10,000 steps required to win, so taking a high risk speed run path would be optimal.

But optimizing for winrate still shouldn't walk back and forth just because it's safe, so there needs to be some way to say "take the safest steps which also decrease the total length of branches moving forward".


Let's not forget that the game, and hence each branch, is finite due to either lack of food or the "the world has ended" event at turn ????. As turns go by, the branches presented to you tend to be more OK'ish the sooner they can potentially lead to the exit sooner.

Re: playing optimally: definition

PostPosted: Friday, 17th February 2017, 00:06
by pedritolo
papilio wrote:The playstyle defined by tavern meme "playing optimally" maybe could maximize winning probability of the given game (though I seriously doubt about that),
the clear fact is that playing in that style is extremely tedious, cumbersome and sucks ass


Yes, I also think that most strategies usually classified as "playing optimally" are dubious at best, and in any case lack supporting empirical evidence.

Re: playing optimally: definition

PostPosted: Friday, 17th February 2017, 03:00
by bel
I have no idea why "optimal play" is compared to EMH, but EMH is far from useless. It reminds a casual investor (which is most of the investors) that they should stop wasting their time in trying to pick stocks and put their investment in index funds. There are also many arguments (not just theoretical), where EMH can provide a much better guide to economic matters than ignorant commentators. It is not a panacea and shouldn't be used dogmatically, but that's true of anything.

Coming back to "optimal play", I am not sure why optimal play is defined like this. How is it useful? For instance, it says that the crawl is deterministic because the RNG is pseudo-random. In practice, nobody knows the state of the RNG, so this assumption is useless. You can create some perfect definition, but you have to show how it's useful. If your aim is to only show that the concept of optimal play is useless, you've not shown it, in my opinion.

I find it interesting that you give the example of chess as a completely deterministic game, but your argument applies there as well: "Optimal play" can be defined in chess, but nobody directly uses the definition (unless you have a forced mate). But one talks all the time of "the best move", or "the move giving the most practical chances".

Here's a chess analogy and a corresponding crawl analogy. "Winning a piece for two pawns" vs "getting to lair".

Neither will guarantee that you win the game, but they increase the chances. So if you can pick an early god that gets you to lair, you will have a better chance of winning the game rather than waiting for some specific altar deep into the game.

One can argue about whether my analogy is good or bad, but here I'm simply arguing that the "optimal play" definition you gave isn't really useful.

Re: playing optimally: definition

PostPosted: Friday, 17th February 2017, 04:03
by TrumpTrain
true, and if you reach lair and choose the wrong skills, you wont have the power to kill monsters and gather the runes. Playing optimally also means leveling up the right skills and having a long term plan as to not get "stuck" not being able to progress because your skills are too diverse.

And for example,

if you are going through lair and you see snake and shaols, then you know you are up against a tough game depending on your character. Seeing these branches early and knowing how to invest in each skill takes times and knowledge to be able to win consistently like dynast (rip). You have to respond accordingly based on what you get as loot and the branches given.

Re: playing optimally: definition

PostPosted: Friday, 17th February 2017, 05:21
by VeryAngryFelid
TrumpTrain wrote:true, and if you reach lair and choose the wrong skills, you wont have the power to kill monsters and gather the runes. Playing optimally also means leveling up the right skills and having a long term plan as to not get "stuck" not being able to progress because your skills are too diverse.


Very true. I remember this type of problem from when I lost 5 NaEn's in a row in Lair. Those deaths helped me realize where my skilling mistakes were.

Re: playing optimally: definition

PostPosted: Friday, 17th February 2017, 11:28
by pedritolo
bel wrote:For instance, it says that the crawl is deterministic because the RNG is pseudo-random. In practice, nobody knows the state of the RNG, so this assumption is useless. You can create some perfect definition, but you have to show how it's useful. If your aim is to only show that the concept of optimal play is useless, you've not shown it, in my opinion.


Those are some very fair points. I agree, being pseudo-rng in this case is irrelevant.
Let me put this in a different perspective. By iterating through different randseeds and gathering their decision trees, ultimately I believe I'm doing a monte carlo sampling on the probabilities of winning for a given decision branch conditioned on the current known game state.
I'm pretty happy to fave a draft definition formalizing an once ambiguous matter. It means people can use unambiguous terms when discussing the subject.

Re: playing optimally: definition

PostPosted: Saturday, 18th February 2017, 12:09
by ion_frigate
My brain is hurting from imagining the processing power required to actually calculate even a single decision tree. Since monster generation will eventually stop, that means that a mummy can survive the anti-scumming police and literally make random moves for ~200000000 turns before going for the orb. So a decision tree will have something on the order of <several dozen>^200000000* nodes, which is an unconscionably huge number.

Non-mummies aren't much better, since their 200000000 turn decision tree is basically: act randomly for 1500 turns, scum Pan/Abyss for food, rinse, repeat (or alternately, scum for and stash 200000 meat rations). Since we're looking at the set of all possible decisions, you should be able to optimize the (non-random) search for food down to a fairly small portion of the 200000000 turns.

* Thinking of actions a mummy can carry out every turn indefinitely: 52 items to drop/pick up, 8 squares to move to, 24 squares to swing a reaching weapon at, etc.

Re: playing optimally: definition

PostPosted: Saturday, 18th February 2017, 12:53
by Magipi
ion_frigate wrote:My brain is hurting from imagining the processing power required to actually calculate even a single decision tree.
(...)

You are weirdly overestimating the whole thing. You don't want to calculate every possible future event, that is both impossible and impractical. You only calculate the current encounter, only one monster is possible.

Re: playing optimally: definition

PostPosted: Saturday, 18th February 2017, 13:00
by Magipi
CanOfWorms wrote:what if there's a branch with 2 OKs but 10^100 non-OKs and another branch that has no sub-branches and is OK, is it still optimal to take the branch with 2 OKs (e.g. if you have the orb of zot and you're on the exit, is it more optimal to do random things since it can generate more OK branches instead of winning)

The reason I don't understand this is simply that I have no clue what you mean by OKs in that sentence.

Re: playing optimally: definition

PostPosted: Saturday, 18th February 2017, 15:12
by ion_frigate
Magipi wrote:
ion_frigate wrote:My brain is hurting from imagining the processing power required to actually calculate even a single decision tree.
(...)

You are weirdly overestimating the whole thing. You don't want to calculate every possible future event, that is both impossible and impractical. You only calculate the current encounter, only one monster is possible.


Unless I'm severely misunderstanding the OP, he means calculating decision trees for entire games. This isn't serious advice (hence its presence in CYC), just a humorous way to illustrate a mathematical definition of "optimal play."

It most certainly does not depend on a single monster, or even a single encounter. Always using potions of heal wounds the second you take >38HP damage definitely optimizes your chances of surviving any single encounter with a monster that does <38 damage/turn. It also makes you much less likely to survive future encounters, since you're now out of potions of heal wounds. Another example would be how pillar dancing an ogre makes it less likely you'll die to that ogre but more likely you'll die to a passing centaur.

Re: playing optimally: definition

PostPosted: Saturday, 18th February 2017, 15:30
by ion_frigate
Magipi wrote:
CanOfWorms wrote:what if there's a branch with 2 OKs but 10^100 non-OKs and another branch that has no sub-branches and is OK, is it still optimal to take the branch with 2 OKs (e.g. if you have the orb of zot and you're on the exit, is it more optimal to do random things since it can generate more OK branches instead of winning)

The reason I don't understand this is simply that I have no clue what you mean by OKs in that sentence.


What he means is:

pedritolo wrote:we mark each branch as OK if it has a valid path to a win scenario


Or loosely translated from math-speak, a branch is OK if every path in it doesn't end with your death. The OP then amended his proposition to say that you choose the branch with the highest proportion of OKs, instead of simply the most OKs, since CanOfWorms pointed out that the latter idea doesn't make sense.

Re: playing optimally: definition

PostPosted: Saturday, 18th February 2017, 17:21
by Magipi
Oh, thank you!

When I first read the opening post, I thought that I vaguely understood it, but it was so vague that I misunderstood it and also I was so confused that I immediately forgot that he used this weird "OK" thingy. Not one of my best moments.
Now I think that I understand (but I might be wrong again), and I agree with you. It seems impossible.

Re: playing optimally: definition

PostPosted: Saturday, 18th February 2017, 21:28
by TrumpTrain
Playing optimally also means playing on a keyboard, having the right environment, the right chair, well rested and hydrated, relaxed.