playing optimally: definition


If it doesn't fit anywhere else, it belongs here. Also, come here if you just need to get hammered.

User avatar

Shoals Surfer

Posts: 287

Joined: Friday, 19th August 2016, 21:21

Post Thursday, 16th February 2017, 13:18

playing optimally: definition

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.
Last edited by pedritolo on Thursday, 16th February 2017, 21:04, edited 1 time in total.
make food great again

Crypt Cleanser

Posts: 714

Joined: Saturday, 5th December 2015, 06:56

Post Thursday, 16th February 2017, 16:03

Re: playing optimally: definition

Tldr; maximize winrate
User avatar

Tartarus Sorceror

Posts: 1762

Joined: Monday, 14th October 2013, 01:05

Post Thursday, 16th February 2017, 17:16

Re: playing optimally: definition

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)

For this message the author Shard1697 has received thanks: 3
nago, Sar, VeryAngryFelid
User avatar

Ziggurat Zagger

Posts: 4478

Joined: Wednesday, 23rd October 2013, 07:56

Post Thursday, 16th February 2017, 19:37

Re: playing optimally: definition

I try to play optimally for maximizing my enjoyment of the game.
DCSS: 97:...MfCj}SpNeBaEEGrFE{HaAKTrCK}DsFESpHu{FoArNaBe}
FeEE{HOIEMiAE}GrGlHuWrGnWrNaAKBaFi{MiDeMfDe}{DrAKTrAMGhEnGnWz}
{PaBeDjFi}OgAKPaCAGnCjOgCKMfAEAtCKSpCjDEEE{HOSu
Bloat: 17: RaRoPrPh{GuStGnCa}{ArEtZoNb}KiPaAnDrBXDBQOApDaMeAGBiOCNKAsFnFlUs{RoBoNeWi

For this message the author Sprucery has received thanks: 6
nago, ololoev, runewalsh, scorpionwarrior, VeryAngryFelid, ZipZipskins

Blades Runner

Posts: 552

Joined: Tuesday, 10th April 2012, 21:11

Post Thursday, 16th February 2017, 20:28

Re: playing optimally: definition

Signs of optimal play:
- Pile of broken keyboards
- Clumps of hair missing
- Bleeding from eyes
- Deep sense of loss and regret

For this message the author moocowmoocow has received thanks:
VeryAngryFelid
User avatar

Shoals Surfer

Posts: 287

Joined: Friday, 19th August 2016, 21:21

Post Thursday, 16th February 2017, 20:50

Re: playing optimally: definition

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.
make food great again

Dungeon Master

Posts: 625

Joined: Thursday, 23rd October 2014, 03:08

Post Thursday, 16th February 2017, 20:57

Re: playing optimally: definition

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)

For this message the author CanOfWorms has received thanks:
chequers
User avatar

Shoals Surfer

Posts: 287

Joined: Friday, 19th August 2016, 21:21

Post Thursday, 16th February 2017, 21:02

Re: playing optimally: definition

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.
make food great again

Ziggurat Zagger

Posts: 5382

Joined: Friday, 25th November 2011, 07:36

Post Thursday, 16th February 2017, 23:23

Re: playing optimally: definition

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".

Slime Squisher

Posts: 395

Joined: Wednesday, 6th July 2016, 02:40

Post Thursday, 16th February 2017, 23:55

Re: playing optimally: definition

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
http://crawl.akrasiac.org/scoring/players/papilio.html

Done 15-rune wins with all playable species, backgrounds, gods!

Ziggurat Zagger

Posts: 6454

Joined: Tuesday, 30th October 2012, 19:06

Post Friday, 17th February 2017, 00:00

Re: playing optimally: definition

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.
Last edited by Siegurt on Friday, 17th February 2017, 00:04, edited 1 time in total.
Spoiler: show
This high quality signature has been hidden for your protection. To unlock it's secret, send 3 easy payments of $9.99 to me, by way of your nearest theta band or ley line. Complete your transmission by midnight tonight for a special free gift!

For this message the author Siegurt has received thanks:
pedritolo
User avatar

Shoals Surfer

Posts: 287

Joined: Friday, 19th August 2016, 21:21

Post Friday, 17th February 2017, 00:03

Re: playing optimally: definition

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.
Last edited by pedritolo on Friday, 17th February 2017, 00:08, edited 2 times in total.
make food great again
User avatar

Shoals Surfer

Posts: 287

Joined: Friday, 19th August 2016, 21:21

Post Friday, 17th February 2017, 00:06

Re: playing optimally: definition

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.
make food great again

bel

Cocytus Succeeder

Posts: 2184

Joined: Tuesday, 3rd February 2015, 22:05

Post Friday, 17th February 2017, 03:00

Re: playing optimally: definition

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.
Last edited by bel on Friday, 17th February 2017, 07:11, edited 1 time in total.

For this message the author bel has received thanks: 2
pedritolo, scorpionwarrior
User avatar

Halls Hopper

Posts: 80

Joined: Sunday, 8th January 2017, 05:05

Post Friday, 17th February 2017, 04:03

Re: playing optimally: definition

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.
Spoiler: show
hi

For this message the author TrumpTrain has received thanks:
VeryAngryFelid

Ziggurat Zagger

Posts: 4432

Joined: Friday, 8th May 2015, 17:51

Post Friday, 17th February 2017, 05:21

Re: playing optimally: definition

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.
Underestimated: cleaving, Deep Elf, Formicid, Vehumet, EV
Overestimated: AC, GDS
Twin account of Sandman25
User avatar

Shoals Surfer

Posts: 287

Joined: Friday, 19th August 2016, 21:21

Post Friday, 17th February 2017, 11:28

Re: playing optimally: definition

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.
make food great again

Slime Squisher

Posts: 377

Joined: Thursday, 12th June 2014, 06:56

Post Saturday, 18th February 2017, 12:09

Re: playing optimally: definition

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.

Cocytus Succeeder

Posts: 2173

Joined: Saturday, 2nd February 2013, 09:52

Post Saturday, 18th February 2017, 12:53

Re: playing optimally: definition

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.

Cocytus Succeeder

Posts: 2173

Joined: Saturday, 2nd February 2013, 09:52

Post Saturday, 18th February 2017, 13:00

Re: playing optimally: definition

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.

Slime Squisher

Posts: 377

Joined: Thursday, 12th June 2014, 06:56

Post Saturday, 18th February 2017, 15:12

Re: playing optimally: definition

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.

Slime Squisher

Posts: 377

Joined: Thursday, 12th June 2014, 06:56

Post Saturday, 18th February 2017, 15:30

Re: playing optimally: definition

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.

Cocytus Succeeder

Posts: 2173

Joined: Saturday, 2nd February 2013, 09:52

Post Saturday, 18th February 2017, 17:21

Re: playing optimally: definition

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.
User avatar

Halls Hopper

Posts: 80

Joined: Sunday, 8th January 2017, 05:05

Post Saturday, 18th February 2017, 21:28

Re: playing optimally: definition

Playing optimally also means playing on a keyboard, having the right environment, the right chair, well rested and hydrated, relaxed.
Spoiler: show
hi

For this message the author TrumpTrain has received thanks:
scorpionwarrior

Return to Crazy Yiuf's Corner

Who is online

Users browsing this forum: No registered users and 17 guests

Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group.
Designed by ST Software for PTF.