There seems to be only two possibilities, one when only two boxes are selected by both of them, which will have a chance of winning = 1/3, other one in which they select one common box and the other with a fair coin toss, which would work with probability if winning = 1/2.

there doesn’t exist any strategy if the thief is allowed to stay in the cave. (the ‘may’ condition of Note 1), if it is sure that he will definitely move in the adjacent cave then there exists a strategy.
In the worst case, thief can be caught in maximum of 24 searches. Strategy is as follows:
Fix one of the cave you are going to search every day, no matter what, (say it is cave no. 13). Now the problem reduces to searching of a linear block of caves and you can search one cave at a time.  So any particular day, thief can either be in an even numbered cave E = {2,4,6,8,10,12} or an odd numbered cave O = {1,3,5,7,9,11}.  Now, use this strategy to search 2-3-4-5-6-7-8-9-10-11-12-12-11-10-9-8-7-6-5-4-3-2 . This strategy guarantees to find the thief.