Способ хранения координат фишек

Есть два варианта хранения - хранение состояния игры (доски), а на ней фишек (например, массив

int board[8][8];

в котором пустые поля обозначены нулями, а непустые - номером стоящей там фишки.

Но исходя из "Необходимо, чтобы можно было максимально просто получить доступ к координатам выбранной фишки", вам нужен второй вариант - а именно, массив фишек с их координатами (x,y), которые можно реализовать как стандартный pair<int,int>, а можно с помощью своей структуры типа

struct Point {
    int x,y;
};

Но, как я понимаю, вам нужно и то, и другое - чтобы, зная фишку, сразу получить возможные ходы - например, пустая ли какая-то клетка?

Я бы просто делал класс типа Game, который бы хранил и доску, и четыре фишки, и при каждом ходе обновлял как координаты фишки, так и состояние доски. Интерфейс такого класса содержал бы функции для
- возврата координат фишки номер N
- возврата номера фишки на поле (x,y) (0, если пусто)
- перемещения фишки N на новое поле.

Как бы вы ни старались, сделать этот класс медленным - с 64 полями - у вас не получится. Какое нужно внутреннее представление - смотрите сами, что вам привычнее.

Пробовал запоминать координаты в обычный массив и в vector, но это не совсем удобно.

А что неудобно? Если делать массив, то нужно конвертер в наглядную форму сделать. И будет всё очень даже удобно.

Но я бы взял пример из шахмат. Где одна ось буквами обозначается, другая цифрами. Координаты записываются как A6, E3... и т.д. Это и очень быстрый вариант, и очень наглядный.