  We define a random step size tug-of-war game, and show that the gradient of a
value function exists almost everywhere. We also prove that the gradients of
value functions are uniformly bounded and converge weakly to the gradient of
the corresponding $p$-harmonic function. Moreover, we establish an improved
Lipschitz estimate when boundary values are close to a plane. Such estimates
are known to play a key role in higher regularity theory of partial
differential equations. The proofs are based on cancellation and coupling
methods as well as improved version of the cylinder walk argument.
