Genre?

It's an action game. Somewhat similar to Descent but with a more developed plot.

Heh, in that case I haven't probably heard of it. Unless I've never read the plot of that game.

Well, the game has a lot of characters, even more dialogues (sometimes even mid-combat), the protagonist displays some sense of humor and you know what you are doing and why. You even get a plot twist or two mid-game and some more closer to the end. Your character even has a shiny name to be remembered by.

To speed things up, I'll drop another hint:
Succubus is what you're after.

Well, going off on the note that it's an action game, you got a ship in a game of dice and you had a friend, it is Risen?

Is it a fantasy game?

tug of war with the cyclops?

It's not Risen and not a fantasy game.
Edit: I don't recall saying that you won the ship in a game of dice. You got the ship from a friend as replacement for the one that was stolen.
Huh? No, no cyclops here, sorry.
No.

Edit 2: did I mention the game has a deep plot? :-)

.....lol

Oh sorry, that's from the previous one.

So is it present-era game? Because succubus is usually present only in fantasy games or in a mix of scifi/fantasy.

Also, we usually call it "strangling the one-eyed serpent".
The game is set in the future. A post-apocalyptic future.
And it's not a literal demon of lust I meant.

Aquanox?

That's the one. :-)
Succubus is the name of the ship that was stolen from the protagonist - Emerald Flint. The game's set in post-apocalyptic future where humanity lives underwater.

So in keeping with the post-apocalyptic theme:

Help! This game is gone from my library... No, sorry, it's there again... Oh wait, it's gone... Nope, there it is again...

Teenagent! ;)