Strongest cribbage bots
I've played literally hundreds of AI's... the strongest opponent cribbage games are all cheating.
The core Issues
Cribbage is focused upon 3 key priorities:

maximize points in hand
maximize points in play
minimize risk of giving points in the crib.

These boil down to two key skills:

Keeping
Playing

Playing is governed by a fairly easily coded set of rules. It's about 30 or 40 decision points, barring reading of the opponent's body language. Coded, it can be done convincingly hard in about 250 lines of basic code.
Keeping is much harder, because it has to balance all three priorities. My own decision tree starts with looking for certain combinations. This alone is several hundred lines of code. ANd then the exception seeking - which requires a good risk assessment protocol. And this is where it gets hard to code.
The AIs
The best non-cheating AI's I've played against (some 30 different programs, 10 of which I was able to examine the source, the others had a normal distribution of hands) are generally about as good as I am. I'm pretty good, but not great.
Now, I've played some 50+ different cribbage games - and I know for a fact that 3 of them cheat, and suspect about 20 more cheat.
The simplest cheat mechanism is to have the computer's hand use a different randomization than the player's hand. One such program was for PalmOS - In 30+ sets to 8 games, it never once had a hand less than 4 points, and never had a 19 crib, either. And it averaged over 6 points per hand.
Several others use similar, but I'm less certain of them.
One, I got hold of the source, and found the code actually gave the computer 8 cards, not 6, kept 4, put two in the crib, and two back in the deck. It was incredibly hard to beat, but occasionally got a 19 hand. I suspect many of using 1-2 extra cards like this.
The Third Key Skill
There is a 3rd key skill for Cribbage - one that AIs as yet have not implemented: reading one's opponent.
EG: In 2004, my buddy George and I played over 50 sets. We usually played  a set during the week, and almost always a set on the weekend, sometimes 2 sets on the weekend. Our play varied by whether we were watching TV or not - when not, we both knew what the other had by subtle cues of posture and reaction to cards. Cribs while not watching TV were usually 0-4 points, and hands typically in the 4-15 point range, with the occasional 2 or 19. When we weren't paying attention, cribs varied more widely, including a 29... I had 5-6-7-8-8-J, Geo had 5-5-7-7-8-8; turn was, of course, the missing jack, my crib. I knew he was throwing points because, while he threw down almost immediately, he also had an eyebrow twitch (a tell for a pair of pairs or a pair royal plus 15-complement). Had it been his crib, with the twitch I might have thrown the 8-J instead of the 5-J.
One of the reasons for including &quot;Cheating&quot; AI's is because that can simulate to a certain degree the reading of one's opponent and the effect upon scores.
Further Discussion
To date, I've seen little documentation of AI work in Cribbage - I've found one academic paper (Kendall &amp; Shaw, 2002), and it is more interested in the development of their own AI. Further, it compares to an non-heuristic AI - Ultimate Cribbage - which I've played, and found a solid opponent.
Cheating AI's, however, are the hardest ones I've found to play against. Just be warned, however - some of those can train one to suboptimal play, especially those that cheat with the crib, as your own crib-risk calculations can become skewed.