This paper addresses energy efficient VNF placement and chaining over NFV enabled infrastructures. VNF placement and chaining are formulated as a decision tree search to overcome this NP-Hard problem complexity. The proposed approach is an extension of the Monte Carlo Tree Search (MCTS) method to achieve energy savings using physical resource consolidation and sharing VNFs between multiple tenants. A real cloud testbed and extensive simulations are used to assess performance and ability to scale with problem size. Evaluation results show significant reduction in energy consumption of the proposed placement solution compared to related work. The polynomial complexity of our proposal is highlighted by the simulation results.