På det tidspunkt var han verdens yngste skakstormester Agdestein fik en andenplads ved det europæiske juniorskakmesterskab i 1984, og en delt førsteplads ved juniorverdensmesterskaberne i skak i 1986.