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 the higher regularity theory of partial differential equations. The proofs are based on cancellation and coupling methods as well as an improved version of the cylinder walk argument.