Player $A$ has a winning strategy. On his first $2^7$ moves he marks $2^8$ arbitrary cells so that the distance of every two of them is at least $10$. Such marks are not consecutive, so every time $B$ deletes exactly one mark on his move. Thus after $2^7$ combined moves of the two there are $2^7$ marks at distances at least $10$. Denote the group of these marks by $G$.

On each of his next $2^6$ moves $A$ marks cells to the left of two different cells from $G$, thus forming blocks of marks with length $2$. Since $B$ can delete at most one such block at a time, $2^6$ combined moves leave at least $2^6$ blocks of marks with length $2$.

Similarly, $A$ starts forming pairs of blocks with length $3$ on each of his next $2^5$ moves. Again $B$ can delete at most one such block on each move, hence after $2^5$ combined moves there remain at least $2^5$ blocks of marks with length $3$.

Proceeding analogously, $A$ can ensure that after some move of $B$ there will be $2^4$ blocks of length $4$, then $2^3$ blocks of length $5$, $2^2$ blocks of length $6$, $2^1 = 2$ blocks of length $7$ and finally $1$ block $K$ of length $8$. Now it is $A$'s turn to move, and he wins by marking the two cells to the left of $K$.