Is finding martingales black magic?

I've recently been learning about the power of martingales for calculating various stochastic quantities. This is a bit of a meta question: is coming up with the right martingale for the quantity you want just complete black magic?

As an example, consider an unbiased random walk, where we start at position $x$ and want the probability we either hit $0$ or $L$. In this case (after shifting the start to $0$ and left/right limits to $-x$ and $L-x$) a good martingale to use for the calculation is $$S_n=\sum_{i=1}^n X_i$$ where $X_i$ is the random variable of the steps ($X_i=\pm 1$ with equal probability).

However, this is not a martingale when the walk is biased, i.e. $X_n=+1$ with probability $p$ and $X_n=-1$ with probability $q=1-p$. Then it turns out that we should use a different martingale for the calculation, namely $$Y_n=\left(\frac{q}{p}\right)^{\sum_{i=1}^n X_i}.$$

How does one come up with the appropriate martingale to calculate a given quantity in general?

Edit: fixed definition of appropriate martingale for unbiased case above, thank you commenters...

Let $f:\mathbb Z\to \mathbb R$ be some function. Then $$ \mathbb E[f(S_{k+1})|\mathcal F_k] = \frac12 (f(S_{k}+1)+f(S_k-1)) $$ thus in order for this to be a martingale $$ \frac{1}{2} (f(S_k+1)+f(S_k-1)) = f(S_k) $$ has to be satisfied, i.e. if your $f$ is such that $$ \frac{1}{2}(f(x+1) + f(x-1)) = f(x) $$ then $f(S_k)$ is a martingale. Unfortunately not many function are suitable to do this. $$ f(x+1) = 2f(x)-f(x-1) \quad x\in\mathbb Z. $$ the solution to this recursion is $$f(n) = c_0 +c_1n $$ hence only the constant and the linear function solves this.

Now if $f:\mathbb N_0\times \mathbb Z \to \mathbb R$, then things look a little different. Namely $$ f(n,S_n)=f(0,S_0)+ \sum_{k=1}^n f(k,S_{k-1})-f(k-1,S_{k-1}) + \sum_{k=1}^nf(k,S_k)-\mathbb E[f(k,S_k)|\mathcal F_{k-1}] + \sum_{k=1}^n \mathbb E[f(k,S_{k})|\mathcal F_{k-1}]- f(k,S_{k-1}) $$ The second sum defines a martingale. So, if the first and the last sum add upp to $0$, then $f(S_n)$ is a martingale. After doing some algebra if $f$ is such that $$ f(k,x+1)+f(k,x-1)-2f(k-1,x)=0 \quad x\in \mathbb Z $$ then this happens.

Example: choose $f(n,x) = x^2-n$, i.e. $f(n,S_n)=S_n^2-n$. Then $$ f(k,x+1)+f(k,x-1)-2f(k-1,x) = (x+1)^2-k + (x-1)^2-k -2(x^2-(k-1)) = x^2+2x+1 + x^2-2x+1 -2k -2x^2 +2k-2=0. $$

Note: One can generalize this argument for the non-symmetric walk, and basically any kind of discrete time stochastic process $X_n (\in L^1$ for all $n$) of course with the appropriate modifications.