Agdestein es gran maestro de ajedrez y siete veces campeón noruego.

A nivel local, su dominio regular de los campeonatos de ajedrez noruegos y nórdicos durante la década de 1980 demostró con creces que había pocos jugadores que podían resistir su estilo emprendedor y creativo.

En 1999, Adgestein regresó a la senda del triunfo ganando el torneo de Cappele la Grande.

[4]​ Agdestein ha representado a su país siete veces en la Olimpiada de Ajedrez, generalmente jugando en el primer tablero y ganando una medalla de oro individual en su primera aparición en 1982.

Su apodo en el Internet Chess Club (ICC) es «Gruk».