I will show that self-dual gravity in Euclidean four-dimensional Anti-de Sitter space (AdS4 ) can be described by a minimally coupled scalar field with a cubic interaction written in terms of a deformed Poisson bracket, providing a remarkably simple generalisation of the Plebanski action for self-dual gravity in flat space. This implies a novel symmetry algebra in self-dual gravity, notably an AdS4 version of the so-called kinematic algebra. This provides a concrete starting point for defining the double copy for Einstein gravity in AdS4 by expanding around the self-dual sector. Moreover, I will show that the new kinematic Lie algebra can be lifted to a deformed version of the w1+∞ algebra, which plays a prominent role in celestial holography.