Non-oblivious Strategy Improvement

Details Non-oblivious Strategy Improvement Non-oblivious Strategy Improvement

2010-03-15

arxiv.org/abs/1003.2976v1

Computer Science

Computer Science and Game Theory

Scientific paper

We study strategy improvement algorithms for mean-payoff and parity games. We describe a structural property of these games, and we show that these structures can affect the behaviour of strategy improvement. We show how awareness of these structures can be used to accelerate strategy improvement algorithms. We call our algorithms non-oblivious because they remember properties of the game that they have discovered in previous iterations. We show that non-oblivious strategy improvement algorithms perform well on examples that are known to be hard for oblivious strategy improvement. Hence, we argue that previous strategy improvement algorithms fail because they ignore the structural properties of the game that they are solving.

Affiliated with

Also associated with

No associations

Rating

Non-oblivious Strategy Improvement does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Non-oblivious Strategy Improvement, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Non-oblivious Strategy Improvement will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-214960