A common pattern with these kind of restarts is to assume that the player wants to play the first time and then ask if he/she wants to continue before ending.
play = 'y'
while play == 'y'
Do your game logic here
play = input('Would you like to play in-between [y|n]? ')
Hopefully that should show you how to get back on track.
Edit: sorry I saw now that this functionality was already in place. The issue you are having is that you get stuck in loops when you look at what value guess is, instead of looping you should use a if statement when checking what the guess is.