If you look back before the mining boom, you can see that their current market share is sort of a continuation of that. I think the mining boom basically inflated their market share for a year or two, but unfortunately most of those cards weren't going to gamers. So, the reality is that AMD has been even less relevant in the gaming space for the past couple of years than it appeared (this sort of showed up in Steam survey results).
Now all of those cards are being sold on Ebay for firesale prices. You can get used RX 580s for close to $100. Compared to that a new RX 580 for $180 doesn't look that great. So, ironically AMD's gaming market share may actually be increasing now, but in terms of new sales it looks terrible.
The reality is that AMD hasn't been competitive for a long time now. They've come out with one architecture for every two Nvidia has come out with. That needs to turn around if they want to remain relevant. I also think they need to be competitive on the high end, both for "mind share", but also because not being competitive on the high end is just a reflection of the fact their architecture is one or two revisions behind where Nvidia is. They need to get back closer to technological parity.
If they only had the GPU division I'd say it was impossible (then again ATi probably wouldn't have allowed itself to get in this situation), but because the company sells CPUs too and Ryzen is doing well, I think it is possible for them to use the R&D money from CPUs to catch back up. As has been said a number of times, it's not something that happens overnight though.
